3.6. Cycling and Bland's Rule*

A discussion of the Simplex Algorithm wouldn't be complete without a discussion of at least one rule that can be used to avoid that pesky cycling problem. Bland's rule is one such rule. It unambiguously specifies the variable that needs to enter the basis and the variable that needs to leave the basis in each pivot step.

Let the LP \(P^{(s)}\) in a given iteration of the Simplex Algorithm be

\[\begin{gathered} \text{Maximize } cz + d\\ \begin{aligned} \text{s.t. } b &= Az\\ z &\ge 0, \end{aligned} \end{gathered}\]

and let \(B^{(s)}\) be its basis.

If we can still pivot, then there exists a non-basic variable \(z_j\) with positive coefficient \(c_j > 0\) in the objective function of \(P^{(s)}\). The first part of Bland's rule states that we should choose the non-basic variable \(z_j\) that enters the basis in the current iteration as the variable with minimum index among all such variables:

\[j = \min \{ h \mid c_h > 0 \}.\]

The second part of Bland's rule breaks ties between the basic variables that can leave the basis in the current iteration. Recall that we defined \(\Delta_i = \frac{b_i}{a_{ij}}\) and chose the basic variable \(z_{j_k}\) that leaves the basis as a variable that satisfies \(\Delta_k = \min \{ \Delta_1, \ldots, \Delta_m \}\). There may be more than one basic variable that meets this criterion. Bland's rule states that we should choose \(z_{j_k}\) so that

\[j_k = \min \{ j_i \mid \Delta_i = \min \{ \Delta_1, \ldots, \Delta_m \} \}.\]

In prose, we have

Bland's rule:

• Among all non-basic variables that can enter the basis in the current iteration, choose the one with minimum index.

• Given this choice of the non-basic variable that enters the basis, choose the basic variable that leaves the basis as the one with minimum index among all basic variables that can leave the basis.

The remainder of this chapter is dedicated to proving that this rule prevents the Simplex Algorithm from cycling. Specifically, we prove that the bases \(B^{(0)}, \ldots, B^{(t)}\) of the LPs \(P^{(0)}, \ldots, P^{(t)}\) produced by the Simplex Algorithm are all distinct. This implies in particular that

Theorem 3.5: If the Simplex Algorithm uses Bland's anti-cycling rule, it terminates after at most \(\binom{m+n}{m}\) iterations.

Proof: Note that every basis \(B^{(s)}\) consists of \(m\) variables and that these variables are chosen from a set of \(m + n\) variables of the LP. Thus, there are only \(\binom{m + n}{m}\) distinct bases to choose from. Therefore, if the algorithm ran for more than \(\binom{m+n}{m}\) iterations, then there would have to exist two LPs \(P^{(s_1)}\) and \(P^{(s_2)}\) with the same basis in the sequence of LPs produced by the algorithm, a contradiction. ▨

The upper bound on the number of iterations of the Simplex Algorithm established by Theorem 3.5 is not polynomial, and there exist artificial inputs where the algorithm does indeed need an exponential number of iterations to terminate. In practice, however, this exponential running time rarely materializes.

Before we can prove that Bland's rule prevents the Simplex Algorithm from cycling, we need two simple facts about the behaviour of the Simplex Algorithm when it does cycle:

Lemma 3.6: If two LPs \(P^{(s_1)}\) and \(P^{(s_2)}\) in the sequence of LPs produced by the Simplex Algorithm have the same basis \(B^{(s_1)} = B^{(s_2)}\), then their basic solutions \(\hat z^{(s_1)}\) and \(\hat z^{(s_2)}\) are identical and achieve the same objective function value.

Proof: If the two basic solutions are identical, then they clearly have the same objective function value because the LPs produced by the Simplex Algorithm are all equivalent; in particular, they assign the same objective function value to any given solution.

To prove that \(P^{(s_1)}\) and \(P^{(s_2)}\) have the same basic solution, recall from Section 3.1 that setting \(\hat z_j^{(s_1)} = 0\) for all \(j \notin B^{(s_1)}\) uniquely determines the values of all basic variables in the basic solution \(\hat z^{(s_1)}\) of \(P^{(s_1)}\): \(P^{(s_1)}\) has exactly one solution \(\hat z^{(s_1)}\) that satisfies \(\hat z_j^{(s_1)} = 0\) for all \(j \notin B^{(s_1)}\).

Since \(P^{(s_1)}\) and \(P^{(s_2)}\) are equivalent, the basic solution \(\hat z^{(s_2)}\) of \(P^{(s_2)}\) is also a solution of \(P^{(s_1)}\). Since \(B^{(s_1)} = B^{(s_2)}\), this solution also satisfies \(\hat z_j^{(s_2)} = 0\) for all \(j \notin B^{(s_1)}\). Since \(P^{(s_1)}\) has exactly one such solution, we must therefore have \(\hat z^{(s_1)} = \hat z^{(s_2)}\). ▨

Corollary 3.7: If two LPs \(P^{(s_1)}\) and \(P^{(s_2)}\) in the sequence of LPs produced by the Simplex Algorithm have the same basis \(B^{(s_1)} = B^{(s_2)}\), then all LPs \(P^{(s_1)}, \ldots, P^{(s_2)}\) have the same basic solution.

Proof: By Lemma 3.6, \(P^{(s_1)}\) and \(P^{(s_2)}\) have the same BFS. Since no pivoting step produces an LP whose BFS has a lower objective function value than the BFS of the previous LP, this implies that the BFSs \(\hat z^{(s_1)}, \ldots, \hat z^{(s_2)}\) of the LPs \(P^{(s_1)}, \ldots, P^{(s_2)}\) all have the same objective function value.

Next consider any index \(s\) with \(s_1 \le s < s_2\), let \(B^{(s+1)} \setminus B^{(s)} = \{j\}\), and assume that \(\hat z^{(s+1)}_j > 0\). Then \(\hat z^{(s+1)}\) would have a greater objective function value than \(\hat z^{(s)}\) because \(z_j\) has a strictly positive coefficient in the objective function of \(P^{(s)}\). Since we just observed that \(\hat z^{(s)}\) and \(\hat z^{(s+1)}\) have the same objective function value, we thus have \(\hat z^{(s+1)}_j = 0\). Therefore, the pivoting step that produces \(P^{(s+1)}\) from \(P^{(s)}\) is degenerate and \(\hat z^{(s+1)} = \hat z^{(s)}\). Since this is true for all \(s_1 \le s < s_2\), this shows that \(\hat z^{(s_1)} = \cdots = \hat z^{(s_2)}\). ▨

We are now ready to prove that Bland's rule prevents the Simplex Algorithm from cycling:

Theorem 3.8: If the Simplex Algorithm uses Bland's anti-cycling rule, it does not cycle.

Proof: Assume for the sake of contradiction that the algorithm cycles. Then there exist two LPs \(P^{(s_1)}\) and \(P^{(s_2)}\) with \(s_1 < s_2\) and with the same basis \(B^{(s_1)} = B^{(s_2)}\) in the sequence of LPs produced by the algorithm.

Let us call a variable \(z_j\) fickle if it belongs to at least one but not all of the bases \(B^{(s_1)}, \ldots, B^{(s_2)}\). Since \(B^{(s_1)} \ne B^{(s_1+1)}\) and \(\bigl|B^{(s_1)}\bigr| = \bigl|B^{(s_1+1)}\bigr| = m\), there exist at least two fickle variables.

Let \(\ell\) be the maximum index of all fickle variables, let \(s_1 \le p, q < s_2\) be indices such that \(z_\ell\) leaves the basis in iteration \(p\) and enters the basis in iteration \(q\). In other words, \(B^{(p)} \setminus B^{(p+1)} = \{\ell\}\) and \(B^{(q+1)} \setminus B^{(q)} = \{\ell\}\). Since \(B^{(s_1)} = B^{(s_2)}\) and \(z_\ell\) is fickle, these indices exist. Let \(z_h\) be the variable that enters the basis in iteration \(p\): \(B^{(p+1)} \setminus B^{(p)} = \{h\}\). Since \(h \notin B^{(p)}\) and \(h \in B^{(p+1)}\), \(z_h\) is also fickle and thus, by the choice of \(z_\ell\),

\[h < \ell.\tag{3.6}\]

Next assume that \(P^{(p)}\) is the LP

\begin{gather} d' + \sum_{j=1}^{m+n} c'_jz_j\tag{3.7}\\ \begin{aligned} \text{s.t.}\ b_i' &= \sum_{j=1}^{m+n} a_{ij}'z_j && \forall 1 \le i \le m\\ z_j &\ge 0 && \forall 1 \le j \le m + n \end{aligned} \end{gather}

and \(P^{(q)}\) is the LP

\begin{gather} d'' + \sum_{j=1}^{m+n} c''_jz_j\tag{3.8}\\ \begin{aligned} \text{s.t.}\ b_i'' &= \sum_{j=1}^{m+n} a_{ij}''z_j && \forall 1 \le i \le m\\ z_j &\ge 0 && \forall 1 \le j \le m + n. \end{aligned} \end{gather}

Let the basis of \(P^{(p)}\) be \(B^{(p)} = (j_1, \ldots, j_m)\).

Now consider an arbitrary value \(y \in \mathbb{R}\) and a (not necessarily feasible) solution \(\tilde z\) that sets \(\tilde z_h = y\) and \(\tilde z_j = 0\) for all \(j \notin B^{(p)} \cup \{h\}\) (for all non-basic variables of \(P^{(p)}\) other than \(z_h\)). This forces the value of each basic variable \(z_{j_i}\) of \(P^{(p)}\) to be

\[\tilde z_{j_i} = b_i' - a_{ih}'y.\]

Since the coefficient \(c_j'\) associated with every basic variable \(z_j\) is \(0\), the objective function value associated with this solution by (3.7) is

\[d' + c'_hy.\]

Since \(\tilde z_j = 0\) for all \(j \notin B^{(p)} \cup \{h\}\), the objective function value associated with this solution by (3.8) is

\[d'' + c''_hy + \sum_{j \in B^{(p)}} c''_j \tilde z_j = d'' + c''_hy + \sum_{i=1}^m c''_{j_i}(b_i' - a_{ih}'y).\]

Since \(P^{(p)}\) and \(P^{(q)}\) are equivalent, these two objective function values are the same:

\[d' + c'_hy = d'' + c''_hy + \sum_{i=1}^m c''_{j_i}\bigl(b_i' - a_{ih}' y\bigr).\]

Since this equality holds for every choice of \(y\), this implies that

\[c'_h = c''_h - \sum_{i=1}^m c''_{j_i} a_{ih}.\tag{3.9}\]

Now observe that, since \(z_h\) enters the basis in the \(p\)th iteration, \(c_h' > 0\). Since \(z_\ell\) enters the basis in the \(q\)th iteration, \(c_\ell'' > 0\). Moreover, \(c_h'' \le 0\) because \(c_h'' > 0\) would imply that \(z_h\) is a non-basic variable that can enter the basis in the \(q\)th iteration but \(h < \ell\) (see (3.6)) and, by the first part of Bland's rule, \(\ell\) is the minimum index of all non-basic variables that can enter the basis in the \(q\)th iteration.

Since \(c'_h > 0\) and \(c''_h \le 0\), (3.9) shows that

\[\sum_{i=1}^m c''_{j_i} a_{ih}' < 0,\]

that is, there exists an index \(i\) such that

\[c''_{j_i} a_{ih}' < 0.\tag{3.10}\]

This implies that \(c''_{j_i} \ne 0\). Thus, \(z_{j_i}\) is a non-basic variable in the \(q\)th iteration (because every index \(j \in B^{(q)}\) satisfies \(c''_j = 0\)). It is also a basic variable in the \(p\)th iteration (because \(j_i \in B^{(p)}\)). This shows that \(z_{j_i}\) is fickle and, hence,

\[j_i \le \ell.\tag{3.11}\]

Since \(z_\ell\) leaves the basis in iteration \(p\), we have \(\ell \in B^{(p)}\), that is, \(\ell = j_{i_\ell}\), for some index \(1 \le i_\ell \le m\). This index satisfies \(a_{i_\ell h}' > 0\) because otherwise the \(i_\ell\)th constraint would impose no upper bound on \(z_h\) and either the LP would be unbounded—and the algorithm would terminate—or \(z_\ell\) would not be the variable that leaves the basis in the \(p\)th iteration. Since \(c_\ell'' > 0\), this implies that

\[c''_\ell a_{i_\ell h}' > 0.\]

Since \(c''_{j_i}a_{ih}' < 0\) (see (3.10)), this shows that \(j_i \ne \ell\), that is,

\[j_i < \ell\]

(since \(j_i \le \ell\) by (3.11)).

To finish the proof, observe that \(c''_{j_i} \le 0\). Otherwise, \(z_{j_i}\) could enter the basis in the \(q\)th iteration and, since \(j_i < \ell\), Bland's rule would choose it over \(z_\ell\). Since \(c''_{j_i}a_{ih}' < 0\), this implies that

\[a_{ih}' > 0.\]

Therefore, the \(i\)th constraint in \(P^{(p)}\) imposes an upper bound on \(z_h\). Since every pivoting operation in the cycle is degenerate, every fickle variable has value \(0\) in the BFS of \(P^{(s_1)}, \ldots, P^{(s_2)}\). Thus, \(z_{j_i} = b_i = 0\) and the upper bound on \(z_h\) imposed by the \(i\)th constraint in \(P^{(p)}\) is

\[\frac{b_i}{a_{ih}'} = 0 \le \frac{b_{i_\ell}}{a_{i_\ell h}'}.\]

Thus, \(z_{j_i}\) is a basic variable that can be chosen as the one leaving the basis in the \(p\)th iteration, a contradiction to the second part of Bland's rule because \(\ell > j_i\) and \(z_\ell\) is chose as the variable to leave the basis in this iteration. ▨