The Accelerated Bound-and-Scan Algorithm for Integer Programming

Bruce H. Faaland and Frederick S. Hillier
Additional contact information
Bruce H. Faaland: University of Washington, Seattle, Washington
Frederick S. Hillier: Stanford University, Stanford, California

Operations Research, 1975, vol. 23, issue 3, 406-433

Abstract: This paper presents a new implicit enumeration algorithm for solving the pure integer linear programming problem. The theory of equivalent integer programming problems is first used to reformulate the problem. A technique originally used with particular success in the bound-and-scan algorithm to deal with only a subset of the variables is extended to all of the variables in the restructured problem. In addition to the resulting basic enumeration scheme, the algorithm includes a scanning procedure and a method for identifying constraints that become redundant during the course of the algorithm. Computational experience on standard test problems is reported.

Date: 1975
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.3.406 (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:23:y:1975:i:3:p:406-433

Access Statistics for this article

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