A Simplified Primal (All-Integer) Integer Programming Algorithm

R. D. Young
Additional contact information
R. D. Young: Rice University, Houston, Texas

Operations Research, 1968, vol. 16, issue 4, 750-782

Abstract: This paper describes a primal, all-integer algorithm for solving a bounded and solvable pure integer programming problem. The method is a primal analogue to the Gomory All-Integer Algorithm, and is a variant of the simplex method in sense that the Gomory algorithm is a variant of the dual method. The simplified primal algorithm makes these major amendments to the simplex method: (i) a special row, indexed by L , is adjoined to the tableau and is periodically revised by a well-defined procedure; (ii) in most cycles of the algorithm the pivot column, A J , is selected so that a LJ > 0 and (1/ a LJ ) A J is lexicographically smaller than (1/ a Lj ) A j for all nonbasic columns A j that have a Lj > 0; (iii) in all cycles of the algorithm a Gomory cut is adjoined after selection of the pivot column, and the cut is selected so that it will have a unit coefficient in the pivot column and it will qualify (in order to be used) as the pivot row. With comparatively minor restrictions on the selection of the row used to generate the Gomory cut the simplified primal algorithm is shown to be finite.

Date: 1968
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.16.4.750 (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:16:y:1968:i:4:p:750-782

Access Statistics for this article

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