Bland's rule

In applied mathematics, Bland's rule (also known as Bland's algorithm or Bland's anti-cycling rule) is a technique used in the simplex method for ensuring that a linear optimization problem always converges to an answer. [1][2] Whenever there is a degenerate corner in the LP (e.g., when Ax = 0), then the simplex algorithm may cycle forever. Bland's rule can break these cycles by using a simple heuristic to decide which column to pivot on. It was developed by Cornell University Engineering professor Robert Bland.

Algorithm

One uses Bland's rule during an iteration of the simplex method to decide what 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:

1. Choose the lowest-numbered (i.e., leftmost) nonbasic column t with a negative cost .

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

References

1. ^ Christos H. Papadimitriou, Kenneth Steiglitz (1998-01-29). Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 53-55.

2. ^ Brown University - Department of Computer Science (2007-10-18). Notes on the Simplex Algorithm. Retrieved on 2007-12-17.