A double-pivot simplex algorithm and its upper bounds of the iteration numbers

DOI10.1007/S40687-020-00235-2MaRDI QIDQ2214920zbMATH OpenOpenAlexFDO

Authors Ya-Guang Yang

Publication date 10 December 2020

Published in Research in the Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

double-pivot algorithmKlee-Minty cubelinear programmingsimplex method

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Abstract: In this paper, a double-pivot simplex method is proposed. Two upper bounds of iteration numbers are derived. Applying one of the bounds to some special linear programming (LP) problems, such as LP with a totally unimodular matrix and Markov Decision Problem (MDP) with a fixed discount rate, indicates that the double-pivot simplex method solves these problems in a strongly polynomial time. A variant of Klee-Minty cube is used to show that the estimated bounds of the iteration numbers are very tight. Numerical test on three variants of Klee-Minty cubes is performed for the problems with sizes as big as $200$ constraints and $400$ variables. Dantzig's simplex method cannot handle Klee-Minty cube problem with $200$ constraints because it needs about $2^{200}approx10^{60}$ iterations. But the proposed algorithm performs extremely good for all three variants.

Recommendations

• The double pivot simplex method
• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• On the number of solutions generated by the simplex method for LP
• A bound for the number of different basic solutions generated by the simplex method
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables

Cites work

• A bound for the number of different basic solutions generated by the simplex method
• A counterexample to the Hirsch conjecture
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• A randomized polynomial-time simplex algorithm for linear programming
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 1503621 (Why is no real title available?)
• Improving bounds on the diameter of a polyhedron in high dimensions
• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• Pivot rules for linear programming: A survey on recent theoretical developments
• Pivoting rules for the revised simplex algorithm
• Programming of Interdependent Activities: II Mathematical Model
• Randomized simplex algorithms on Klee-Minty cubes
• The double pivot simplex method
• The Hirsch conjecture has been disproved: an interview with Francisco Santos
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• Worst case behavior of the steepest edge simplex method

Cited in

(3)

• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• The double pivot simplex method

This page was built for publication: A double-pivot simplex algorithm and its upper bounds of the iteration numbers

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