Journal article
A Monotonic Build-Up Simplex Algorithm for Linear Programming
Operations research, Vol.42(3), pp.556-561
05/01/1994
DOI: 10.1287/opre.42.3.556
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.
Details
- Title: Subtitle
- A Monotonic Build-Up Simplex Algorithm for Linear Programming
- Creators
- Kurt M. Anstreicher - University of IowaTamás Terlaky - Delft University of Technology
- Resource Type
- Journal article
- Publication Details
- Operations research, Vol.42(3), pp.556-561
- DOI
- 10.1287/opre.42.3.556
- ISSN
- 0030-364X
- eISSN
- 1526-5463
- Language
- English
- Date published
- 05/01/1994
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380418002771
Metrics
15 Record Views