User:Shuiberts/sandbox/Klee-Minty cube

In computer science, Klee-Minty cubes (named after Victor Klee and George J. Minty) are geometric constructions used to prove lower bounds on the worst-case complexity of the simplex method. The original such cube was introduced by Klee and Minty specifically for Dantzig's original simplex method, which is based on the most-negative reduced cost rule. Similar constructions have been found for other pivot rules (see Simplex method § Entering variable selection) as well.

For a given pivot rule and a given number of variables, the applicable Klee-Minty cube is a linear program, whose feasible set is a `squashed' hypercube. On this linear program, the simplex method with the given pivot rule will visit an exponentially large number of vertices. Such an input thus shows that the pivot rule does not lead to a polynomial-time algorithm.

Description of the cube

edit
 
Klee Minty cube in three variables with  

The original Klee-Minty cube with   variables and   inequality constraints is the following linear program, for any  :

 

Starting from the all-zero vector, which is feasible, the least negative reduced cost rule visits all   vertices of the feasible set before reaching the optimal vertex.

todo

edit
  • references for all interesting pivot rules (bland, shadow vertex, steepest edge, greatest improvement) and amenta-ziegler
  • recent trends in simplex lower bounds (history dependent, randomized, no longer cubes)
  • klee minty cubes drove lots of research into average case analysis and prompted the introduction of smoothed analysis

References

edit
edit