This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Avis, D. Articles by Titley-Péloquin, D. Search for Related Content

Visualizing and Constructing Cycles in the Simplex Method

School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6
School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6
School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6
avis{at}cs.mcgill.ca
beezer{at}cs.mcgill.ca
dtitle{at}cs.mcgill.ca

Most examples of cycling in the simplex method are given without explanation of how they were constructed. An exception is Beale's example built around the geometry of the dual simplex method in the plane [Beale, E. 1955. Cycling in the dual simplex method. Naval Res. Logist. Quart. 2(4) 269–275]. Using this approach, we give a simple geometric explanation for a number of examples of cycling in the simplex method, including Hoffman's original example [Hoffman, A. 1953. Cycling in the Simplex Algorithm. National Bureau of Standards, Washington, D.C.]. This gives rise to a simple method for generating examples with cycles.

Subject classifications: linear programming theory.
History: Received September 2005; revision received January 2007; accepted April 2007.