Content deleted Content added
mNo edit summary |
Mentioning Zadeh's rule as the most prominent history-based pivot rule. |
||
Line 265:
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">
{{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>
History-based pivot rules such as [[Zadeh's Rule]] also try to circumvent the issue of stalling and cycling by keeping track how often particular variables are being used, and then favor such variables that have been used least often.
===Efficiency===
| |||