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. cite book | title = Combinatorial Optimization: Algorithms and Complexity | publisher = Dover Publications | author = Christos H. Papadimitriou, Kenneth Steiglitz | date = 1998-01-29 | pages = 53-55 ] cite web | url = http://www.cs.brown.edu/courses/csci1490/notes/day9.pdf | title = Notes on the Simplex Algorithm| accessdate = 2007-12-17 | author = Brown University - Department of Computer Science |date = 2007-10-18 ] 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:

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

References