A Monotonic Build-Up Simplex Algorithm for Linear Programming

Kurt M. Anstreicher and Tamás Terlaky
Additional contact information
Kurt M. Anstreicher: University of Iowa, Iowa City, Iowa
Tamás Terlaky: Delft University of Technology Delft, The Netherlands

Operations Research, 1994, vol. 42, issue 3, 556-561

Abstract: We devise a new simplex pivot rule which has interesting theoretical properties. Beginning with a basic feasible solution, and any nonbasic variable having a negative reduced cost the pivot rule produces a sequence of pivots such that ultimately the originally chosen nonbasic variable enters the basis, and all reduced costs which were originally nonnegative remain nonnegative. The pivot rule thus monotonically builds up to a dual feasible, and hence optimal, basis. A surprising property is that the pivot sequence results in intermediate bases which are neither primal nor dual feasible. We prove the correctness of the procedure, and relate it to other pivoting rules for linear programming.

Keywords: programming; linear; algorithms: monotonic buildup; programming; linear; parametric: shadow vertex algorithm (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.3.556 (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:42:y:1994:i:3:p:556-561

Access Statistics for this article

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