Criss-cross algorithm: Difference between revisions

Revision as of 22:31, 25 March 2011

Revision as of 22:33, 25 March 2011

Line 14:

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).<ref name="FukudaTerlaky"/><ref name="TerlakyZhang">{{harvtxt|Terlaky|Zhang|1993}}</ref>

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 [[Bland's rule|least-index pivoting rule of Bland]].<ref name="Bland">

{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|number=2|month=May|year=1977|pages=103–107|urlhttpurl=http://www.jstor.org/stable/3689647|doi=10.1287/moor.2.2.103|jstor=3689647|MR=459599}}</ref> Bland's rule uses only [[sign function|sign]]s of coefficients rather than their [[real number|(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.<ref>R.G. Bland, New finite pivoting rules for the simplex method, ''Math. Oper. Res.'' 2 (1977) 103–107.<p>Bland's rule is also related to an earlier least-index rule, which was proposed by Katta&nbsp;G. Murty for the [[linear complementarity problem]].</ref> 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.<ref name="FukudaTerlaky"/><ref name="TerlakyZhang"/>

==Computational complexity: Worst and average cases==