Klee–Minty cube

The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube".

On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case. In particular, many optimization algorithms for linear optimization exhibit poor performance when applied to the Klee–Minty cube. In 1973 Klee and Minty showed that Dantzig's simplex algorithm was not a polynomial-time algorithm when applied to their cube.

Later, modifications of the Klee–Minty cube have shown poor behavior both for other basis-exchange pivoting algorithms and also for interior-point algorithms. \begin{align} x_1 &\le 5 \\ 4x_1 + x_2 &\le 25 \\ 8x_1 + 4x_2 + x_3 &\le 125 \\ &\vdots \\ 2^Dx_1 + 2^{D-1}x_2 + \dots + 4x_{D-1} + x_D &\le 5^D \\ x_1 \ge 0, \, \, \dots , \, \, x_D &\ge 0. \end{align} This has D variables, D constraints other than the D non-negativity constraints, and 2^D vertices, just as a dimensional hypercube does. If the objective function to be maximized is 2^{D-1}x_1+2^{D-2}x_2+ \dots + 2x_{D-1}+x_D, and if the initial vertex for the simplex algorithm is the origin, then the algorithm as formulated by Dantzig visits all 2^D vertices, finally reaching the optimal vertex (0, 0, \dots, 5^D) . A picture of a Klee-Minty cube showing a simplex-algorithm path (automatic translation of German) by Günter Ziegler.

The picture in the second half of the page.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1301703533 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.