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.
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 the minimum ratio is shared by several rows, choose the lowest-numbered (i.e., topmost) one of them.
Extensions to oriented matroids
In the abstract setting of oriented matroids, 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, avoids cycles on all oriented-matroid linear-programs.
- Bland (1977).
- Christos H. Papadimitriou, Kenneth Steiglitz (1998-01-29). Combinatorial Optimization: Algorithms and Complexity. Dover Publications. pp. 53–55.
- Brown University - Department of Computer Science (2007-10-18). "Notes on the Simplex Algorithm". Retrieved 2007-12-17.
- Fukuda, Komei; Terlaky, Tamás (1997). "Criss-cross methods: A fresh view on pivot algorithms". In Thomas M. Liebling and Dominique de Werra. Mathematical Programming: Series B 79 (1-3) (Amsterdam: North-Holland Publishing Co.). pp. 369–395. doi:10.1007/BF02614325. MR 1464775.
- Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 459599.
- 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. Tucker, 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)
- Michael J. Todd (February 2002). "The many facets of linear programming". Mathematical Programming 91 (3). (Invited survey, from the International Symposium on Mathematical Programming.)