Systematic construction of examples for cycling in the simplex method

Systematic construction of examples for cycling in the simplex method

0.00 Avg rating0 Votes
Article ID: iaor20072073
Country: United Kingdom
Volume: 33
Issue: 8
Start Page Number: 2247
End Page Number: 2262
Publication Date: Aug 2006
Journal: Computers and Operations Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.