<p>The simplex algorithm indeed visits all <span class="math-container">$2^n$</span> vertices in the worst case (<a href="https://ci.nii.ac.jp/naid/10020194052/" rel="noreferrer">Klee &amp; Minty 1972</a>), and this turns out to be true for any deterministic pivot rule. However, in a landmark paper using a smoothed analysis, Spielman and Teng (2001) <a href="http://arxiv.org/abs/cs.DS/0111050" rel="noreferrer">proved</a> that when the inputs to the algorithm are slightly randomly perturbed, the expected running time of the simplex algorithm is polynomial for any inputs -- this basically says that for any problem there is a "nearby" one that the simplex method will efficiently solve, and it pretty much covers every real-world linear program you'd like to solve.  Afterwards, Kelner and Spielman (2006) <a href="http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf" rel="noreferrer">introduced</a> a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.</p>

CC BY-SA 4.0
2010-10-22T03:20:42.477Z
2019-09-21T18:18:37.247Z
2019-09-21T18:18:37.247Z
Lev Reyzin
<p>As Lev said, in the worst case the algorithm visits all <span class="math-container">$2^d$</span> vertices where <span class="math-container">$d$</span> is number of variables. However, the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. As far as I am aware, it is still an open question if there exists a specific deterministic pivot rule with sub-exponential worst-case running time. Many candidates have been ruled out by lower bound results. Recently, <a href="https://epubs.siam.org/doi/abs/10.1137/1.9781611973082.19" rel="nofollow noreferrer">Friedmann, Hansen, and Zwick</a> also showed the first non-polynomial lower bounds for some natural randomized pivot rules with some corrections provided <a href="https://arxiv.org/pdf/1410.7871.pdf" rel="nofollow noreferrer">later</a>.</p>

<p>However, adding to the smoothed analysis result mentioned by Lev: Following Spielman and Tengs seminal paper introducing smoothed analysis, Vershynin <a href="https://www.math.uci.edu/~rvershyn/papers/simplex-journal.pdf" rel="nofollow noreferrer">improved</a> their bounds further in 2006. He showed that the expected running time on slightly perturbed instances is only poly-logarithmic in the number of constraints <span class="math-container">$n$</span>, down from <span class="math-container">$n^{86}$</span>.</p>

CC BY-SA 4.0
2019-09-17T12:10:40.733Z
The link to the Vershynin paper is dead.
kutschkem
CC BY-SA 2.5
2010-10-22T17:34:54.750Z
and as JeffE pointed out in a different question (http://cstheory.stackexchange.com/questions/2149/consequences-of-existence-of-a-strongly-polynomial-algorithm-for-linear-programmi) the current best subexponential method is a kind of dual simplex.
Suresh Venkat
CC BY-SA 4.0
2010-10-22T10:06:18.413Z
2019-09-21T18:18:21.420Z
2019-09-21T18:18:21.420Z
Matthias
<p>To obtain insight into the worst-case and average-case analysis of the simplex method, you should read "Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time." by Spielman and Teng.  </p>

CC BY-SA 2.5
2010-11-14T22:00:53.877Z
2010-11-14T22:00:53.877Z
Christina Boucher
<p>A good reference on why simplex is not running in polynomial time, rather than why it's exponential is Papadimitriou &amp; Steiglitz Combinatorial Optimization, Section 8.6 in which they demonstrate that Simplex is not a polynomial-time algorithm.</p>

CC BY-SA 2.5
2010-11-18T06:41:43.777Z
2010-11-18T06:41:43.777Z
hyperboreean
<p>In 2019, the opensource LP solver <a href="https://www.gnu.org/software/glpk/" rel="nofollow noreferrer">GLPK</a> 
does the
<a href="https://en.wikipedia.org/wiki/Klee-Minty_cube" rel="nofollow noreferrer">Klee-Minty cube</a>
problem with <span class="math-container">$D=200$</span>
in under 100 milliseconds, on a 2.7 GHz iMac:</p>

<pre><code>GLPK Simplex Optimizer, v4.65
200 rows, 200 columns, 20100 non-zeros
Preprocessing...
199 rows, 200 columns, 20099 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.607e+60  ratio =  1.607e+60
...
Constructing initial basis...
Size of triangular part is 199
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (200)
*     1: obj = -6.223015278e+139 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 3.4 Mb
</code></pre>

<p>Can anyone suggest other ways to construct difficult problems for the simplex method,
slow but not memory-bound ? </p>

<p>Added: Latin squares aka <a href="https://math.stackexchange.com/questions/3370934/3d-permutation-matrices">3d-permutation-matrices</a> seem to have many vertices -- how many ?<br>
<sub>Theory and practice are closer in theory than they are in practice.</sub> </p>

CC BY-SA 4.0
2019-09-17T10:30:49.630Z
2019-09-28T10:27:53.460Z
2019-09-28T10:27:53.460Z
Denis
<p>it might be a bit off-topic but even the interior-point methods do have an exponential worst-case complexity as proven in the following paper:
<a href="https://link.springer.com/article/10.1007/s10107-006-0044-x#citeas" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s10107-006-0044-x#citeas</a></p>
<p>so basically Linear Programming has an exponential worst-case complexity or am I getting this wrong?</p>

CC BY-SA 4.0
2021-07-26T18:54:14.190Z
Linear programming is in P.  Even some interior-point methods (e.g. Karmarkar's algorithm) have poly-time bounds(https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm)  And of course the Ellipsoid method takes polynomial time.
Neal Young
CC BY-SA 4.0
2021-07-26T20:41:38.207Z
Yes, you are wrong. The running time is to be measured as a function of the (bit)length of the input. Here both are exponential in the parameter $n$.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-07-27T09:02:44.060Z
@neal Young they just have poly-time bounds on regular problems though? Have you looked into the article?
learnPyt
CC BY-SA 4.0
2021-07-27T09:03:58.377Z
do you guys know a complexity comparison of different methods for solving LP by any chance?
learnPyt
CC BY-SA 4.0
2021-07-26T17:18:07.907Z
2021-07-26T17:18:07.907Z
learnPyt
<p>What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?</p>

<p>How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in practice the simplex algorithm will run significantly faster than this for more standard problems.</p>

<p>How can I reason about the average complexity of a problem being solved using this method?</p>

<p>Any information or references are greatly appreciated!</p>

CC BY-SA 2.5
2011-02-02T20:40:02.163Z
A cube in dimension $n$ has $2^n$ vertices, and so this if an upper bound for any simplex variant on (e.g., Klee-Minty) cubes. However, there are polyhedra in dimension $n$ with $2n$ facets, such as dual cyclic polytopes, with more than $2^n$ vertices, so $2^n$ is not an immediate upper bound of for the running time of the simplex method for square constraint matrices in general.
Rahul Savani
CC BY-SA 2.5
2010-10-22T11:21:32.890Z
Note that, as mashca said in an [answer](http://cstheory.stackexchange.com/questions/2373/complexity-of-simplex-algorithm/2377#2377), we do not really have “the simplex algorithm.”  There are many different simplex algorithms depending on the choice of a pivoting rule.
Tsuyoshi Ito
<ds.algorithms><linear-programming><simplex><smoothed-analysis>
Complexity of the simplex algorithm
shuttle87
# Complexity of the simplex algorithm

(Asked by: username_0 on 2010-10-22)

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?

How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in practice the simplex algorithm will run significantly faster than this for more standard problems.

How can I reason about the average complexity of a problem being solved using this method?

Any information or references are greatly appreciated!

**Tags:** ds.algorithms, linear-programming, simplex, smoothed-analysis
> **Comments:**
> **username_2**: Note that, as mashca said in an [answer](http://cstheory.stackexchange.com/questions/2373/complexity-of-simplex-algorithm/2377#2377), we do not really have “the simplex algorithm.”  There are many different simplex algorithms depending on the choice of a pivoting rule.  
> **username_1**: A cube in dimension $n$ has $2^n$ vertices, and so this if an upper bound for any simplex variant on (e.g., Klee-Minty) cubes. However, there are polyhedra in dimension $n$ with $2n$ facets, such as dual cyclic polytopes, with more than $2^n$ vertices, so $2^n$ is not an immediate upper bound of for the running time of the simplex method for square constraint matrices in general.  

---

## 6 answers

### Answer by username_3 on 2010-10-22. Score: 85

The simplex algorithm indeed visits all $2^n$ vertices in the worst case ([Klee & Minty 1972](https://ci.nii.ac.jp/naid/10020194052/)), and this turns out to be true for any deterministic pivot rule. However, in a landmark paper using a smoothed analysis, Spielman and Teng (2001) [proved](http://arxiv.org/abs/cs.DS/0111050) that when the inputs to the algorithm are slightly randomly perturbed, the expected running time of the simplex algorithm is polynomial for any inputs -- this basically says that for any problem there is a "nearby" one that the simplex method will efficiently solve, and it pretty much covers every real-world linear program you'd like to solve. Afterwards, Kelner and Spielman (2006) [introduced](http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf) a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.


---

### Answer by username_4 on 2010-10-22. Score: 39

As Lev said, in the worst case the algorithm visits all $2^d$ vertices where $d$ is number of variables. However, the performance of the simplex algorithm may also greatly depend on the specific pivot rule used. As far as I am aware, it is still an open question if there exists a specific deterministic pivot rule with sub-exponential worst-case running time. Many candidates have been ruled out by lower bound results. Recently, [Friedmann, Hansen, and Zwick](https://epubs.siam.org/doi/abs/10.1137/1.9781611973082.19) also showed the first non-polynomial lower bounds for some natural randomized pivot rules with some corrections provided [later](https://arxiv.org/pdf/1410.7871.pdf).

However, adding to the smoothed analysis result mentioned by Lev: Following Spielman and Tengs seminal paper introducing smoothed analysis, Vershynin [improved](https://www.math.uci.edu/~rvershyn/papers/simplex-journal.pdf) their bounds further in 2006. He showed that the expected running time on slightly perturbed instances is only poly-logarithmic in the number of constraints $n$, down from $n^{86}$.

> **Comments:**
> **username_6**: and as JeffE pointed out in a different question (http://cstheory.stackexchange.com/questions/2149/consequences-of-existence-of-a-strongly-polynomial-algorithm-for-linear-programmi) the current best subexponential method is a kind of dual simplex.  
> **username_5**: The link to the Vershynin paper is dead.  

---

### Answer by username_7 on 2010-11-14. Score: 10

To obtain insight into the worst-case and average-case analysis of the simplex method, you should read "Smoothed Analysis: Why The Simplex Algorithm Usually Takes Polynomial Time." by Spielman and Teng.


---

### Answer by username_8 on 2010-11-18. Score: 4

A good reference on why simplex is not running in polynomial time, rather than why it's exponential is Papadimitriou & Steiglitz Combinatorial Optimization, Section 8.6 in which they demonstrate that Simplex is not a polynomial-time algorithm.


---

### Answer by username_9 on 2019-09-17. Score: 0

In 2019, the opensource LP solver GLPK 
does the
Klee-Minty cube
problem with $D=200$
in under 100 milliseconds, on a 2.7 GHz iMac:
GLPK Simplex Optimizer, v4.65
200 rows, 200 columns, 20100 non-zeros
Preprocessing...
199 rows, 200 columns, 20099 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.607e+60  ratio =  1.607e+60
...
Constructing initial basis...
Size of triangular part is 199
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (200)
*     1: obj = -6.223015278e+139 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 3.4 Mb

Can anyone suggest other ways to construct difficult problems for the simplex method,
slow but not memory-bound ? 
Added: Latin squares aka 3d-permutation-matrices seem to have many vertices -- how many ?
Theory and practice are closer in theory than they are in practice.


---

### Answer by username_10 on 2021-07-26. Score: -3

it might be a bit off-topic but even the interior-point methods do have an exponential worst-case complexity as proven in the following paper:
<https://link.springer.com/article/10.1007/s10107-006-0044-x#citeas>

so basically Linear Programming has an exponential worst-case complexity or am I getting this wrong?

> **Comments:**
> **username_11**: Linear programming is in P.  Even some interior-point methods (e.g. Karmarkar's algorithm) have poly-time bounds(https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm)  And of course the Ellipsoid method takes polynomial time.  
> **username_12**: Yes, you are wrong. The running time is to be measured as a function of the (bit)length of the input. Here both are exponential in the parameter $n$.  
> **username_10**: @neal Young they just have poly-time bounds on regular problems though? Have you looked into the article?  
> **username_10**: do you guys know a complexity comparison of different methods for solving LP by any chance?  

---

