Degeneracy in Simplex Algorithm

Question

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not every unique basic feasible solution of the polyhedron is represented by a unique basis.
This is detected in Simplex Algorithm when one of the components of the basic variable vector has a value of zero, that is: $B^{-1} * b$ = $(...,0,..)^{t}$ with a zero at the $k^{th}$ position for a basic variable $x_{k}$. (Hence, having an extra binding constraint at that point).

Here is my Question: If this component of the basic variable vector (whose value is zero and is in the basis) was a slack variable originally introduced to formulate the problem in standard form (to convert inequalities to equalities and get started with simplex), does the definition of degeneracy still apply? and is this still defined as a degenerate basic feasible solution? and why?

I appreciate your help.

Answer 1

Yes to both questions. I first start with a simple example, then ellaborate the definition of degeneracy.

A simple degenerate LPP

To illustrate this problem, let me use this example.

$\max x$ subject to

\begin{align} \color{blue}{x+y}&\le\color{blue}{1}\\ \color{red}x\phantom{+y}&\le\color{red}1\\ x,y&\ge0 \end{align}

Obviously, exactly one of the blue and red constraints is redundant, so this LPP has degenerate solution.

We transform it to the standard form by adding slack variable $\color{blue}{s_1}, \color{red}{s_2}$.

$\max x$ subject to

\begin{align} \color{blue}{x+y+s_1\phantom{+s_2}}&=\color{blue}{1}\\ \color{red}{x\phantom{+y+s_1}+s_2}&=\color{red}1\\ x,y,\color{blue}{s_1},\color{red}{s_2}&\ge0 \end{align}

Thus, each of $x=0,y=0,\color{blue}{s_1=0},\color{red}{s_2=0}$ corresponds to a line which bounds the feasible region.

• If we choose $x,\color{blue}{s_1}$ as basic variables, then the basic solution is $x_B=(x,\color{blue}{s_1})=(1,\color{blue}0)$.
• If we choose $x,\color{red}{s_2}$ as basic variables, then the basic solution is $x_B=(x,\color{red}{s_2})=(1,\color{red}0)$.
• If we choose $x,y$ as basic variables, then the basic solution is $x_B=(x,y)=(1,0)$.

Therefore, in the first prompt, the condition (zero-valued slack variable $s_i$ in the basic variable $x_B$) is irrelevant to the degeneracy of $x_B$. The definition of degeneracy still applies to $x_B=(1,\color{blue}0)$ and $x_B=(1,\color{red}0)$.

• Geometric interpretation/intuition: Three lines (constraints) intersect at the point $(1,0)$, so one line is redundant. We use the word degenerate to capture this phenomenon.
• Use the definition of degenerate solution: In each case, we have a zero entry in the basic solution $x_B$, so it should be degenerate.

Theoretical stuff

Suppose $\mathrm{rank}(B)=n$. You have at most $n-1$ variables with non-zero value in the current solution. The degeneracy of a solution just depends on the presence of zero entry in the basic solution $B^{-1}b$. It doesn't matter whether the basic variable is a slack variable or not.