J.A.J. Hall and K.I.M. McKinnon
Abstract
This paper introduces a class of linear programming examples which
cause the simplex method to cycle indefinitely and which are the
simplest possible examples which show this behaviour. The structure of
examples from this class repeats after two iterations. Cycling is shown
to occur for both the most negative reduced cost and steepest edge
column selection criteria. In addition it is shown that the
EXPAND anti-cycling procedure of Gill
et al is not guaranteed to prevent cycling.
Key words: Linear programming, simplex method, degeneracy, cycling.