= Klee-Minty cube
{c}
{title2=$0\leq x_1\leq1,\quad\varepsilon x_{j-1}\leq x_j\leq1-\varepsilon x_{j-1}$}
{wiki=Klee–Minty_cube}
= Klee-Minty polytope
{c}
{synonym}
For $0<\varepsilon<1/2$, these inequalities define a deformed <cube> with $2^n$ <vertices of a polytope>. Choose either the lower or upper bound recursively at each coordinate to obtain a <vertex of a polytope>; changing one choice gives an adjacent <vertex of a polytope>. When maximizing $x_n$, smallest-index improving-facet pivoting visits all $2^n$ <vertices of a polytope>: first traverse the lower last-coordinate face, then move to the upper face and traverse the preceding path in reverse. Thus this geometric version of the <Bland pivoting rule> can require $2^n-1$ pivots. Rescaling the coordinate $x_i$ to $y_i=\varepsilon^{2(n-i)}x_i$ makes the positive rate per unit freed coordinate equal to $\varepsilon^{-(n-i)}$; <Dantzig pivot rule> then selects the same exponential path. Euclidean edge-length pricing is a different rule.
Back to article page
