Bland's Rule and Anti-Cycling

Bland's rule is a deterministic pivot-selection rule for the simplex method that provably prevents cycling. The entering variable is the smallest-indexed nonbasic variable with a negative reduced cost; the leaving variable is the smallest-indexed basic variable among those tied in the minimum-ratio test. This lesson introduces both halves of the rule, applies them to degenerate iterations, and works through a full pivot.

Step 1 of 157%

Tutorial

Bland's Rule for the Entering Variable

Cycling in the simplex method occurs only at degenerate vertices, where a sequence of pivots returns to a previously visited basis without improving the objective. Bland's rule is a deterministic pivot-selection rule that provably prevents cycling.

Bland's rule has two parts:

Entering variable. Among all nonbasic variables $x_j$ with negative reduced cost $\bar{c}_j < 0$ , choose the one with the smallest index $j$ .

Leaving variable. Perform the minimum-ratio test as usual. If several basic variables tie for the minimum ratio, choose the one with the smallest index.

These two rules together remove all ambiguity from the pivot choice. The standard "most-negative reduced cost" and "first row found" rules can cycle on degenerate problems; Bland's rule cannot.

As a tiny illustration, suppose the nonbasic variables and their reduced costs are

\bar{c}_2 = 3,\qquad \bar{c}_4 = -2,\qquad \bar{c}_5 = -6.

The most-negative-cost rule would pick $x_5$ , but Bland's rule picks $x_4$ — the smallest-indexed nonbasic variable with $\bar{c}_j < 0$ .