Criss-cross algorithm: Difference between revisions

Revision as of 13:19, 29 October 2014

Revision as of 22:34, 16 November 2014

Line 22:

==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. anAn 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.

==Computational complexity: Worst and average cases==