A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
Fred Glover · Operations Research · 1965
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.
Cited by 327 works. doi:10.1287/opre.13.6.879
Authors
References
- Outline of an algorithm for integer solutions to linear programs
- Discrete-Variable Extremum Problems
- An Algorithm for the Traveling Salesman Problem
- Management Models and Industrial Applications of Linear Programming
- A Linear Programming Approach to the Cutting-Stock Problem
- An Automatic Method for Solving Discrete Programming Problems
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- AN ALL-INTEGER INTEGER PROGRAMMING ALGORITHM
- Algorithms for Solving Production-Scheduling Problems