Bland's rule
In mathematical optimization, 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 for linear optimization.
With Bland's rule, the simplex algorithm solves feasible linear optimization problems without cycling.[1][2][3]
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, now an Emeritus Professor of operations research at Cornell University, while he was a research fellow at the Center for Operations Research and Econometrics in Belgium.[1]
Algorithm
[edit]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.[4]: 72–76
Extensions to oriented matroids
[edit]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.[5]
Notes
[edit]- ^ a b Bland (1977).
- ^ Christos H. Papadimitriou, Kenneth Steiglitz (1998-01-29). Combinatorial Optimization: Algorithms and Complexity. Dover Publications. pp. 53–55. ISBN 9780486402581.
- ^ Brown University - Department of Computer Science (2007-10-18). "Notes on the Simplex Algorithm" (PDF). Retrieved 2007-12-17.
- ^ Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.: 44–48
- ^ Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms" (PDF). Mathematical Programming, Series B. 79 (1–3). Amsterdam: North-Holland Publishing Co.: 369–395. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
Further reading
[edit]- 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 0459599.
- 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): 417–436. doi:10.1007/s101070100261. S2CID 6464735. (Invited survey, from the International Symposium on Mathematical Programming.)