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

DOI10.1007/S10107-003-0488-1MaRDI QIDQ1890306zbMATH OpenOpenAlexFDO

Authors J. A. J. Hall, K. I. M. McKinnon

Publication date 3 January 2005

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0012242

zbMATH Keywords

cyclingdegeneracyexpandlinear programmingsimplex method

Mathematics Subject Classification ID

Linear programming (90C05)

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

Recommendations

• Systematic construction of examples for cycling in the simplex method
• Visualizing and Constructing Cycles in the Simplex Method
• Cycling in linear programming problems
• A note on cycling LP examples with permutation structure
• What is the worst case behavior of the simplex algorithm?

Cited in

(11)

• Solving large-scale optimization problems related to Bell's theorem
• Methods for convex and general quadratic programming
• A note on cycling LP examples with permutation structure
• Systematic construction of examples for cycling in the simplex method
• Primal and dual active-set methods for convex quadratic programming
• Visualizing and Constructing Cycles in the Simplex Method
• Solving multiscale linear programs using the simplex method in quadruple precision
• On cycling in the simplex method of the transportation problem
• A factorization with update procedures for a KKT matrix arising in direct optimal control
• Classroom Note:Hoffman's Circle Untangled
• Revisiting degeneracy, strict feasibility, stability, in linear programming

This page was built for publication: The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1890306)