page_title: Klee–Minty cube
hierarchical_section_title: Klee–Minty cube
caption_attribution_description: English: Illustration of 3-dimensional worst-case instance for the shadow vertex simplex method with six facets. Due to Murty (1980) and Goldfarb (1983, 1994). Description for this object was taken from Amenta and Ziegler (1996) with epsilon = 1/3 and epsilon*gamma = 1/16. The object is a deformed cube and its projection onto a two-dimensional plane has 8 vertices. Rendered using Blender with Freestyle option turned on, from a wavefront (.obj) file calculated from the given inequalities.
context_page_description: The Klee–Minty cube or Klee–Minty polytope 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.
context_section_description: 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 .
caption: Klee Minty cube for shadow vertex simplex method.
exif: {}