Klee–Minty cube

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".

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.

The Klee–Minty cube was originally specified with a parameterized system of linear inequalities, with the dimension as the parameter. When the dimension is two, the "cube" is a squashed square. When the dimension is three, the "cube" is a squashed cube. Illustrations of the "cube" have appeared besides algebraic descriptions.

The Klee–Minty polytope is given by

This has D variables, D constraints other than the D non-negativity constraints, and 2^D vertices, just as a D-dimensional hypercube does. If the objective function to be maximized is

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 ${\displaystyle (0,0,\dots ,5^{D}).}$

...
Wikipedia