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 ...

, Bland's rule (also known as Bland's algorithm, Bland's anti-cycling rule or Bland's pivot 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 ...

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 function#As a polynomial function, li ...

. With Bland's rule, the simplex algorithm solves feasible

problems without cycling.. The original simplex algorithm starts with an arbitrary basic feasible solution, and then changes the basis in order to decrease the minimization target and find an optimal solution. Usually, the target indeed decreases in every step, and thus after a bounded number of steps an optimal solution is found. However, there are examples of degenerate linear programs, on which the original simplex algorithm cycles forever. It gets stuck at a basic feasible solution (a corner of the feasible polytope) and changes bases in a cyclic way without decreasing the minimization target. Such cycles are avoided by Bland's rule for choosing a column to enter and a column to leave the basis. Bland's rule was developed by

Robert G. Bland Robert Gary Bland (born February 25, 1948) is an American mathematician and operations researcher, a professor of operations research and information engineering at Cornell University.

, now an Emeritus Professor of operations research at

Cornell University Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to teach an ...

, while he was a research fellow at the

Center for Operations Research and Econometrics The Center for Operations Research and Econometrics (CORE) is an interdisciplinary research institute of the University of Louvain (UCLouvain) located in Louvain-la-Neuve, Belgium. Since 2010, it is part of the Louvain Institute of Data Analysis ...

in Belgium.

Algorithm

One uses Bland's rule during an iteration of the simplex method to decide first what column (known as the ''entering variable'') and then row (known as the ''leaving variable'') in the tableau to pivot on. Assuming that the problem is to minimize the objective function, the algorithm is loosely defined as follows: # Choose the lowest-numbered (i.e., leftmost) nonbasic column with a negative (reduced) cost. # Now among the rows, choose the one with the lowest ratio between the (transformed) right hand side and the coefficient in the pivot tableau where the coefficient is greater than zero. If the minimum ratio is shared by several rows, choose the row with the lowest-numbered column (variable) basic in it. It can be formally proved that, with Bland's selection rule, the simplex algorithm never cycles, so it is guaranteed to terminate in a bounded time. While Bland's pivot rule is theoretically important, from a practical perspective it is quite inefficient and takes a long time to converge. In practice, other pivot rules are used, and cycling almost never happens.

Extensions to oriented matroids

In the abstract setting of

oriented matroid An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid a ...

s, Bland's rule cycles on some examples. A restricted class of oriented matroids on which Bland's rule avoids cycling has been termed "Bland oriented matroids" by Jack Edmonds. Another pivoting rule, the

criss-cross algorithm In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear object ...

, avoids cycles on all oriented-matroid linear-programs.

Algorithm

Extensions to oriented matroids

Notes

Further reading