Bland's rule
Encyclopedia
In mathematical optimization, Bland's rule (also known as Bland's algorithm or Bland's anti-cycling rule) is an algorithmic refinement of the simplex method for linear optimization
.
With Bland's rule, the simplex algorithm solves feasible linear optimization problems without cycling. There are examples of degenerate linear optimization problems on which the original simplex algorithm would cycle forever. Such cycles are avoided by Bland's rule for choosing a column to enter the basis.
Bland's rule was developed by Robert Gary Bland, now a professor of operations research at Cornell University
.
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
.
With Bland's rule, the simplex algorithm solves feasible linear optimization problems without cycling. There are examples of degenerate linear optimization problems on which the original simplex algorithm would cycle forever. Such cycles are avoided by Bland's rule for choosing a column to enter the basis.
Bland's rule was developed by Robert Gary Bland, now a professor of operations research at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
.
Algorithm
One uses Bland's rule during an iteration of the simplex method to decide first what column (known as the entering column) and then row (known as the leaving row) 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 t with a positive cost.
- Now among the rows choose the one with the lowest ratio between the cost and the index in the matrix where the index is greater than zero. If several rows have the same minimum ratio, choose the first one (i.e., topmost) of them.
Further reading
- George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
- Kattta G. Murty, Linear Programming, Wiley, 1983.
- Evar D. Nering and Albert W. TuckerAlbert W. TuckerAlbert William Tucker was a Canadian-born American mathematician who made important contributions in topology, game theory, and non-linear programming....
, 1993, Linear Programs and Related Problems, Academic Press. - M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.
- Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover. (computer science)
- Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical) (Invited survey, from the International Symposium on Mathematical Programming.)