ADDENDUM: Bland's pivoting rule

In 1977 R.G. Bland proposed the pivoting rule of the least index. When Bland's rule is adopted, then the simplex method is guaranteed not to cycle.

Pivoting Rule 1 (Least Index Rule)   Let us assume to have introduced a total order on the indices of the variables (hence we can regard to the variables as to $x_1, x_2, \ldots$).

• When more non-basic variables are candidates for entering the basis (positive reduced cost), then we choose among them the variable of smallest index.
  
• When more basic variables are candidates for leaving the basis (hence degeneracy will result, since even the ones among them which will remain basic will have $0$ value in the basic solution associated to the next dictionary), then we choose among them the variable of smallest index.

Note that Bland's rule uniquely specifies both the entering and the leaving variable (contrary to what happens with the anti-degenerative methods like the perturbation method or the lexicographic method, where only the exiting variable is decided by the method and we are left free choice on the entering variable). In fact, this drawback delayed (at least in a first time) its adoption.

Here follows a formal proof of the following result.

Teorema 1 (R. G. Bland 1977)   When the least index rule is adopted, then the simplex method can not cycle. (And hence its termination is guaranteed).

proof: Assume, by absurd, that the method cycles producing the following sequence of dictionaries: $D_0, D_1, D_2, \ldots, D_k = D_0$. A variable is called fickle if it is basic for some but not all of these dictionaries. Let $t$ be the maximum index for which $x_t$ is fickle. In the sequence $D_0, D_1, \ldots, D_k$ there will be a dictionary $D$ having $x_t$ as exiting variable (basic for $D$ but non-basic for the next dictionary) and let $x_s$ be the variable entering in the basis in place of $x_t$. Clearly, the sequence $D_0, D_1, \ldots, D_k$ contains a dictionary $D^*$ with $x_t$ entering back. Where $B$ is the set of indices of the variables which are basic for $D$, then the structure of $D$ is as follows:

$$\begin{array}{l} x_i = b_i - \sum_{j \notin B} a_{ij} x_j ... ... \overline{z = v + \sum_{j \notin B} c_j x_j} \\ \end{array}$$

Moreover, the objective function $z$ takes the same value in the basic solutions associated to $D$ and $D^*$. Therefore, last row of dictionary $D^*$ can be written as:

$$z = v + \sum_{j=1}^{n+m} c^*_j x_j$$

where $c^*_j = 0$ whenever $x_j$ is basic for $D^*$. Since this last equation has been obtained from the equations describing $D$ through pivoting operations, it must admit any solution which is admitted from $D$. In particular, it must be satisfied by the following choice of values:

$$\begin{array}{l} x_s = y \mbox{\hspace{1cm} per qualsiasi ... ...mbox{\hspace{1cm}} (i\in B) \\ z = v + c_s y \\ \end{array}$$

Therefore, $v + c_s y = v + c^*_s y + \sum_{i\in B} c^*_i (b_i - a_{is} y)$, which, after simple rewriting becomes:

$$\left( c_s - c^*_s + \sum_{i \in B} c^*_i a_{is} \right)y = \sum_{i \in B} c^*_i b_i$$

Since the second term of this equation is a constant independent from $y$ we can conclude that $c_s - c^*_s + \sum_{i \in B} c^*_i a_{is} = 0$. Moreover, $c_s > 0$ since $x_s$ is entering in $D$. Furthermore $c^*_s \leq 0$ since $s < t$ and nevertheless $x_t$ and not $x_s$ is the variable entering in $D^*$. We therefore conclude that

$$c^*_r a_{rs} < 0 \mbox{\hspace{1cm} for some $r\in B$}$$

Since $c^*_r \neq 0$, the variable $x_r$ is not basic for $D^*$ and is hence fickle. However $r\neq t$ since $c^*_t a_{ts} > 0$: since $x_t$ enters for $D^*$, then $c^*_t > 0$; since $x_t$ exits for $D$, then $a_{ts} > 0$. Therefore, $r < t$ and since $x_r$ does not enter in $D^*$ in the place of $x_t$, we can conclude that $c^*_r$ can not be positive. Therefore

$$a_{rs} > 0 \mbox{\hspace{1cm} for some $r\in B$\ different from $t$}$$

Since all iterations in the cycle are degenerate, to $D$ and $D^*$ precisely the same solution is associated. And all fickle variables are set to zero in this solution. In particular $x_r$, which is non-basic for $D^*$, will have zero value also in the solution associated to $D$ and therefore $b_r = 0$. But then $x_r$ was a candidate to leave the basis in $D$. This is at odds with the least index rule, since we preferred $x_t$ to $x_r$. $\Box$