#
The simplest examples where the simplex method cycles and conditions
where EXPAND fails to prevent cycling

###
Technical Report MS 96-010

**
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.

**
Text
**

PDF 96010.pdf

**
History:
**
Appears with minor modifications in the Southampton e-print archive as
math.OC/0012242

*Mathematical Programming* **100(1)**, 133-150, 2004.

**
Note:
**
An important member of the class of examples is illustrated by the
following LP
Explorer applet