Pivot rules for linear programming: A survey on recent theoretical developments

DOI10.1007/BF02096264zbMath0793.90034OpenAlexW1986414193WikidataQ54105206 ScholiaQ54105206MaRDI QIDQ1312760

Tamás Terlaky, Shu-Zhong Zhang

Publication date: 7 February 1994

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

surveyparametric programmingsimplex methodcyclingminimal index rulepivot rules

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

Numerical aspects in developing LP softwares, LPAKO and LPABO, A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs, A computationally stable solution algorithm for linear programs, The use of the optimal partition in a linear programming solution for postoptimal analysis, A regularized simplex method, Three nearly scaling-invariant versions of an exterior point algorithm for linear programming, Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems, Criss-cross methods: A fresh view on pivot algorithms, Limit laws for empirical optimal solutions in random linear programs, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, Implementing the simplex method as a cutting-plane method, with a view to regularization, The \(s\)-monotone index selection rules for pivot algorithms of linear programming, The Polyhedral Geometry of Pivot Rules and Monotone Paths, Revisiting degeneracy, strict feasibility, stability, in linear programming, Customizing the solution process of COIN-OR's linear solvers with python, Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks, A counterexample to the Hirsch conjecture, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, On the Use of Duality and Pricing Criteria in the Generalized‐simplex Method, A projective simplex algorithm using LU decomposition, Exterior point simplex-type algorithms for linear and network optimization problems, A simpler and tighter redundant Klee-Minty construction, Efficient nested pricing in the simplex algorithm, The double pivot simplex method, How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules, Stabilized dynamic constraint aggregation for solving set partitioning problems, Multi-phase dynamic constraint aggregation for set partitioning type problems, Dual–primal algorithm for linear optimization, The sagitta method for solving linear programs, An interesting characteristic of phase-1 of dual–primal algorithm for linear programming, Anstreicher–Terlaky type monotonic simplex algorithms for linear feasibility problems, Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm, Finiteness of the quadratic primal simplex method when \(\mathbf s\)-monotone index selection rules are applied, A new version of the improved primal simplex for degenerate linear programs, A redundant Klee-Minty construction with all the redundant constraints touching the feasible region, Steepest-edge rule and its number of simplex iterations for a nondegenerate LP, The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential, LPAKO: A Simplex-based Linear Programming Program, Computing monotone disjoint paths on polytopes, A triangulation and fill-reducing initialization procedure for the simplex algorithm, Combined projected gradient algorithm for linear programming, The central path visits all the vertices of the Klee–Minty cube, On the Length of Monotone Paths in Polyhedra, Pivot versus interior point methods: Pros and cons, Degeneracy in interior point methods for linear programming: A survey, An experimental investigation of a primal–dual exterior point simplexalgorithm, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, A new efficient primal dual simplex algorithm, New variants of finite criss-cross pivot algorithms for linear programming

Uses Software

• DEVEX
• OSL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The steepest descent gravitational method for linear programming
• Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids
• Practical finite pivoting rules for the simplex method
• The principal pivoting method revisited
• Linear quadratic programming in oriented matroids
• A new polynomial-time algorithm for linear programming
• A potential-reduction variant of Renegar's short-step path-following method for linear programming
• An infeasible (exterior point) simplex algorithm for assignment problems
• An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
• A finite crisscross method for oriented matroids
• The simplex method. A probabilistic analysis
• A finite conformal-elimination free algorithm over oriented matroid programming
• A note on the Edmonds-Fukuda pivoting rule for simplex algorithms
• A new algorithm for quadratic programming
• A dual approach to primal degeneracy
• On the solution of highly degenerate linear programmes
• Parametric linear programming and anti-cycling pivoting rules
• Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
• On the finiteness of the criss-cross method
• On anti-cycling pivoting rules for the simplex method
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Oriented matroids
• A combinatorial abstraction of linear programming
• The linear complementarity problem, sufficient matrices, and the criss- cross method
• A practical anti-cycling procedure for linearly constrained optimization
• An exterior point simplex algorithm for (general) linear programming problems
• Steepest-edge simplex algorithms for linear programming
• The gravitational method for linear programming
• The duoplex-algorithm
• The Criss-Cross Method for Solving Linear Programming Problems
• Complementarity in Oriented Matroids
• A convergent criss-cross method
• The d-Step Conjecture and Its Relatives
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A DUAL INTERIOR PRIMAL SIMPLEX METHOD FOR LINEAR PROGRAMMING METHOD
• Computational complexity of parametric linear programming
• Least-index resolution of degeneracy in quadratic programming
• The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods
• Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• On Finding Primal- and Dual-Optimal Bases
• Implementing the Simplex Method: The Initial Basis
• A Note on Convergence of the Ford-Fulkerson Flow Algorithm
• New Finite Pivoting Rules for the Simplex Method
• New purification algorithms for linear programming
• Implementing the simplex method for the Optimization Subroutine Library
• Some generalizations of the criss-cross method for quadratic programming
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Variants of the Hungarian method for solving linear programming problems
• The pivot and probe algorithm for solving a linear program
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
• Bimatrix Equilibrium Points and Mathematical Programming
• Pivot selection methods of the Devex LP code