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!

  • 5
    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. – Tsuyoshi Ito Oct 22 '10 at 11:21
  • 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. – Rahul Savani 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^n$ vertices. 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.

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

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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