Bland’s Rule guarantees termination

First we’ll explain why the only way for the Simplex Method to fail to finish when following a given pivoting rule is for it to cycle, which means to get stuck in a loop of degenerate pivots that bring you back exactly to a previous dictionary (and once a dictionary repeats, the rule your following will make you choose the same pivots over and over again).

Imagine that the Simplex Method fails to finish, pivoting for all eternity. Since there are only a finite number of possible sets of basic variables, at some point you must reach a dictionary with exactly the same set of basic variables as a previous dictionary. But then not just the basic variables but the whole dictionary must repeat: the matrix formulas for the dictionary we found prove that once you know which variables are basic, the entire dictionary is determined.

So now all we need to show is that following Bland’s rule we never repeat a dictionary (or equivalently, never repeat a basis).

Assume for the sake of obtaining a contradiction that \(D_0\), \(D_1\), …, \(D_{k-1}\), \(D_k = D_0\) is a cycle of dictionaries each obtained from the previous by Bland’s rule. Of course, all of the pivots must be degenerate since otherwise the value of the objective function would be larger in the last dictionary than in the first.

For the purposes of this proof, call a variable fickle if it enters or leaves the basis at some point on the cycle; that is, if it is basic in some dictionary and non-basic in some other dictionary of the cycle.

Let \(x_t\) be the fickle variable with largest index. For some dictionary \(D_p\) in the cycle, \(x_t\) must exit with, say, \(x_s\) entering. At some later point \(x_t\) must enter the basis again, let’s say that it is chosen to enter in the pivot from dictionary \(D_q\) to \(D_{q+1}\).

Say the dictionary \(D_p\) looks like:

\[\begin{aligned} x_i & = b_i - \sum_{j \notin B_p} a_{ij} x_j\\ z & = v + \sum_{j \notin B_p} c_j x_j \end{aligned}\]

(Here \(B_p\) is the set of indices of basic variables for dictionary \(D_p\), so the sums \(\sum_{j \notin B_p}\) range over non-basic variables for \(D_p\), as you’d expect.)

Since all the pivots are degenerate in \(D_q\) the objective function still has value \(v\), so its last row must look like \(z = v + \sum_{j=1}^{m+n} c^*_j x_j\) (where, for convenience, we’ve listed all the variables, but any basic variable for \(D_q\) has coefficient 0).

All the dictionaries are systems of equations with the same solutions, so any solution (even if not feasible) of \(D_p\) we manage to write down must also satisfy \(D_q\). Take, for the non-basic variable in \(D_p\) the values \(x_s = y\), \(x_j = 0\) for \(j \neq s, j \notin B_p\), which force \(x_i = b_i - a_{is} y\) for the basic variables. Since this choice must also solve \(D_q\), we have, equating the objective functions, that \[ v + c_s y = v + c^*_s y + \sum_{i \in B_p} c^*_i(b_i - a_{is} y).\]

This must be true for any value of \(y\), so the two sides must be the same function of \(y\). The graph of each side as a function of \(y\) is a straight line and since they are equal they must have the same slope, so we learn that

\begin{equation} c_s = c^*_s - \sum_{i \in B_p} c^*_i a_{is}. \label{slopes} \end{equation}

Now we will gather some inequalities about these various quantities with the eventual aim of showing that Bland’s Rule would not actually have chosen \(x_t\) to exit the basis of \(D_p\). That contradiction will show that Bland’s Rule cannot lead to cycling.

• \(c_s > 0\). This is because \(x_s\) is chosen as the entering variable for \(D_p\), so it must appear in the objective function with positive coefficient.
• \(c^*_s \le 0\) and \(c^*_t>0\). This is because in \(D_q\) the entering variable is \(x_t\) and according to Bland’s rule, \(x_t\) must the variable with smallest index that has a positive coefficient in the \(z\)-row of \(D_q\). Since \(s < t\) (because we assumed \(x_t\) had the largest index among fickle variables), we have \(c^*_s \le 0\).

Then, by equation \eqref{slopes}, we must have that \(\sum_{i \in B_p} c^*_i a_{is} < 0\), so at least one of the terms \(c^*_i a_{is}\) must be negative. What can we say about the variable \(x_i\)?

• It’s basic in \(D_p\) because the sum only ranges over \(i \in B_p\).
• It’s non-basic in \(D_q\) because \(c^*_i \neq 0\) (if \(c^*_i\) were \(0\), then \(c^*_i a_{is}\) would be zero rather than negative).
• Therefore \(x_i\) is fickle and \(i \le t\) (because \(t\) was chosen to be the largest index of a fickle variable).
• But we can’t have \(i=t\)! This is because \(i\) was chosen so that \(c^*_i a_{is} < 0\) but \(c^*_t a_{ts} > 0\): we already saw that \(c^*_t > 0\); and in dictionary \(D_p\) the variable \(x_s\) was chosen to enter and \(x_t\) was chosen to exit, so \(a_{ts}>0\) because \(x_t\) had to impose a restriction on the increase of \(x_s\).

Now we can argue that Bland’s Rule actually would have chosen \(x_i\) over \(x_t\) to exit the basis of dictionary \(D_p\). We know that \(i < t\), so if \(x_i\) is viable candidate for the exiting variable, then it would be chosen. We need to show:

1. That \(a_{is}>0\), so that \(x_i\) does impose a limit on how far \(x_s\) could increase.

   To see this, it is enough to show \(c^*_i \le 0\), because \(i\) was chosen to satisfy \(c^*_i a_{is} < 0\). Recall that \(x_t\) was selected by Bland’s Rule to enter the basis when the dictionary was \(D_q\), so we must have \(c^*_i \le 0\) because we know \(i < t\).

2. That the restriction \(x_i\) imposes, \(x_s \le b_i/a_{is}\), is at least as strong as the restriction imposed by \(x_t\), which is \(x_s \le b_t/a_{ts}\).

   In fact both \(b_i = b_t = 0\)! Every pivot in a cycle must be degenerate so that all variables conserve their values throughout the process and every fickle variable must therefore be zero in the solution associated to any dictionary in the cycle.