Criss-cross algorithm: Difference between revisions

Revision as of 05:22, 4 August 2011

Revision as of 19:02, 21 August 2011

Line 15:

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|url=http://www.jstor.org/stable/3689647|doi=10.1287/moor.2.2.103|jstor=3689647|MRmr=459599|ref=harv}}</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>

==Description==

Line 41:

===Vertex enumeration===

The criss-cross algorithm was used in an an algorithm for [[Vertex enumeration problem|enumerating all the vertices of a polytope]], which was published by [[David Avis]] and Komei Fukuda in&nbsp;1992.<ref>{{harvtxt|Avis|Fukuda|1992|p=297}}</ref> Avis and Fukuda presented an algorithm which finds the&nbsp;''v'' vertices of a [[polyhedron]] defined by a nondegenerate system of&nbsp;''n'' [[linear inequality|linear inequalities]] in&nbsp;''D'' [[dimension (vector space)|dimension]]s (or, dually, the&nbsp;''v'' [[facet]]s of the [[convex hull]] of&nbsp;''n'' points in&nbsp;''D'' dimensions, where each facet contains exactly&nbsp;''D'' given points) in time&nbsp;[[Big Oh notation|O]](''nDv'') and&nbsp;O(''nD'') [[space complexity|space]].<ref>The&nbsp;''v'' vertices in a simple arrangement of&nbsp;''n'' [[hyperplane]]s in&nbsp;''D'' dimensions can be found in&nbsp;O(''n''²''Dv'') time and O(''nD'') [[space complexity]].</ref>

===Oriented matroids===

Line 60:

|mr=278972

|url=http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf|ref=harv|id=[http://www.math.washington.edu/~rtr/papers/rtr-ElemVectors.pdf PDF reprint]}}</p><p>Rockafellar was influenced by the earlier studies of [[Albert W. Tucker]] and [[George J. Minty]]. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.</p>

</ref> Indeed, Bland's pivoting rule was based on his previous papers on oriented-matroid theory. However, Bland's rule exhibits cycling on some oriented-matroid linear-programming problems.<ref name="OMBook"/> The first purely combinatorial algorithm for linear programming was devised by [[Michael J. Todd (mathematician)|Michael&nbsp;J. Todd]].<ref name="OMBook"/><ref name="Todd"/> Todd's algorithm was developed not only for linear-programming in the setting of oriented matroids, but also for [[quadratic programming|quadratic-programming problems]] and [[linear complementarity problem|linear-complementarity problem]]s.<ref name="OMBook"/><ref name="Todd" >{{cite journal|last=Todd|first=Michael&nbsp;J.|authorlink=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series&nbsp;B|volume=39|year=1985|number=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5|url=http://dx.doi.org/10.1016/0095-8956(85)90042-5|ref=harv}}</ref> Todd's algorithm is complicated even to state, unfortunately, and its finite-convergence proofs are somewhat complicated.<ref name="OMBook"/>

The criss-cross algorithm and its proof of finite termination can be simply stated and readily extend the setting of oriented matroids. The algorithm can be further simplified for ''linear feasibility problems'', that is for [[linear system]]s with [[linear inequality|nonnegative variable]]s; these problems can be formulated for oriented matroids.<ref name="KT91"/> The criss-cross algorithm has been adapted for problems that are more complicated than linear programming: There are oriented-matroid variants also for the quadratic-programming problem and for the linear-complementarity problem.<ref name="FukudaTerlaky"/><ref name="FukudaNamikiLCP"/><ref name="OMBook"/>

Line 78:

* {{cite journal|url=http://www.springerlink.com/content/m7440v7p3440757u/|first1=David|last1=Avis|first2=Komei|last2=Fukuda|authorlink2=Komei Fukuda|authorlink1=David Avis|title=A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra|journal=[[Discrete and Computational Geometry]]|volume=8|number=1|month=December|year=1992|pages=295–313

|doi=10.1007/BF02293050|issue=ACM Symposium on Computational Geometry (North Conway, NH, 1991)|mr=1174359|ref=harv}}

* {{cite journal|last1=Fukuda|first1=Komei|authorlink1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|year=1994|month=March|pages=365–370|volume=64|number=1|url=http://dx.doi.org/10.1007/BF01582581|doi=10.1007/BF01582581|ref=harv|MRmr=1286455}}

* {{cite journal|first1=Komei|last1=Fukuda|<!-- authorlink1=Komei Fukuda -->|first2=Tamás|last2=Terlaky|<!-- authorlink2=Tamás Terlaky -->|title=Criss-cross methods: A fresh view on pivot algorithms |url=http://dx.doi.org/=10.1007/BF02614325|journal=Mathematical Programming: Series&nbsp;B|volume=79|number=1–3|pages=369–395|issue=Papers from the&nbsp;16th International Symposium on Mathematical Programming held in Lausanne,&nbsp;1997|editor1-first=Thomas&nbsp;M.|editor1-last=Liebling|editor2-first=Dominique|editor2-last=de&nbsp;Werra|publisher=North-Holland Publishing&nbsp;Co.|___location=Amsterdam|year=1997|doi=10.1016/S0025-5610(97)00062-2|mr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}

* {{<!-- 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

|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|ref=harv}}

*{{cite journal|first1=Emil|last1=Klafszky|first2=Tamás|last2=Terlaky|title=The role of pivoting in proving some fundamental theorems of linear algebra|journal=Linear Algebra and its Applications|volume=151|month=June|year=1991|pages=97–118|doi=10.1016/0024-3795(91)90356-2|url2=http://www.sciencedirect.com/science/article/pii/0024379591903562|url=http://www.cas.mcmaster.ca/~terlaky/files/pivot-la.ps|type=postscript|ref=harv|mr=1102142}}

* {{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|number=1|series=Series&nbsp;A|79–84|doi=10.1007/BF01585729|url=http://dx.doi.org/10.1007/BF01585729|MRmr=1045573|ref=harv|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=T.|title=A convergent criss-cross method|journal=Optimization: A Journal of Mathematical Programming and Operations Research|volume=16|year=1985|number=5|pages=683–690|issn=0233-1934|doi=10.1080/02331938508843067|url=http://dx.doi.org/10.1080/02331938508843067|ref=harv|MRmr=798939|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last=Terlaky|first=Tamás|authorlink=Tamás Terlaky|title=A finite crisscross method for oriented matroids|volume=42|year=1987|number=3|pages=319–327|journal=Journal of Combinatorial Theory|series=Series&nbsp;B|issn=0095-8956|doi=10.1016/0095-8956(87)90049-9|url=http://dx.doi.org/10.1016/0095-8956(87)90049-9|MRmr=888684|ref=harv|<!-- Google scholar reported no free versions -->}}

* {{cite journal|last1=Terlaky|first1=Tamás|<!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu&nbsp;Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems|journal=Annals of Operations Research|volume=46–47|year=1993|number=1|pages=203–233|doi=10.1007/BF02096264|url=http://dx.doi.org/10.1007/BF02096264|MRmr=1260019|id=[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.7658&rep=rep1&type=pdf PDF file of (1991) preprint]|publisher=Springer Netherlands|issn=0254-5330|ref=harv}}

* {{cite journal|last=Wang|first=Zhe&nbsp;Min|title=A finite conformal-elimination free algorithm over oriented&nbsp;matroid programming|journal=Chinese Annals of Mathematics (Shuxue Niankan&nbsp;B&nbsp;Ji)|series=Series&nbsp;B|volume=8|year=1987|number=1|pages=120–125|issn=0252-9599|mr=886756|ref=harv|<!-- Google scholar reported no free versions -->}}