The Accelerated Bound-and-Scan Algorithm for Integer Programming

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.