Cunningham's rule

In mathematical optimization, Cunningham's rule (also known as least recently considered rule or round-robin rule) is an algorithmic refinement of the simplex method for linear optimization.

The rule was proposed 1979 by W. H. Cunningham to defeat the deformed hypercube constructions by Klee and Minty et. al. (see, e.g. Klee–Minty cube).[1]

Cunningham's rule assigns a cyclic order to the variables and remembers the last variable to enter the basis. The next entering variable is chosen to be the first allowable candidate starting from the last chosen variable and following the given circular order. History-based rules defeat the deformed hypercube constructions because they tend to average out how many times a variable pivots.

It has recently been shown by David Avis and Oliver Friedmann that there is a family of linear programs on which the simplex algorithm equipped with Cunningham's rule requires exponential time.[2]

Notes
  1. Cunningham, W.H. (1979). "Theoretical properties of the network simplex method". Mathematics of Operations Research.
  2. Avis, David; Friedmann, Oliver (2017). "An exponential lower bound for Cunningham's rule". Mathematical Programming. 161 (1–2): 271–305. arXiv:1305.3944. doi:10.1007/s10107-016-1008-4.
gollark: Would that be such a bad thing?
gollark: Presumably you could have a similar system be trained on messages as they're sent.
gollark: WHY
gollark: You can just use adblock for the actual website, and alternative YouTube clients like NewPipe for mobile devices.
gollark: Not entirely sure what my *favourite* is, but I like this: https://www.youtube.com/watch?v=KxUHE6u9SDc
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.