An Improved Implicit Enumeration Approach for Integer Programming

A. M. Geoffrion
Additional contact information
A. M. Geoffrion: University of California at Los Angeles, Los Angeles, California

Operations Research, 1969, vol. 17, issue 3, 437-454

Abstract: This paper synthesizes the Balasian implicit enumeration approach to integer linear programming with the approach typified by Land and Doig and by Roy, Bertier, and Nghiem. The synthesis results from the use of an imbedded linear program to compute surrogate constraints that are as “strong” as possible in a sense slightly different from that originally used by Glover. A simple implicit enumeration algorithm fitted with optional imbedded linear programming machinery was implemented and tested extensively on an IBM 7044. Use of the imbedded linear program greatly reduced solution times in virtually every case, and seemed to render the tested algorithm superior to the five other implicit enumeration algorithms for which comparable published experience was available. The crucial issue of the sensitivity of solution time to the number of integer variables was given special attention. Sequences were run of set-covering, optimal-routing, and knapsack problems with multiple constraints of varying sizes up to 90 variables. The results suggest that use of the imbedded linear program in the prescribed way may mitigate solution-time dependence on the number of variables from an exponential to a low-order polynomial increase. The dependence appeared to be approximately linear for the first two problem classes, with 90-variable problems typically being solved in about 15 seconds; and approximately cubic for the third class, with 80-variable problems typically solved in less than 2 minutes. In the 35-variable range for all three classes, use of the imbedded linear program reduced solution times by a factor of about 100.

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.17.3.437 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:17:y:1969:i:3:p:437-454

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().