Criss-cross algorithm: Difference between revisions

Revision as of 00:18, 29 December 2023

Latest revision as of 17:42, 23 June 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Method for mathematical optimization}}

{{About|an algorithm for mathematical optimization||Criss-cross (disambiguation){{!}}Criss-cross}}

{{Use dmy dates|date=DecemberJanuary 20132024}}

<!-- {{Context|date=May 2012}} -->

[[File:Unitcube.svg|thumb|right|alt=A three-dimensional cube|The criss-cross algorithm visits all&nbsp;8 corners of the [[Klee–Minty cube]] in the worst case. It visits&nbsp;3 additional corners on&nbsp;average. The Klee–Minty cube is a perturbation of the cube shown here.]]

Line 17:

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 [[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.

==Description==

{{Expand section|date=April 2011}}

The criss-cross algorithm works on a standard pivot tableau (or on-the-fly calculated parts of a tableau, if implemented like the revised simplex method). In a general step, if the tableau is primal or dual infeasible, it selects one of the infeasible rows / columns as the pivot row / column using an index selection rule. An important property is that the selection is made on the union of the infeasible indices and the standard version of the algorithm does not distinguish column and row indices (that is, the column indices basic in the rows). If a row is selected then the algorithm uses the index selection rule to identify a position to a dual type pivot, while if a column is selected then it uses the index selection rule to find a row position and carries out a primal type pivot.

Line 38 ⟶ 37:

===Other optimization problems with linear constraints===

There are variants of the criss-cross algorithm for linear programming, for [[quadratic programming]], and for the [[linear complementarity problem|linear-complementarity problem]] with "sufficient matrices";<ref name="FukudaTerlaky"/><ref name="FTNamiki"/><ref name="FukudaNamikiLCP" >{{harvtxt|Fukuda|Namiki|1994|}}</ref><ref name="OMBook" >{{cite book|last1=Björner|first1=Anders|last2=Las Vergnas|first2=Michel|author2-link=Michel Las Vergnas|last3=Sturmfels|first3=Bernd|author-link3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|author-link5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=978-0-521-77750-6|pages=417–479|doi=10.1017/CBO9780511586507|mr=1744046}}</ref><ref name="HRT">{{cite journal|first1=D. |last1=den Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and Its Applications|volume=187|date=1 July 1993|pages=1–14|url=httphttps://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|doi-access=free}}</ref><ref name="CIsufficient">{{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf<!--|eprint=http://www.tandfonline.com/doi/pdf/10.1080/10556780500095009-->|mr=2195759|s2cid=24418835|access-date=30 August 2011|archive-date=23 September 2015|archive-url=https://web.archive.org/web/20150923211403/http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|url-status=dead}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> A [[sufficient&nbsp;matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal&nbsp;minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journal|last1=Cottle|first1=R. W.|author-link1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear complementarity problem|journal=Linear Algebra and Its Applications|volume=114–115|date=March–April 1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|mr=986877|doi-access=free}}</ref> The criss-cross algorithm has been adapted also for [[linear-fractional programming]].<ref name="LF99Hyperbolic"/><ref name="Bibl"/>

===Vertex enumeration===

Line 73 ⟶ 72:

==Notes==

{{Reflist}}

<references/>

==References==

Line 80 ⟶ 79:

* {{cite journal|last1=Fukuda|first1=Komei|author-link1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|date=March 1994|pages=365–370|volume=64|number=1|doi=10.1007/BF01582581|mr=1286455|s2cid=21476636}}

* {{cite journal|first1=Komei|last1=Fukuda| author-link1=Komei Fukuda |first2=Tamás|last2=Terlaky| author-link2=Tamás Terlaky |title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|pages=369–395|issue=Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3 |editor1-first=Thomas M.|editor1-last=Liebling|editor2-first=Dominique|editor2-last=de Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|citeseerx=10.1.1.36.9373|s2cid=2794181}}

* {{cite journal|first1=D.|last1=den Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and Its Applications|volume=187|date=1 July 1993|pages=1–14|url=httphttps://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|mr=1221693|doi-access=free}}

* {{<!-- citation -->cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|number=1|

pages=198–214|year=1999<!-- |issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a