Criss-Cross Algorithm

The criss-cross algorithm is a family of algorithms for mathematical optimization that solves linear programming problems, along with related problems such as quadratic programming, linear-fractional programming and linear complementarity problems with linear inequality constraints. Unlike the simplex algorithm, which proceeds in two phases and maintains a feasible solution at every step, the criss-cross algorithm operates in a single phase and can pass through iterates that lie outside the feasible region before reaching an optimal solution; it selects its pivot variables by a purely combinatorial rule based on the signs of coefficients, rather than the numerical ordering rules such as Bland's rule used in simplex variants. The algorithm was published independently by Tamas Terlaky and by Zhe-Min Wang, building on earlier combinatorial optimization theory, with related unpublished approaches proposed by other researchers around the same time. Like the simplex algorithm, the criss-cross algorithm is not known to run in polynomial time in the worst case, since both can visit all corners of a Klee-Minty cube. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/