A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
复制标题
DOI：
10.1287/opre.13.6.879
复制
发表时间：
1965-12
影响因子：
2.7
通讯作者：
F. Glover
中科院分区：
文献类型：
--
作者：
F. Glover
遵循Egon Balas最近应用于0-1整数规划问题并取得一定成功的一系列方法，本文的算法基于一种基本的树搜索结构，在该结构上叠加一系列测试，以排除树中所有可能的0-1解的大部分。在我们的方法中，枚举和测试的特定设计，加上一种特殊类型的约束(称为“代理约束”)的使用，导致了一种与目前可用于解决0-1整数规划问题的其他算法相比似乎非常有效的算法。然而，由于到目前为止所审查的问题的范围和规模有限，早期的有效性迹象必须被视为提示性的，而不是决定性的。在此基础上，用多相-对偶算法对三个算例问题进行了详细的求解，说明了其应用的各个方面。在结束语部分简要介绍了该算法对一般有界变量整数规划问题的推广。
Following a line of approach recently applied to the 0-1 integer programming problem with some success by Egon Balas, the algorithm of this paper is based upon an underlying tree-search structure upon which a series of tests is superimposed to exclude large portions of the tree of all possible 0-1 solutions from examination. In our method, the specific design of the enumeration and tests, supplemented by the use of a special type of constraint called a "surrogate constraint," results in an algorithm that appears to be quite efficient in relation to other algorithms currently available for solving the 0-1 integer programming problem. Early indications of efficiency must, however, be regarded as suggestive rather than conclusive, due to the limited range and size of problems so far examined. Following the analytical development of the method, three example problems are solved in detail with the Multiphase-Dual Algorithm to illustrate various aspects of its application. An extension of the algorithm to the general integer programming problem in bounded variables is briefly sketched in a concluding section.