3.5 How fast is the simplex method?

In practice the number of pivots grows roughly linearly with the number of constraints, typically between \(m\) and \(3m\). In the worst case it does not. Klee and Minty (1972) constructed a distorted cube in \(\mathbb R^n\) on which Dantzig’s rule visits all \(2^n\) vertices, taking \(2^n - 1\) pivots (Software 3.6.3). Similar examples are known for every simple pivoting rule. Whether some pivoting rule is polynomial is still unknown. Spielman and Teng (2004) explained the good practical behaviour by smoothed analysis: after a small random perturbation of the data the expected number of pivots is polynomial. Linear programming itself is solvable in polynomial time, by Khachiyan’s ellipsoid method (1979) and by Karmarkar’s interior-point method (1984), whose descendants compete with the simplex method on large problems.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.