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

, Cunningham's rule (also known as least recently considered rule or round-robin rule) is an algorithmic refinement of the

simplex method In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...

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 and objective are represented by linear relationships. Linear ...

. 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 hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has po ...

). 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 Canadian and British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the School of Computer Science, ...

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