An Algorithm for the Bounded Variable Integer Programming Problem
- 1 July 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (3) , 505-513
- https://doi.org/10.1145/321832.321848
Abstract
An algorithm is proposed for the bounded variable pure integer programming problem which treats general integer variables directly in an implicit enumeration procedure closely related to that advanced by Balas and Geoffrion for binary programming problems. Means of obtaining near optimum solutions through a slight modification of the algorithm are discussed. Techniques which use bounds on variables to improve algorithmic efficiency are developed and examined computationally. Further computational results indicate that direct treatment of general integer variables is significantly more effective than binary expansion.Keywords
This publication has 9 references indexed in Scilit:
- A Survey of Integer Programming Emphasizing Computation and Relations among ModelsPublished by Elsevier ,1973
- Integer Programming Algorithms: A Framework and State-of-the-Art SurveyManagement Science, 1972
- Generalized implicit enumeration using bounds on variables for solving linear programs with zero‐one variablesNaval Research Logistics Quarterly, 1972
- Letter to the Editor—Computational Results of an Integer Programming AlgorithmOperations Research, 1969
- A Bound-and-Scan Algorithm for Pure Integer Linear Programming with General VariablesOperations Research, 1969
- An Improved Implicit Enumeration Approach for Integer ProgrammingOperations Research, 1969
- Integer Linear Programming: A Study in Computational EfficiencyManagement Science, 1969
- An Additive Algorithm for Solving Linear Programs with Zero-One VariablesOperations Research, 1965
- A tree-search algorithm for mixed integer programming problemsThe Computer Journal, 1965