Parametric linear programming and anti-cycling pivoting rules

DOI10.1007/BF01580770zbMath0653.90040OpenAlexW2081964341WikidataQ59592710 ScholiaQ59592710MaRDI QIDQ1108192

James B. Orlin, Thomas L. Magnanti

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1007/bf01580770

zbMATH Keywords

perturbation methoddegeneracycyclinganti-cycling ruledual pivoting procedure

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

A parametric programming methodology to solve the Lagrangian dual for network problems with multiple side-constraints, Applications of the parametric programming procedure, Systematic construction of examples for cycling in the simplex method, 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 comprehensive simplex-like algorithm for network optimization and perturbation analysis

Cites Work

• Unnamed Item
• Linear quadratic programming in oriented matroids
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• On the average number of steps of the simplex method of linear programming
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• The Average number of pivot steps required by the Simplex-Method is polynomial
• New Finite Pivoting Rules for the Simplex Method
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• A Technique for Resolving Degeneracy in Linear Programming
• Optimality and Degeneracy in Linear Programming