Complexity of the simplex algorithm

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!

• Note that, as mashca said in an answer, we do not really have “the simplex algorithm.” There are many different simplex algorithms depending on the choice of a pivoting rule. Oct 22 '10 at 11:21
• 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. Feb 2 '11 at 20:40

The simplex algorithm indeed visits all $$2^n$$ vertices in the worst case (Klee & Minty 1972), 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 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 a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.

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 also showed the first non-polynomial lower bounds for some natural randomized pivot rules with some corrections provided later.

However, adding to the smoothed analysis result mentioned by Lev: Following Spielman and Tengs seminal paper introducing smoothed analysis, Vershynin improved 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}$$.

• and as JeffE pointed out in a different question (cstheory.stackexchange.com/questions/2149/…) the current best subexponential method is a kind of dual simplex. Oct 22 '10 at 17:34
• The link to the Vershynin paper is dead. Sep 17 '19 at 12: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.

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.

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.

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?

• Linear programming is in P. Even some interior-point methods (e.g. Karmarkar's algorithm) have poly-time bounds(en.wikipedia.org/wiki/Karmarkar%27s_algorithm) And of course the Ellipsoid method takes polynomial time. Jul 26 at 18:54
• 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$. Jul 26 at 20:41
• @neal Young they just have poly-time bounds on regular problems though? Have you looked into the article? Jul 27 at 9:02
• do you guys know a complexity comparison of different methods for solving LP by any chance? Jul 27 at 9:03