A generalized euclidean procedure for integer linear programs

Tyronza R. Richmond and Arunachalam Ravindran

Naval Research Logistics Quarterly, 1974, vol. 21, issue 1, 125-144

Abstract: This paper investigates a new procedure for solving the general‐variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier‐Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all‐integer algorithm.

Date: 1974
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800210109

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:wly:navlog:v:21:y:1974:i:1:p:125-144

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().