---
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} \approx 10^{60}$ iterations. But the proposed algorithm performs extremely good for all three variants.'
author:
- 'Yaguang Yang[^1]'
title: 'A double-pivot simplex algorithm and its upper bounds of the iteration numbers'
---

[**Keywords:**]{} Double-pivot algorithm, simplex method, linear programming.

Introduction
============

Since Dantzig invented the simplex method in 1940s [@dantzig49], its complexity has been a topic attracted many researchers. Since simplex methods search the optimizer among vertices which are defined by the linear constraints, the iterate moves from 