A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem

Abstract

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.