An Algorithm for Integer Linear Programming: A Combined Algebraic and Enumeration Approach

Gordon H. Bradley and Pran N. Wahi
Additional contact information
Gordon H. Bradley: Yale University, New Haven, Connecticut
Pran N. Wahi: IBM Scientific Center, Cambridge, Massachusetts

Operations Research, 1973, vol. 21, issue 1, 45-60

Abstract: This paper develops an algorithm for pure integer programming problems. It first transforms the integer programming problem to an algebraically equivalent Hermite canonical problem, and then employs the Fourier-Motzkin elimination. These algebraic operations transform the problem into a form that leads to an efficient implicit enumeration scheme to calculate an optimal solution. The algorithm constructs, in a finite number of operations, an optimal solution to an integer program with n variables and n or n + 1 inequality constraints. If the original problem has more than n + 1 constraints, then the integer program with only the constraints that are binding at an optimal linear programming solution is solved in place of the original problem. Computational results are presented.

Date: 1973
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.1.45 (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:21:y:1973:i:1:p:45-60

Access Statistics for this article

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