49
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Oct 22, 2010 at 11:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – Rahul Savani
    Feb 2, 2011 at 20:40

6 Answers 6

Reset to default
81
$\begingroup$

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.

Improve this answer
$\endgroup$
37
$\begingroup$

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}$.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Oct 22, 2010 at 17:34
  • $\begingroup$ The link to the Vershynin paper is dead. $\endgroup$
    – kutschkem
    Sep 17, 2019 at 12:10
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-3
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jul 26, 2021 at 18:54
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jul 26, 2021 at 20:41
  • $\begingroup$ @neal Young they just have poly-time bounds on regular problems though? Have you looked into the article? $\endgroup$
    – learnPyt
    Jul 27, 2021 at 9:02
  • $\begingroup$ do you guys know a complexity comparison of different methods for solving LP by any chance? $\endgroup$
    – learnPyt
    Jul 27, 2021 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.