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]
Notesedit
^Cunningham, W. H. (1979). "Theoretical properties of the network simplex method". Mathematics of Operations Research. 4 (2): 196–208. doi:10.1287/moor.4.2.196.
cunningham, rule, this, article, about, mathematical, method, internet, concept, ward, cunningham, cunningham, mathematical, optimization, also, known, least, recently, considered, rule, round, robin, rule, algorithmic, refinement, simplex, method, linear, opt. This article is about the mathematical method For the Internet concept see Ward Cunningham Cunningham s Law 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 edit Cunningham W H 1979 Theoretical properties of the network simplex method Mathematics of Operations Research 4 2 196 208 doi 10 1287 moor 4 2 196 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 S2CID 2986216 Retrieved from https en wikipedia org w index php title Cunningham 27s rule amp oldid 1189035343, wikipedia, wiki, book, books, library,
