Systematic construction of examples for cycling in the simplex method

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. (c) 2005 Elsevier Ltd. All rights reserved.