数学优化
整数规划
剖切面法
本德分解
整数(计算机科学)
分解
线性规划
选择(遗传算法)
计算机科学
非线性规划
帕累托原理
趋同(经济学)
数学
非线性系统
物理
程序设计语言
经济
人工智能
生态学
生物
量子力学
经济增长
作者
Thomas L. Magnanti,Richard T. Wong
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:1981-06-01
卷期号:29 (3): 464-484
被引量:854
标识
DOI:10.1287/opre.29.3.464
摘要
This paper proposes methodology for improving the performance of Benders decomposition when applied to mixed integer programs. It introduces a new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations. The acceleration technique is based upon selecting judiciously from the alternate optima of the Benders subproblem to generate strong or pareto-optimal cuts. This methodology also applies to a much broader class of optimization algorithms that includes Dantzig-Wolfe decomposition for linear and nonlinear programs and related “cutting plane” type algorithms that arise in resource directive and price decomposition. When specialized to network location problems, this cut generation technique leads to very efficient algorithms that exploit the underlying structure of these models. In discussing the “proper” formulation of mixed integer programs, we suggest criteria for comparing various mixed integer formulations of a problem and for choosing formulations that can provide stronger cuts for Benders decomposition. From this discussion intimate connections between the previously disparate viewpoints of strong Benders cuts and tight linear programming relaxations of integer programs emerge.
科研通智能强力驱动
Strongly Powered by AbleSci AI