Now that we know the simplex method maintains a basic feasibles solution at each iteration with objective function value at most the objective function value of the basic feasible solution in previous iterations, we want to know if the simplex method will actually terminate. As the number of bases is finite (there are no more than \(\binom{n}{m}\) bases), the simplex method will terminate as long as no basis is encountered more than once. (For instance, finite termination is guaranteed if no basic feasible solution is degenerate.) Unfortunately, the algorithm as stated could encounter the same basis twice. Encountering the same basis twice is called cycling. It is known that cycling cannot occur in LP problems with fewer than six variables and there exist examples of cycling with six variables. Below is an example of cycling with eight variables.
Consider the problem \(\min\{ \mathbf{c}^\mathsf{T}\mathbf{x} :\mathbf{A}\mathbf{x} = \mathbf{0},~ \mathbf{x} \geq \mathbf{0}\}\) where \(\mathbf{x} = [x_1,\ldots,x_8]^\mathsf{T}\), \(\mathbf{A} = \left[\begin{array}{rrrrrrrr} 1 & 0 & 1 & -1 &-1 & 0 & -\frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 0 & \frac{1}{4} & \frac{1}{2} &-1 & -1 & \frac{1}{2} \end{array}\right]\), and \(\mathbf{c} = [2,0,0,-1/2,-2,2,-1,3/2]^\mathsf{T}\).
We show that if we solve the above problem starting with the basis \(B = \{2,3\}\) using the simplex method, we could have the sequence of bases: \(\{3,4\}\), \(\{4,5\}\), \(\{5,6\}\), \(\{6,7\}\), \(\{7,8\}\), \(\{1,8\}\), \(\{1,2\}\). Once we reach \(\{1,2\}\), we will be forced to go back to \(\{2,3\}\) again.
Take the basis \(B = \{2,3\}\). The associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & - & 2x_1 & & & & & + & \frac{1}{2}x_4 & + & 2x_5 & - & 2x_6 & + & x_7 & - & \frac{3}{2} x_8 & = & 0 \\ & & x_1 & & & + & x_3 & - & x_4 & - & x_5 & & & - & \frac{1}{2}x_7 & + & \frac{1}{2}x_8 & = & 0 \\ & & & & x_2 & & & + & \frac{1}{4}x_4 & + & \frac{1}{2} x_5 & - & x_6 & - & x_7 & + & \frac{1}{2}x_8 & = & 0. \end{array} \] Since the coefficient of \(x_4\) in the \(z\)-row is positive, \(x_4\) can be the entering variable. Only the last equation in the tableau has a positive coefficient for \(x_4\). Thus, \(x_2\) is the leaving variable. Thus, the new basis is \(B = \{3,4\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & - & 2x_1 & - & 2x_2 & & & & & + & x_5 & & & + & 3 x_7 & - & \frac{5}{2} x_8 & = & 0 \\ & & x_1 & + & 4x_2 & + & x_3 & & & + & x_5 & -& 4x_6 & - & \frac{9}{2}x_7 & + & \frac{5}{2}x_8 & = & 0 \\ & & & & 4x_2 & & & + & x_4 & + & 2 x_5 & - & 4 x_6 & - & 4 x_7 & + & 2x_8 & = & 0. \end{array} \] Since the coefficient of \(x_5\) in the \(z\)-row is positive, \(x_5\) can be the entering variable. We have a choice for the leaving variable between \(x_3\) and \(x_4\) but we will choose \(x_3\). Thus, the new basis is \(B = \{4,5\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & - & 3x_1 & - & 6x_2 & - & x_3 & & & & & + & 4x_6 & + & \frac{15}{2} x_7 & - & 5 x_8 & = & 0 \\ & & -2x_1 & - & 4x_2 & - & 2x_3 & + & x_4 & & & + & 4 x_6 & + & 5 x_7 & - & 3x_8 & = & 0 \\ & & x_1 & + & 4x_2 & + & x_3 & & & + & x_5 & -& 4x_6 & - & \frac{9}{2}x_7 & + & \frac{5}{2}x_8 & = & 0. \\ \end{array} \] Since the coefficient of \(x_6\) in the \(z\)-row is positive, \(x_6\) can be the entering variable. Only the second equation in the tableau has a positive coefficient for \(x_6\). Thus, \(x_4\) is the leaving variable. Thus, the new basis is \(B = \{5,6\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & - & x_1 & - & 2x_2 & + & x_3 & - & x_4 & & & & & + & \frac{5}{2} x_7 & - & 2 x_8 & = & 0 \\ & & -x_1 & & & - & x_3 & + & x_4 & + & x_5 & & & + & \frac{1}{2}x_7 & - & \frac{1}{2}x_8 & = & 0 \\ & & -\frac{1}{2}x_1 & - & x_2 & - & \frac{1}{2}x_3 & + & \frac{1}{4}x_4 & & & + & x_6 & + & \frac{5}{4} x_7 & - & \frac{3}{4}x_8 & = & 0. \\ \end{array} \] Since the coefficient of \(x_7\) in the \(z\)-row is positive, \(x_7\) can be the entering variable. We have a choice for the leaving variable between \(x_5\) and \(x_6\) but we will choose \(x_5\). Thus, the new basis is \(B = \{6,7\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & + & 4x_1 & - & 2x_2 & + & 6x_3 & - & 6x_4 & - & 5x_5 & & & & & + & \frac{1}{2} x_8 & = & 0 \\ & & 2x_1 & - & x_2 & + & 2x_3 & - & \frac{9}{4}x_4 & - & \frac{5}{2}x_5 & + & x_6 & & & + & \frac{1}{2}x_8 & = & 0 \\ & & -2x_1 & & & - & 2x_3 & + & 2x_4 & + & 2x_5 & & & + & x_7 & - & x_8 & = & 0. \\ \end{array} \] Since the coefficient of \(x_8\) in the \(z\)-row is positive, \(x_8\) can be the entering variable. Only the second equation in the tableau has a positive coefficient for \(x_8\). Thus, \(x_6\) is the leaving variable. Thus, the new basis is \(B = \{7,8\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & + & 2x_1 & - & x_2 & + & 4x_3 & - & \frac{15}{4}x_4 & - & \frac{5}{2}x_5 & - & x_6 & & & & & = & 0 \\ & & 2x_1 & - & 2x_2 & + & 2x_3 & - & \frac{5}{2}x_4 & - & 3x_5 & + & 2x_6 & + & x_7 & & & = & 0 \\ & & 4x_1 & - & 2x_2 & + & 4x_3 & - & \frac{9}{2}x_4 & - & 5x_5 & + & 2x_6 & & & + & x_8 & = & 0. \\ \end{array} \] Since the coefficient of \(x_1\) in the \(z\)-row is positive, \(x_1\) can be the entering variable. We have a choice for the leaving variable between \(x_7\) and \(x_8\) but we will choose \(x_7\). Thus, the new basis is \(B = \{1,8\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & & & + & x_2 & + & 2x_3 & - & \frac{5}{4}x_4 & + & \frac{1}{2}x_5 & - & 3x_6 & - & x_7 & & & = & 0 \\ & & x_1 & - & x_2 & + & x_3 & - & \frac{5}{4}x_4 & - & \frac{3}{2}x_5 & + & x_6 & + & \frac{1}{2}x_7 & & & = & 0 \\ & & & & 2x_2 & & & + & \frac{1}{2}x_4 & + & x_5 & - & 2x_6 & - & 2x_7 & + & x_8 & = & 0. \\ \end{array} \] Since the coefficient of \(x_2\) in the \(z\)-row is positive, \(x_2\) can be the entering variable. Only the last equation in the tableau has a positive coefficient for \(x_2\). Thus, \(x_8\) is the leaving variable. Thus, the new basis is \(B = \{1,2\}\) whose associated tableau is: \[ \small \begin{array}{ccccccccccccccccccl} z & & & & & + & 2x_3 & - & \frac{3}{2}x_4 & & & - & 2x_6 & & & - & \frac{1}{2} x_8 & = & 0 \\ & & x_1 & & & + & x_3 & - & x_4 & - & x_5 & - & & - & \frac{1}{2}x_7 & +& \frac{1}{2}x_8 & = & 0 \\ & & & & x_2 & & & + & \frac{1}{4}x_4 & + & \frac{1}{2}x_5 & - & x_6 & - & x_7 & + & \frac{1}{2}x_8 & = & 0. \\ \end{array} \] Now, in the \(z\)-row, the only variable other than \(z\) having a positive coefficient is \(x_3\). So \(x_3\) is the only possible entering variable. But this forces \(x_1\) to be the leaving variable. Thus, we are forced to visit the basis that we started with. In other words, if we continue to make the same choices of entering and leaving variables as before, we will never stop.
Incidentally, if we had chosen \(x_7\) as the entering variable instead of \(x_4\) in the first iteration, we would detect unboundedness!
Cycling can be prevented if the choices for the entering and leaving variables are made carefully. Different schemes for making such choices lead to variants of the simplex method. One simple rule proposed by Robert Bland is to choose the variable with the smallest index whenever there is a choice.
Show that the cycling example is in fact unbounded.