Parametric linear programming and anti-cycling pivoting rules
It is well-known that in the presence of degeneracy in linear programming the simplex procedure may select a sequence of admissible bases that cycles. The perturbation method avoids cycling by refining the selection rule for the exiting variable while the combinatorial rule avoids cycling by refining the selection rule for both the exiting and entering variables. This raises the following question answered affirmatively by the authors. Is there a simplex pivoting procedure for avoiding cycling that does not restrict the minimum ratio rule choice of exiting variables? In this paper the authors describe an anti-cycling rule that avoids cycling by refining the selection rule for only the entering variable. The authors have also described a dual pivoting procedure that avoids cycling by refining only the choice of exiting variables.
- A practical anti-cycling procedure for linearly constrained optimization
- Systematic construction of examples for cycling in the simplex method
- scientific article; zbMATH DE number 3904322
- A new revised simplex method for degenerate linear programs
- Making progress during a stall in the simplex algorithm
- A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
- A Technique for Resolving Degeneracy in Linear Programming
- scientific article; zbMATH DE number 3069632 (Why is no real title available?)
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- Linear quadratic programming in oriented matroids
- New Finite Pivoting Rules for the Simplex Method
- On the average number of steps of the simplex method of linear programming
- Optimality and Degeneracy in Linear Programming
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- The Average number of pivot steps required by the Simplex-Method is polynomial
- Applications of the parametric programming procedure
- A practical anti-cycling procedure for linearly constrained optimization
- A constrained nonlinear 0-1 program for data allocation
- Selected bibliography on degeneracy
- Degeneracy graphs: Theory and applications. An updated survey
- Pivot rules for linear programming: A survey on recent theoretical developments
- Encounters with degeneracy: A personal view
- A practical anti-degeneracy row selection technique in network linear programming
- Cycling in linear programming problems
- Resolving degeneracy in combinatorial linear programs: Steepest edge, steepest ascent, and parametric ascent
- Geometry of the Gass-Saaty parametric cost LP algorithm
- A parametric programming methodology to solve the Lagrangian dual for network problems with multiple side-constraints
- Systematic construction of examples for cycling in the simplex method
- A combinatorial program using the simplex method.
- Anti-stalling Pivot Rule for Linear Programs with Totally Unimodular Coefficient Matrix
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- scientific article; zbMATH DE number 803005 (Why is no real title available?)
- Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules
This page was built for publication: Parametric linear programming and anti-cycling pivoting rules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108192)
