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

Klee Minty cube in three variables with $\varepsilon =1/3$

The original Klee-Minty cube with $d$ variables and $2d$ inequality constraints is the following linear program, for any $\varepsilon \in (0,1/2)$:

${\begin{aligned}\operatorname {maximize} ~~&x_{d}\\\operatorname {subject~to} ~~~0\leq &x_{1}\leq 1\\\varepsilon x_{1}\leq &x_{2}\leq 1-\varepsilon x_{1}\\\varepsilon x_{2}\leq &x_{3}\leq 1-\varepsilon x_{2}\\&\vdots \\\varepsilon x_{d-1}\leq &x_{d}\leq 1-\varepsilon x_{d-1}.\end{aligned}}$

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

todo

• 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

External links

• www.example.com