Content deleted Content added
m Journal cites, using AWB (11335) |
m →Degeneracy: Stalling and cycling: decapitalized common noun in section heading as per MOS:HEAD |
||
Line 261:
In large linear-programming problems '''A''' is typically a [[sparse matrix]] and, when the resulting sparsity of '''B''' is exploited when maintaining its invertible representation, the revised simplex algorithm is a much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.<ref name="DantzigThapa2"/><ref name="Padberg" >M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref><ref>Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)</ref><ref name="MarosMitra" >{{cite book|last1=Maros|first1=István|last2=Mitra|first2=Gautam|chapter=Simplex algorithms|mr=1438309|title=Advances in linear and integer programming|pages=1–46|editor=J. E. Beasley|publisher=Oxford Science|year=1996}}</ref><ref>{{cite book|mr=1960274|last=Maros|first=István|title=Computational techniques of the simplex method|series=International Series in Operations Research & Management Science|volume=61|publisher=Kluwer Academic Publishers|___location=Boston, MA|year=2003|pages=xx+325|isbn=1-4020-7332-1}}</ref>
===Degeneracy:
If the values of all basic variables are strictly positive, then a pivot must result in an improvement in the objective value. When this is always the case no set of basic variables occurs twice and the simplex algorithm must terminate after a finite number of steps. Basic feasible solutions where at least one of the ''basic ''variables is zero are called ''degenerate'' and may result in pivots for which there is no improvement in the objective value. In this case there is no actual change in the solution but only a change in the set of basic variables. When several such pivots occur in succession, there is no improvement; in large industrial applications, degeneracy is common and such "''stalling''" is notable.
Worse than stalling is the possibility the same set of basic variables occurs twice, in which case, the deterministic pivoting rules of the simplex algorithm will produce an infinite loop, or "cycle". While degeneracy is the rule in practice and stalling is common, cycling is rare in practice. A discussion of an example of practical cycling occurs in Padberg.<ref name="Padberg"/> [[Bland's rule]] prevents cycling and thus guarantees that the simplex algorithm always terminates.<ref name="Padberg"/><ref name="Bland">
| |||