Visualizing and Constructing Cycles in the Simplex Method

David Avis (), Bohdan Kaluzny () and David Titley-Péloquin ()
Additional contact information
David Avis: School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6
Bohdan Kaluzny: School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6
David Titley-Péloquin: School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A6

Operations Research, 2008, vol. 56, issue 2, 512-518

Abstract: 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.

Keywords: linear; programming; theory (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0474 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:56:y:2008:i:2:p:512-518

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().