Editing Linear programming (section)

=== Basis exchange algorithms ===

==== Simplex algorithm of Dantzig ====

The [[simplex algorithm]], developed by [[George Dantzig]] in 1947, solves LP problems by constructing a feasible solution at a vertex of the [[polytope]] and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure. In many practical problems, "[[Simplex algorithm#Degeneracy: stalling and cycling|stalling]]" occurs: many pivots are made with no increase in the objective function.<ref name="DT03">{{harvtxt|Dantzig|Thapa|2003}}</ref><ref name="Padberg">{{harvtxt|Padberg|1999}}</ref> In rare practical problems, the usual versions of the simplex algorithm may actually "cycle".<ref name="Padberg" /> To avoid cycles, researchers developed new pivoting rules.<ref name="FukudaTerlaky" />

In practice, the simplex [[algorithm]] is quite efficient and can be guaranteed to find the global optimum if certain precautions against ''cycling'' are taken. The simplex algorithm has been proved to solve "random" problems efficiently, i.e. in a cubic number of steps,<ref>{{harvtxt|Borgwardt|1987}}</ref> which is similar to its behavior on practical problems.<ref name="DT03" /><ref name="Todd">{{harvtxt|Todd|2002}}</ref>

However, the simplex algorithm has poor worst-case behavior: Klee and Minty constructed a family of linear programming problems for which the simplex method takes a number of steps exponential in the problem size.<ref name="DT03" /><ref name="Murty">{{harvtxt|Murty|1983}}</ref><ref name="PS">{{harvtxt|Papadimitriou|Steiglitz|}}</ref> In fact, for some time it was not known whether the linear programming problem was solvable in [[polynomial time]], i.e. of [[P (complexity)|complexity class P]].

==== Criss-cross algorithm ====
Like the simplex algorithm of Dantzig, the [[criss-cross algorithm]] is a basis-exchange algorithm that pivots between bases. However, the criss-cross algorithm need not maintain feasibility, but can pivot rather from a feasible basis to an infeasible basis. The criss-cross algorithm does not have [[time complexity|polynomial time-complexity]] for linear programming. Both algorithms visit all&nbsp;2<sup>''D''</sup> corners of a (perturbed) [[unit cube|cube]] in dimension&nbsp;''D'', the [[Klee–Minty cube]], in the [[worst-case complexity|worst case]].<ref name="FukudaTerlaky">{{cite journal|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor=Thomas M. Liebling |editor2=Dominique de Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|citeseerx=10.1.1.36.9373|s2cid=2794181}}</ref><ref name="Roos">{{cite journal|last=Roos|first=C.|title=An exponential example for Terlaky's pivoting rule for the criss-cross simplex method|journal=Mathematical Programming|volume=46|year=1990|series=Series A|doi=10.1007/BF01585729|mr=1045573 |issue=1|pages=79–84|s2cid=33463483}}</ref>