mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, 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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

. 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 The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit cube, unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorith ...

). 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 David Michael Avis (born March 20, 1951) is a Canadians, Canadian and United Kingdom, British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the S ...

and

Oliver Friedmann Oliver Friedmann is a German computer scientist and mathematician known for his work on parity games and the simplex algorithm. Friedmann earned his doctorate's degree from the Ludwig Maximilian University of Munich in 2011 under the supervision ...

that there is a family of linear programs on which the simplex algorithm equipped with Cunningham's rule requires exponential time.

Notes

{{Reflist Optimization algorithms and methods Exchange algorithms Oriented matroids Linear programming