Klee–Minty cube

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.[2][3]

The Klee–Minty polytope is given by[4]

${\displaystyle {\begin{aligned}x_{1}\leq 5\\4x_{1}+x_{2}\leq 25\\8x_{1}+4x_{2}+x_{3}\leq 125\\\vdots \\2^{D}x_{1}+2^{D-1}x_{2}+\dots +4x_{D-1}+x_{D}\leq 5^{D}\\x_{1}\geq 0,\,\,\dots ,\,\,x_{D}\geq 0.\end{aligned}}}$

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

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

The Klee–Minty cube has been used to analyze the performance of many algorithms, both in the worst case and on average. The time complexity of an algorithm counts the number of arithmetic operations sufficient for the algorithm to solve the problem. For example, Gaussian elimination requires on the order of D³ operations, and so it is said to have polynomial time-complexity, because its complexity is bounded by a cubic polynomial. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called Buchberger's algorithm has for its complexity an exponential function of the problem data (the degree of the polynomials and the number of variables of the multivariate polynomials). Because exponential functions eventually grow much faster than polynomial functions, an exponential complexity implies that an algorithm has slow performance on large problems.

Worst case

An illustration of a three-dimensional polytope which is the feasible region for a linear programming problem. The simplex algorithm traverses the edges between vertices until it reaches an optimal vertex. In the case shown, the simplex algorithm takes five steps. However, the simplex algorithm visits every vertex in the worst case of a problem whose feasible region is the Klee–Minty cube, so the number of steps rises exponentially with the dimension of the problem.

In mathematical optimization, the Klee–Minty cube is an example that shows the worst-case computational complexity of many algorithms of linear optimization. It is a deformed cube with exactly  2^D corners in dimension D. Klee and Minty showed that Dantzig's simplex algorithm visits all corners of a (perturbed) cube in dimension D in the worst case.[1][5][6]

Modifications of the Klee–Minty construction showed similar exponential time complexity for other pivoting rules of simplex type, which maintain primal feasibility, such as Bland's rule.[7][8][9] Another modification showed that the criss-cross algorithm, which does not maintain primal feasibility, also visits all the corners of a modified Klee–Minty cube.[6][10][11] Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.

• Projective algorithm of Karmarkar
• Ellipsoidal algorithm of Khachiyan

• Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (May 2008). "How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds" (PDF). Mathematical Programming. 113 (1): 1–14. CiteSeerX 10.1.1.214.111. doi:10.1007/s10107-006-0044-x. MR 2367063. S2CID 156325.
• Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• Gartner, B.; Ziegler, G. M. (1994). "Randomized simplex algorithms on Klee-Minty cubes". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE. pp. 502–510. CiteSeerX 10.1.1.24.1405. doi:10.1109/SFCS.1994.365741. ISBN 978-0-8186-6580-6. S2CID 8090478.
• Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press. pp. 159–175. MR 0332165.
• Megiddo, Nimrod; Shub, Michael (February 1989). "Boundary Behavior of Interior Point Algorithms in Linear Programming". Mathematics of Operations Research. 14 (1): 97–146. CiteSeerX 10.1.1.80.184. doi:10.1287/moor.14.1.97. JSTOR 3689840. MR 0984561.
• Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547.
• Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46 (Degeneracy in optimization problems, number 1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.