Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476391 | Computers & Operations Research | 2006 | 16 Pages |
Abstract
We present systematic procedures to construct examples of linear programs that cycle when the simplex method is applied. Cycling examples are constructed for diverse variants of pivot selection strategies: most negative reduced-cost and steepest-edge rule for the entering variable, and smallest ratio rule for the leaving variable (where ties are broken according to the least-index or the largest coefficient criterion, respectively). The results are of theoretical interest since only a limited number of cycling examples have been presented in the literature up to date. Constructed cycling examples may also serve as test problems to evaluate the practical performance of anticycling procedures or new variants of simplex type methods.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Peter Zörnig,