GENERALIZED EUCLIDEAN PROCEDURE FOR INTEGER LINEAR PROGRAMS.

Tyronza R. Richmond, Arunachalam Ravindran

Research output: Contribution to journalArticlepeer-review

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 R. E. Gomory all-integer algorithm.

Original languageEnglish (US)
Pages (from-to)125-144
Number of pages20
JournalNaval Research Logistics
Volume21
Issue number1
StatePublished - Jan 1 1974

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'GENERALIZED EUCLIDEAN PROCEDURE FOR INTEGER LINEAR PROGRAMS.'. Together they form a unique fingerprint.

Cite this