Lower Bounds for Simplex Pivot Rules via Markov Decision Processes

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.