This is Exercise 3.11 from Introduction to Linear Optimization by Bertsimas and Tsitsiklis.
Exercise 3.11 Construct an example with $n-m=3$ and a pivoting rule under which the simplex method will cycle.
Here $m$ and $n$ refers to the dimensions of the matrix $A$ in a standard form LP: $$ \begin{align} \min_{x\in\mathbb{R}^n}&\quad c^\top \\ \text{s.t.}&\quad Ax=b \\ &\quad x\ge 0 \end{align} $$ where $A\in\mathbb{R}^{m\times n}$ has full row rank, and $b\in\mathbb{R}^m$.
I tried to construct some examples of the following form: $$ \begin{align} \min_{x_1,...,x_6}&\quad c_1x_1+c_2x_2+c_3x_3 \\ \text{s.t.}&\quad x_4=a_{11}x_1+a_{12}x_2+a_{13}x_3 \\ &\quad x_5=a_{21}x_1+a_{22}x_2+a_{23}x_3 \\ &\quad x_6=a_{31}x_1+a_{32}x_2+a_{33}x_3 \\ &\quad x_1,...,x_6\ge 0 \end{align} $$ but have not succeeded so far, most likely because I do not know how to design the coefficients that lead to cycling.
I think that first designing the sequence of cycles and then computing the tableaus with the symbols $a_{ij}$'s (instead of concrete numbers) can lead to a certain set of conditions on the coefficients required for cycling to occur. However, the computation looks too intimidating. Is it possible to construct cycling examples through geometric intuition? In addition, what is so special about $n-m=3$?
Since we are focusing more on what types of coefficients $a_{ij}$ lead to cycling, let’s look at a two-dimensional model that I created so we can better understand what causes cycling in the first place as conditions for cycling is universal regardless of dimension:
$$\min z=x-2y$$ $$\text{subject to: }\qquad\qquad\qquad\qquad\qquad\text{ }$$ $$-2x+2y\le8$$ $$-x+y\le4$$ $$-\frac{1}{8}x+\frac{1}{2}y\le2$$ $$x,y\ge0$$
Let’s put this model into standardized form: $$\min z-x+2y=0$$ $$\text{subject to: }\qquad\qquad\qquad\qquad\qquad\text{ }$$ $$-2x+2y+s_1=8$$ $$-x+y+s_2=4$$ $$-\frac{1}{8}x+\frac{1}{2}y+s_3=2$$ $$x,y,s_1,s_2,s_3\ge0$$
In addition, let us denote each basis we visit as $B_n$ where $n$ denotes the current iteration we are on. Thus, our first tableau will look like:
\begin{array} {|c|c|} \hline Current Basis & BV & z & x & y & s_1 & s_2 & s_3 & RHS & Ratio Test \\ \hline & z & 1 & -1 & 2 & 0 & 0 & 0 & 0 & - \\ \hline & s_1 & 0 & -2 & 2 & 1 & 0 & 0 & 8 & \frac{8}{2}=4 \\ B_0 & s_2 & 0 & -1 & 1 & 0 & 1 & 0 & 4 & \frac{4}{1}=4 \\ & s_3 & 0 & -\frac{1}{8} & \frac{1}{2} & 0 & 0 & 1 & 2 & \frac{2}{\frac{1}{2}}=4 \\ \hline \end{array}
After pivoting the $y$ column, we’ll get: \begin{array} {|c|c|} \hline Current Basis & BV & z & x & y & s_1 & s_2 & s_3 & RHS & Ratio Test \\ \hline & z & 1 & 1 & 0 & -1 & 0 & 0 & -8 & - \\ \hline & y & 0 & -1 & 1 & \frac{1}{2} & 0 & 0 & 4 & \frac{4}{-1}=\infty \\ B_1 & s_2 & 0 & -2 & 0 & -\frac{1}{2} & 1 & 0 & 0 & \frac{0}{-\frac{1}{2}}=0 \\ & s_3 & 0 & \frac{3}{8} & 0 & -\frac{1}{4} & 0 & 1 & 0 & \frac{0}{\frac{3}{8}}=0 \\ \hline \end{array}
However, while there is a technique of saying zero divided by a negative number is “negative zero” and becomes infinity, but for our example we can say it’s just zero to simplify our calculations as cycling will still occur even if the last row is selected. Hence, we’ll always choose the first row with a zero minimum-ratio-test.
Thus, when we pivot the $x$ column we’ll get:
\begin{array} {|c|c|} \hline Current Basis & BV & z & x & y & s_1 & s_2 & s_3 & RHS & Ratio Test \\ \hline & z & 1 & 0 & 0 & -\frac{5}{4} & \frac{1}{2} & 0 & -8 & - \\ \hline & y & 0 & 0 & 1 & \frac{3}{4} & -\frac{1}{2} & 0 & 4 & \infty \\ B_2 & x & 0 & 1 & 0 & \frac{1}{4} & -\frac{1}{2} & 0 & 0 & 0 \\ & s_3 & 0 & 0 & 0 & -\frac{11}{32} & \frac{3}{16} & 1 & 0 & 0 \\ \hline \end{array}
After pivoting the $s_2$ column we’ll get: \begin{array} {|c|c|} \hline Current Basis & BV & z & x & y & s_1 & s_2 & s_3 & RHS & Ratio Test \\ \hline & z & 1 & 1 & 0 & -1 & 0 & 0 & -8 & - \\ \hline & y & 0 & -1 & 1 & \frac{1}{2} & 0 & 0 & 4 & - \\ B_3 & s_2 & 0 & -2 & 0 & -\frac{1}{2} & 1 & 0 & 0 & - \\ & s_3 & 0 & \frac{3}{8} & 0 & -\frac{1}{4} & 0 & 1 & 0 & - \\ \hline \end{array}
Take notice that $B_1=B_3$, and as such if we continue pivoting this way cycling will occur. Most importantly, notice the right-hand side values of our tableaus past the first iteration, and the ratio test of the first tableau, they’re all the same values! This is where cycling occurs, were more than one row has the same RHS/Ratio Test values.
Thus, for the three-dimensional problem you must construct a model that produces the same effect on the RHS/Ratio test to incur cycling within the Simplex Method.