On the foundations of linear and integer linear programming I

Research output: Contribution to journalArticlepeer-review

85 Scopus citations

Abstract

In this paper we consider the question: how does the flow algorithm and the simplex algorithm work? The usual answer has two parts: first a description of the "improvement process", and second a proof that if no further improvement can be made by this process, an optimal vector has been found. This second part is usually based on duality -a technique not available in the case of an arbitrary integer programming problem. We wish to give a general description of "improvement processes" which will include both the simplex and flow algorithms, which will be applicable to arbitrary integer programming problems, and which will in themselves assure convergence to a solution. Geometrically both the simplex algorithm and the flow algorithm may be described as follows. At the ith stage, we have a vertex (or feasible flow) to which is associated a finite set of vectors, namely the set of edges leaving that vertex (or the set of unsaturated paths). The algorithm proceeds by searching among this special set for a vector along which the gain function is increasing. If such a vector is found, the algorithm continues by moving along this vector as far as is possible while still remaining feasible. The search is then repeated at this new feasible point. We give a precise definition for sets of vectors, called test sets, which will include those sets described above arising in the simplex and flow algorithms. We will then prove that any "improvement process" which searches through a test set at each stage converges to an optimal point in a finite number of steps. We also construct specific test sets which are the natural extensions of the test sets employed by the flow algorithm to arbitrary linear and integer linear programming problems.

Original languageEnglish (US)
Pages (from-to)207-226
Number of pages20
JournalMathematical Programming
Volume9
Issue number1
DOIs
StatePublished - Dec 1975

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'On the foundations of linear and integer linear programming I'. Together they form a unique fingerprint.

Cite this