📂Optimization

Simplex Method Cycling

Definition

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

For the matrix $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$, let us say the linear programming problem is expressed in the equation form as above, and for $i = 1 , \cdots , m$, let us represent its dictionary as follows. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$

If for some $i \in \mathcal{B}$, $b_{i} = 0$ is true, this dictionary is said to be Degenerate, and due to this, the phenomenon where there is no progress in the simplex method is called Cycling¹.

Explanation

Degenerate…?

Searching on Naver, Degenerate is translated into deteriorate, decadent, degenerate, regressive, atrophied, etc. Naturally, the most famous usage in STEM fields is in quantum mechanics regarding degeneracy, where two different wave functions have the same eigenvalue, and it is sometimes used in linear algebra when a vector can be represented as a linear combination of other vectors. Accepting the English term as it is, it is quite logical to call it Degenerate when $b_{i} = 0$. The problem is that it doesn’t match the meaning of degeneracy in Korean translation at all. It might have been possible to find a completely different expression, but thinking about it, since it implies that the simplex method is not working properly, degenerate is not entirely the wrong term, so it was euphemistically translated to degenerate.

Example

$$ \begin{matrix} \text{Maximize} & & & & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 0 \\ & & 1_{2} & & & \le & 2 \end{matrix} $$

For example, writing down the linear programming problem above as a dictionary will look like this. $$ \begin{matrix} \zeta & = & & & & & & x_{2} \\ x_{3} & = & & & & x_{1} & - & x_{2} \\ x_{4} & = & & 2 & - & x_{1} & & \end{matrix} $$

At this point, for $i = 3$, if $b_{i} = 0$ is true, swapping variables does not change the objective value, and it goes around in circles. In other words, for the $t$-th dictionary being $D_{t}$, there exists some $k \in \mathbb{N}$ that satisfies the following. $$ D_{t} = D_{t+k} $$

This may seem like a very simple example, but it’s impossible to tell when any cycling might occur with a dictionary as large as $A$. For example, substituting variables may serendipitously fit together such that $b_{i_{1}} = -b_{i_{2}}$ and $0$ occur. It’s not particularly difficult to detect this programmatically, but the problem is how to navigate through it.

Solution: Bland’s Rule

If the entering variable and leaving variable are chosen from $\mathcal{N}$ and $\mathcal{B}$ respectively based on the smallest index, it prevents cycling. This selection method is called Bland’s Rule.

Conversely, when the simplex method does not terminate, it can be guaranteed through the following theorem that the dictionary has entered a cycle.

Theorem

If the simplex method does not terminate, then the dictionary has entered a cycle.

Proof

Consider finding all cases where a basic feasible solution is possible in a linear programming problem using a greedy algorithm, i.e., in the worst possible way we can imagine. The number of cases to find $n$ basic variables out of $n+m$ variables is $$ \binom{n+m}{n} = {{ (n+m)! } \over { n!m! }} $$ which is a significant number but, nonetheless, finite. Calculating all these cases would inevitably complete the optimization, so if the simplex method does not stop, it means it has entered a cycle.

■

Fundamental Theorem of Linear Programming

This theorem is used in the proof of the Fundamental Theorem of Linear Programming.