Criss-cross algorithm

In mathematical optimization, the criss-cross algorithm denotes 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] quadratic-programming problems, and linear complementarity problems.^[2]

Comparison with the simplex algorithm of Dantzig

See also: Linear programming, Simplex algorithm, and Bland's rule

In linear programming, the criss-cross algorithm pivots between a sequence of bases but differs from the simplex algorithm of George Dantzig. The simplex algorithm first finds a (primal-) feasible basis by solving a "phase-one problem"; in "phase two", the simplex algorithm pivots between a sequence of basic feasible solutions so that the objective function is non-decreasing with each pivot, terminating when with an optimal solution (also finally finding a "dual feasible" solution).^[2][3]

The criss-cross algorithm is simpler than the simplex algorithm, because the criss-cross algorithm only has one-phase. Its pivoting rules are similar to the least-index pivoting rule of Robert G. Bland. Bland's rule uses only signs of coefficients rather than their (real-number) order when deciding eligible pivots. Bland's rule selects an entering variables by comparing values of reduced costs, using the real-number ordering of the eligible pivots. Unlike Bland's rule, the criss-cross algorithm is "purely combinatorial", selecting an entering variable and a leaving variable by considering only the signs of coefficients rather than their real-number ordering.^[2][3]

Properties

See also: Oriented matroid

The criss-cross algorithm was published independently by Tamás Terlaky^[4] and by Zhe-Min Wang;^[5] related algorithms appeared in unpublished reports by other authors. Their publications considered linear-programming in the abstract setting of oriented matroids (OMs).^[6] Indeed, Bland's pivoting rule was based on his previous papers on oriented matroid theory. Much literature on the criss-cross algorithm concerns oriented matroids. Historically, OM algorithms for quadratic-programming problems and linear-complementarity problems had been published by Michael J. Todd before Terlaky and Wang published their criss-cross algorithms.^[7] However, Todd's pivoting-rule cycles on nonrealizable oriented matroids (and only on nonrealizable oriented matroids). Such cycling does not stump the OM criss-cross algorithms of Terlaky and Wang, however. There are oriented-matroid variants of the criss-cross algorithm for linear programming, for quadratic programming, and for the linear-complementarity problem.^[2][8]

Like the simplex algorithm of Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. The original criss-cross algorithm of Terlaky visits all the 2^D corners of a (perturbed) cube in dimension D, according to a paper of Roos (which modifies the Klee-Minty construction of a cube on which the simplex algorithm takes 2^D steps.^[2][9][10]

Summary

The criss-cross algorithm is a simply stated algorithm for linear programming. It was the second earliest fully combinatorial algorithm for linear programming; unlike the first algorithm for oriented matroids by Todd, the criss-cross algorithm does not cycle on nonrealizable oriented-oriented matroid problems. It is not a polynomial-time algorithm, however. Researchers have extended the criss-cross algorithm for many optimization-problems, including linear-fractional programming.^[1] The criss-cross algorithm can solve quadratic programming problems and linear complementarity problems in the setting of oriented matroids.

See also

• Jack Edmonds (pioneer of combinatorial optimization and oriented-matroid theorist; doctoral advisor of Komei Fukuda)

Notes

1. Illés, Szirmai & Terlaky (1999)
2. Fukuda & Terlaky (1997)
3. Terlaky & Zhang (1993)
4. Terlaky (1985) and Terlaky (1987)
5. Wang (1987) harvtxt error: no target: CITEREFWang1987 (help)
6. The theory of oriented matroids was initiated by R. Tyrrell Rockafellar to describe the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm; Rockafellar was inspired by Albert W. Tucker studies of such sign patterns in "Tucker tableaux". (Rockafellar 1969)
7. Template:Cite article
8. Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 9780521777506. MR 1744046. {{cite book}}: Cite has empty unknown parameter: |1= (help)
9. Roos (1990)
10. 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. {{cite book}}: Invalid |ref=harv (help)

References

• Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Cambridge University Press. doi:10.1017/CBO9780511586507. ISBN 9780521777506. MR 1744046. {{cite book}}: Invalid |ref=harv (help)
• Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite criss-cross method for hyperbolic programming". European Journal of Operational Research. 114 (1): 198–214. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217. {{cite journal}}: Invalid |ref=harv (help)
• Fukuda, Komei; Terlaky, Tamás (1997). "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). Amsterdam: North-Holland Publishing Co.: 369–395. doi:10.1016/S0025-5610(97)00062-2. MR 1464775. {{cite journal}}: Invalid |ref=harv (help); More than one of |number= and |issue= specified (help); Unknown parameter |editors= ignored (|editor= suggested) (help)
• Rockafellar, R. T. (1969). "The elementary vectors of a subspace of ${\displaystyle R^{N}}$  (1967)". In R. C. Bose and T. A. Dowling (ed.). Combinatorial Mathematics and its Applications (PDF). The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 0278972. {{cite book}}: Invalid |ref=harv (help)
• Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1). doi:10.1007/BF01585729. MR 1045573. {{cite journal}}: Invalid |ref=harv (help); Text "79–84" ignored (help)
• Terlaky, T. (1985). "A convergent criss-cross method". Optimization: A Journal of Mathematical Programming and Operations Research. 16 (5): 683--690. doi:10.1080/02331938508843067. ISSN 0233-1934. MR 0798939. {{cite journal}}: Invalid |ref=harv (help)
• Terlaky, Tamás (1987). "A finite crisscross method for oriented matroids". Journal of Combinatorial Theory. Series B. 42 (3): 319–327. doi:10.1016/0095-8956(87)90049-9. ISSN 0095-8956. MR 0888684. {{cite journal}}: Invalid |ref=harv (help)
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems). Springer Netherlands: 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. PDF file of (1991) preprint. {{cite journal}}: Cite has empty unknown parameter: |1= (help); Invalid |ref=harv (help); More than one of |number= and |issue= specified (help)
• Wang, Zhe Min. "A finite conformal-elimination free algorithm over oriented matroid programming". Chinese Annals of Mathematics (Shuxue Niankan B Ji). Series B. 8 (1): 120–125. ISSN 0252-9599. MR 0886756. {{cite journal}}: Invalid |ref=harv (help); Text "year1987" ignored (help)