Criss-cross algorithm: Difference between revisions

Revision as of 12:04, 16 February 2021

Revision as of 12:08, 16 February 2021

Line 16:

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|date=May 1977|pages=103–107|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#Axiomatic approach|(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 name="Bland"/><ref>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]], according to {{harvtxt|Fukuda|Namiki|1994}}.</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"/> The criss-cross algorithm has been applied to furnish constructive proofs of basic results in [[real number|real]] [[linear algebra]], such as <!-- [[Steinitz's theorem|Steinitz's lemma]], --> the [[Farkas lemma|lemma of Farkas]]<!-- , [[Weyl's theorem]] on the finite generation of [[convex polytope]]s by linear inequalities ([[halfspace]]s), and the [[Krein–Milman theorem|Minkowski's theorem]] on [[extreme point]]s -->.<ref name="KT91" >{{harvtxt|Klafszky|Terlaky|1991}}</ref>

While most simplex variants are monotonic in the objective (strictly in the non-degenerate case), most variants of the criss-cross algorithm lack a monotone merit function which can be a disadvantage in practice.