Content deleted Content added
Citation bot (talk | contribs) m Alter: doi-broken-date, number. Removed URL that duplicated unique identifier. Formatted dashes. | You can use this bot yourself. Report bugs here.| Activated by User:AManWithNoPlan | Category:Pages_with_DOIs_inactive_as_of_2019. |
→Degeneracy: stalling and cycling: wikilink |
||
Line 258:
===Degeneracy: stalling and cycling===
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 [[Manfred W. Padberg|Padberg]].<ref name="Padberg"/> [[Bland's rule]] prevents cycling and thus guarantees that the simplex algorithm always terminates.<ref name="Padberg"/><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|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|ref=harv}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> Another pivoting algorithm, the [[criss-cross algorithm]] never cycles on linear programs.<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>
| |||