Letter to the Editor—Toward a Unifying Theory for Integer Linear Programming

During the last decade a great number of approaches and schemes have been proposed for solving integer linear programming problems. These range from the implicit enumeration schemes including, for example, the additive algorithm of Balas to schemes that proceed in a simplicial fashion to an optimal solution as does, for example, the All-Integer Method of Gomory. Still other approaches have been heuristic in nature and strive to achieve so-called good (not necessarily optimal) solutions. The purpose of this paper is to discuss a framework that appears to offer some potential for devising new algorithms, and, at the same time, provides a theory that helps to unify some of the previously advanced methods for solving integer linear programming problems. The framework involves the use of bounds on variables and is related to some of the author's earlier work on the Geometric Definition Method of linear programming.