In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems,[1][2] quadratic-programming problems, and linear complementarity problems.[3]
Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2D corners of a (perturbed) cube in dimension D, the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst case.[4][5] However, when it is started at a random corner, the criss-cross algorithm on average visits only D additional corners.[6][7][8] Thus, for the three-dimensional cube, the algorithm visits all 8 corners in the worst case and exactly 3 additional corners on average.
- ^ Illés, Szirmai & Terlaky (1999)
- ^ Stancu-Minasian, I. M. (August 2006). "A sixth bibliography of fractional programming". Optimization. 55 (4): 405–428. doi:10.1080/02331930600819613. MR 2258634. S2CID 62199788.
- ^ Fukuda & Terlaky (1997)
- ^ Roos (1990)
- ^ Cite error: The named reference
KleeMintywas invoked but never defined (see the help page). - ^ Cite error: The named reference
FTNamikiwas invoked but never defined (see the help page). - ^ Cite error: The named reference
FukudaNamikiwas invoked but never defined (see the help page). - ^ The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467.