Lower Bounds for Simplex Pivot Rules via Markov Decision Processes

Nils Mosis ()
Additional contact information
Nils Mosis: TU Darmstadt

Chapter Chapter 41 in Operations Research Proceedings 2023, 2025, pp 317-323 from Springer

Abstract: Abstract It is a major open problem in the fields of operations research and linear optimization whether there is an efficient pivot rule for Dantzig’s simplex algorithm. We show that it is not possible to obtain the desired strongly polynomial running time with a pivot rule that is a combination of Bland’s pivot rule, Dantzig’s pivot rule, and the Largest Increase rule—three of the most classical simplex pivot rules. The proof is based on a close relation to the policy iteration algorithm for Markov decision processes. More precisely, we construct a family of Markov decision processes for which policy iteration performs the same exponential sequence of improving switches when applied with any of the three pivot rules. This behavior yields that the worst-case running time of the algorithm is exponential for every combination of the considered rules. Then, due to the connection between both algorithms, we obtain the same exponential lower bound result for the simplex method. Typically, the policy iteration algorithm applies multiple switches simultaneously, and our lower bounds for Dantzig’s rule and the Largest Increase rule, where we assume that policy iteration only performs single switches, seem novel. The individual lower bounds for the simplex algorithm were previously proven separately via deformed hypercube constructions.

Keywords: Bland’s pivot rule; Dantzig’s pivot rule; Largest increase rule; Linear programming; Markov decision process; Policy iteration; Simplex algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-58405-3_41

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_41

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().