Systematic construction of examples for cycling in the simplex method

DOI10.1016/J.COR.2005.02.001MaRDI QIDQ2489285zbMATH OpenOpenAlexFDO

Authors Peter Zörnig

Publication date 16 May 2006

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2005.02.001

zbMATH Keywords

Mathematical programmingLinear programmingDegeneracyCycling

Mathematics Subject Classification ID

Linear programming (90C05)

Recommendations

• The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling
• 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?

Cites work

• scientific article; zbMATH DE number 3115468 (Why is no real title available?)
• scientific article; zbMATH DE number 794684 (Why is no real title available?)
• A new pivoting rule for solving various degeneracy problems
• A note on cycling in the simplex method
• A practicable steepest-edge simplex algorithm
• A practical anti-cycling procedure for linearly constrained optimization
• A simplex algorithm for piecewise-linear programming. II: Finiteness, feasibility and degeneracy
• An Algorithm for Large-Scale Quadratic Programming
• An exterior point simplex algorithm for (general) linear programming problems
• An integral simplex algorithm for solving combinatorial optimization problems
• Classroom Note:Hoffman's Circle Untangled
• Cycling in linear complementarity problems
• Cycling in linear programming problems
• Cycling in the transportation problem
• Degeneracy graphs and simplex cycling
• Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
• Least-index resolution of degeneracy in quadratic programming
• Making progress during a stall in the simplex algorithm
• On anti-cycling pivoting rules for the simplex method
• On cycling in the network simplex method
• On the bottleneck linear programming problem
• Parametric linear programming and anti-cycling pivoting rules
• Practical finite pivoting rules for the simplex method
• Resolution of the problem of degeneracy in a primal and dual simplex algorithm
• Survey of solved and open problems in the degeneracy phenomenon
• The Convex Simplex Method
• The TOMLAB OPERA toolbox for linear and discrete optimization
• The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
• The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling

Cited in

(11)

• Parametric linear programming and anti-cycling pivoting rules
• A note on cycling LP examples with permutation structure
• On Hoffman's celebrated cycling LP example
• scientific article; zbMATH DE number 4152143 (Why is no real title available?)
• Phase I cycling under the most-obtuse-angle pivot rule
• Constructing cycles in the simplex method for DPLL(T)
• A practical anti-cycling procedure for linearly constrained optimization
• Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules
• Visualizing and Constructing Cycles in the Simplex Method
• The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling
• On cycling in the simplex method of the transportation problem

Describes a project that uses

Uses Software

• TOMLAB
• OPERA

This page was built for publication: Systematic construction of examples for cycling in the simplex method

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