A SIMPLEX-SEARCH ALGORITHM FOR SOLVING ZERO-ONE MIXED INTEGER PROGRAMS.
Abstract
An algorithm for solving zero-one mixed integer programming problems which has been developed and implemented in an all-in-core FORTRAN program is reported with computational experience on a variety of well-known problem types. The imbedded linear programs of Land and Doig, the derived binary constraints of Benders, and the binary feasibility tests introduced by Balas, are used in conjunction with augmented linear programs obtained by summarizing in the form of a linear inequality the set of solutions remaining to be (implicitly) enumerated when only partial completion of a branch-and-bound search has been accomplished. These augmented linear programs yield new sufficient conditions for optimality of an incumbent solution which have significantly accelerated convergence of the search procedure on a number of problem types, notably the Savage-Lorie project selection or multi-dimensional knapsack variety. Computational experience with scheduling, warehouse location, and economic investment planning models is also reported. The algorithm has proven satisfactory for use on a production basis, and is currently in use for selection of water resource development projects. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 13, 1969
- Accession Number
- AD0697301
Entities
People
- Ronald E. Davis
Organizations
- Stanford University