It previous blog, we know how to do a typical iteration in Simplex algorithm, but we will got trouble when the degeneracy happens, which will turn out that cycling can occur in our Simplex. In this blog, we will show some ways to avoid cycling in Simplex, but please note that these ways cannot make Simplex to be polynomial algorithm.

At some basis change, we have $\theta^* = 0$, which indicates that while the basis changes, we are not moving corners in the polyhedron. If cycling happens, all following successive bases correspond to the same b.f.s.

We are going to discuss two anticycling rules which can guarantee the simplex algorithm to terminate, thus extending Termination Theorem to degenerate cases.

The lexicographic pivoting rule

Definition

Definition: A vector $\bar{u} \in \mathbb{R}^n$ is said to be lexicographically larger than another vector $\bar{v} \in \mathbb{R}^n$ if $\bar{u} \neq \bar{v}$ and the first nonzero component of $\bar{u} - \bar{v}$ is positive. We write $\bar{u} \overset{L}{>} \bar{v}$ to denote that $\bar{u}$ is lexicographically larger than $\bar{v}$. When $\bar{w} \overset{L}{>} \bar{0}$, we say that $\bar{w}$ is lexicographically positive.

Examples: \(\begin{bmatrix} 0 \\ 2 \\ 3 \\ 1 \end{bmatrix} \overset{L}{>} \begin{bmatrix} 0 \\ 2 \\ 1 \\ 4 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 0 \\ 2 \\ -1 \\ -4 \end{bmatrix} \overset{L}{>} \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\0 \end{bmatrix}\)

Definition: A vector $\bar{u} \in \mathbb{R}^n$ is said to be lexicographically smaller than another vector $\bar{v} \in \mathbb{R}^n$ if $\bar{u} \neq \bar{v}$ and the first nonzero component of $\bar{u} - \bar{v}$ is negative. We write $\bar{u} \overset{L}{<} \bar{v}$ to denote that $\bar{u}$ is lexicographically smaller than $\bar{v}$.

Lexicographic pivoting rule:

1. Choose an entering variable $x_j$ arbitrarily, as long as the reduced cost $\tilde{c}_j$ is negative. Let $\mu = B^{-1} \bar{A}_j$ be the $j^{th}$ column of the simplex tableau.

2. For each $i$ with $\mu_i > 0$, divide the $i^{th}$ row of the tableau (including the entry in the zeroth column) by $\mu_i$; and choose the lexicographically smallest row. If row $\ell$ is lexicographically smallest, then the $\ell^{th}$ basic variable $x_{B(\ell)}$ exits the basis.

Note: The lexicographic pivoting rule always leads to a unique choice for the exiting variable.

Otherwise, two of the rows in the tableau would have to be proportional. But if two rows of the matrix $B^{-1}A$ are proportional, the rank of the matrix $B^{-1}A$ is strictly smaller than the number of rows of the matrix $B^{-1}A$, which contradicts our standing assumption that $A$ has linearly independent rows.

Effectivity of Lexicographic rule

The following theorem tell us the zeroth row will increases lexicographically, which leads to that the Simplex will never get into cycling.

Theorem Suppose that the simplex algorithm starts with all rows in the simplex tableau are lexicographically positive (except zeroth row). ($*$)

Then, provided the lexicographic pivoting rule is followed,

1. Every row of the simplex tableau, other than the zeroth row, remains lexicographically positive throughout the algorithm;
2. The zeroth row strictly increases lexicographically at each operation;
3. And the simplex method terminates after a finite number of iterations.

Proof.

(1) Suppose that $x_j$ enters the basis and that the pivot row is the $\ell^{th}$ row. According to the lexicographic pivoting rule, that means that $\mu_{\ell} > 0$ and $\frac{\ell^{th} \text{ row}}{\mu_\ell} \overset{L}{<} \frac{i^{th} \text{ row}}{\mu_{i}}$ if $\ell \neq i$ and $\mu_i > 0$.

Let’s perform the elementary row operation of the pivot:

• If $\ell^{th}$ row with $i \neq \ell$ has $\mu_i \leq 0$, then

\[(\text{new } i^{th} \text{ row}) = (\text{old } i^{th} \text{ row}) - \frac{\mu_i}{\mu_{\ell}} (\text{old } \ell^{th} \text{ row}) \overset{L}{>} \bar{0}\]

(Note, here $- \frac{\mu_i}{\mu_{\ell}} \geq 0$, $(\text{old } i^{th} \text{ row})$ and $(\text{old } \ell^{th} \text{ row})$ are lexicographically positive by assumption, so the new $i^{th}$ row is lexicographically positive).

• If $i^{th}$ row with $i \neq \ell$ has $\mu_i > 0$, then

\[\frac{\ell^{th} \text{ row}}{\mu_\ell} \overset{L}{<} \frac{i^{th} \text{ row}}{\mu_{i}} \Leftrightarrow \mu_i \frac{\ell^{th} \text{ row}}{\mu_\ell} \overset{L}{<} (i^{th} \text{ row})\]

which implies

\[\bar{0} \overset{L}{<} (i^{th} \text{ row}) - \frac{ \mu_i}{\mu_\ell} (\ell^{th} \text{ row})\]

Hence, we can get \((\text{new } i^{th} \text{ row}) = (\text{old } i^{th} \text{ row}) - \frac{\mu_i}{\mu_{\ell}} (\text{old } \ell^{th} \text{ row}) \overset{L}{>} \bar{0}\)

• For the pivot row:

\[(\text{new } i^{th} \text{ row}) = \frac{1}{\mu_{\ell}} (\text{old } \ell^{th} \text{ row}) \overset{L}{>} \bar{0}\]

Thus, all rows of the simplex tableau remain lexicographically positive.

(2) The zeroth row strictly increases lexicographically at each operation.

Note that the reduced cost of the variable $x_j$ entering the basis is negative, so we have

\((\text{new } i^{th} \text{ row}) = (\text{old } i^{th} \text{ row}) - \frac{\tilde{c}_i}{\mu_{\ell}} (\text{old } \ell^{th} \text{ row}) \overset{L}{>} \bar{0}\) Thus, we are adding to the 0$^{th}$ row is a lexicographically positive vector, which implies that the zeroth row increases lexicographically.

(3) Since the zeroth row increases lexicographically at each iteration, it never returns to a previous value. Since the zeroth row is determined completely by the current basis, no basis can be repeated twice and the simplex algorithm must terminate after a finite number of iterations. $\square$

Supplement about Assumption

However, in order to apply the lexicographic pivoting rule, an initial tableau with lexicographically positive rows is required. If the rows of the initial simplex tableau are not lexicographically positive, we can rename the variables so that the basic variables are the first $m$ ones: $x_1, x_2, x_3, …, x_m$. This amounts to reordering the columns of the tableau so that the first $m$ columns of $B^{-1}A$ form the identity $m×n$ matrix. (We can reorder the variables to guarantee the all rows in initial tableau (expect zeroth row) are positive).

Bland’s pivoting rule

Bland’s smallest subscript pivoting rule is another rule known to prevent cycling from occurring and thereby guaranteeing that the simplex algorithm terminates after a finite number of iterations.

Bland’s smallest subscript pivoting rule:

1. Find the smallest index $j$ for which the reduced cost $\tilde{c_j}$ is negative and have the variable $x_j$ enter the basis.
2. Out of all variables $x_i$ that are candidates for choosing an exiting variable, select the one with the smallest index $i$.

We don’t show the proof here.