3.4 Degeneracy, cycling and Bland’s rule
At a degenerate BFS the ratio test can give \(\theta ^* = 0\): the basis changes but the point does not. The proof of Theorem 3.1.3 then fails, and the method can cycle, returning to a basis it has visited and repeating forever. Beale (1955) gave an example with three constraints in which Dantzig’s rule cycles through six bases at the same degenerate vertex (Software 3.6.3). Cycling is rare in practice, but it can be prevented.
Theorem 3.4.1 (Bland’s rule). If the entering variable is always the eligible one (\(\bar c_j < 0\)) with the smallest index, and ties in the ratio test are broken by choosing the leaving variable with the smallest index, the simplex method never cycles.
The proof (Bland, 1977) supposes a cycle and considers the largest index \(t\) of a variable that enters and leaves during it; comparing the tableau where \(x_t\) leaves with the one where it re-enters yields a contradiction in the signs of the reduced costs. Other remedies are the lexicographic rule and small perturbations of \(b\). With any anti-cycling rule, the simplex method solves every LP in finitely many pivots, which gives a constructive proof of the fundamental theorem.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.