Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent.

$$ \left \{ x | Ax = b, x \geq 0 \right \} $$

(a) Suppose that two different bases lead to the same basic solution. Show that the basic solution is degenerate (has less than m non-zero entries).

(b) Consider a degenerate basic solution. Is it true that it corresponds to two or more distinct bases? Prove or give a counterexample.

(c) Suppose that a basic solution is degenerate. Is it true that there exists an adjacent basic solution which is degenerate? Prove or give a counterexample.

Solution

(a) I think it's obvious but how build the proof, the two different bases lead to the same basic solution, when the last entering variable cannot be increased at all because it's b value equals 0 therefore as result we have the same basic solution. But how to prove that?

(b) no, degenerate basic solution can correspond to one basis only as well. But how to prove that?

Addendum

I found great description of (a) and (b), but level of this text is much higher than I can apprehend. I will appreciate if someone could shed light on this explanation.

(a) every basic feasible solution is equivalent to an extreme point. However, there may exist more than one basic corresponding to the same basic feasible solution or extreme point. Case of degeneracy corresponds to that of a extreme point at which some $r > p \equiv n- m $ defining hyperplanes from $x\geq 0$ are binding. Hence, for any associated basis, $(r-p)$ of the $X_{B}$ - variables area also zero. Consequently, the number of positive variables is $q = m-(r-p)<m$. In this case, each possible choice of a basis $B$ that includes the columns of these q positive variables represents this point. Clearly, if there exists more than one basis representing an extreme point, then this extreme point is degenerate

(b) Consider example $$x_{1} + x_{2} + x_{3} = 1$$

$$-x_{1} + x_{2} + x_{3} = 1$$

$$x_{1}, x_{2}, x_{3} \geq 0$$

Consider the solution $\bar{x}=(0,1,0)$. Observer that this is an extreme point or a basic feasible solution with a corresponding basis having $x_{1}$ and $x_{2}$ as basic variables. Moreover, this is a degenerate extreme point. There are four defining hyperplanes binding at $\bar{x}$. Moreover, there are three ways of choosing three linearly independent hyperplanes from this set that yield $\bar{x}$ as the (unique) solution. However, the basis associated with $\bar{x}$ is unique. Consider a degenerate basic variable ${x_{B}}_{r}$ (with $\bar{b}_{r}=0$), which is such that $Ax=b$ does not necessarily imply that ${x_{B}}_{r}=0$. Given that such a variable exists, we will construct another basis representing this point. Let $x_{k}$ be some component of $x_{N}$ that has a nonzero coefficient $\theta_{r}$ in the row corresponding to ${x_{B}}_r$. Note that $x_{k}$ exists. Then consider a new choice of $(n-m)$ nonbasic variables given by ${x_{B}}_{r}$ and $x_{N-k}$, where $x_{N-k}$ represents the components of $x_{N}$ other than $x_{k}$. Putting ${x_{B}}_{r}= 0$ and $x_{N-k}=0$ above uniquely gives $x_{k}=\frac{\bar{b}_{r}}{\theta_{r}}=0$ from row $r$, and so ${x_{B}}_{i} = \bar{b}_{i}$ is obtained as before from the other rows. Hence, this corresponds to an alternative basis that represents the same extreme point. Finally, note that if no degenerate basic variable ${x_{B}}_{r}$ of this type exists, then there is only one basis that represents this extreme point.

Solution 1:

(Most of this was written before the recent addendum. It addresses the OP's original question, not the addendum.)

(a) Suppose we have distinct bases $B_1$ and $B_2$ that each yield the same basic solution ${\bf x}$. Now, suppose (we're looking for a contradiction) that ${\bf x}$ is nondegenerate; i.e., every one of the $m$ variables in ${\bf x}$ is nonzero. Thus every one of the $m$ variables in $B_1$ is nonzero, and every one of the $m$ variables in $B_2$ is nonzero. Since $B_1$ and $B_2$ are distinct, there is at least one variable in $B_1$ not in $B_2$. But this yields at least $m+1$ nonzero variables in ${\bf x}$, which is a contradiction. Thus ${\bf x}$ must be degenerate.

(b) No. The counterexample linked to by the OP involves the system $$ \begin{align} x_1 + x_2 + x_3 = 1, \\ -x_1 + x_2 + x_3 = 1, \\ x_1, x_2, x_3 \geq 0. \end{align}$$
There are three potential bases in this system: $B_1 = \{x_1, x_2\}$, $B_2 = \{x_1, x_3\}$, $B_3 = \{x_2, x_3\}$. However, $B_3$ can't actually be a basis because the corresponding matrix $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ isn't invertible. $B_1$ yields the basic solution $(0,1,0)$, and $B_2$ yields the basic solution $(0,0,1)$. Both of these are degenerate, but there is only one basis corresponding to each.

(c) No. Look at the system $$ \begin{align} x_1 + x_2 = 1, \\ x_2 + x_3 = 1, \\ x_1, x_2, x_3 \geq 0. \end{align} $$ The basic solution $(0,1,0)$ corresponds to bases $\{x_1, x_2\}$ and $\{x_2, x_3\}$. The only other basis is $\{x_1, x_3\}$, which implies that the only other basic solution is $(1,0,1)$. Thus the degenerate basic solution $(0,1,0)$ is not adjacent to another degenerate basic solution.

Say there are $n$ total variables in the problem: $x_1, x_2, \ldots, x_n$. Every basis $B$ consists of some $m$ of these variables. The basic solution ${\bf x}$ corresponding to a given basis $B$ has the other $n-m$ variables equal to $0$. (Setting these to $0$ is partly how you determine the value of ${\bf x}$; see, for instance, the examples above). If ${\bf x}$ is degenerate it might have some of the variables in $B$ equal to $0$, too, but the point in terms of the argument is that ${\bf x}$ can have no more than $m$ nonzero variables.

Now, suppose $B_1$ and $B_2$ are distinct and each have $m$ nonzero variables, yet both correspond to ${\bf x}$. Let's say $B_2 = \{x_1, x_2, \ldots, x_m\}$. Since $B_1$ and $B_2$ are distinct, $B_1$ has at least one variable that's not in $B_2$. Let's say this variable is $x_{m+1}$. But since every variable in $B_1$ and $B_2$ is nonzero, that means that $x_1, x_2, \ldots, x_m, x_{m+1}$ are all nonzero. However, $B_1$ and $B_2$ both correspond to ${\bf x}$, which means that there are at least $m+1$ nonzero variables in ${\bf x}$. That cannot happen for a basic solution, and so we have a contradiction.

Solution 2:

I have a slightly different proof for part (a). If the bases, $B$ and $B'$ are distinct, but correspond to the same basic feasible solution $x_b$ ($x_b$ corresponds to the vector of basic variables), then, by definition $Bx_b=b$ and $B'x_b=b$. Hence, $(B-B')x_b=0$. Since $B,B'$ are distinct, $dim(B-B') \geq 1$. Therefore, by rank-nullity theorem, $dim(x_b) \leq (m-1)$, which implies that at least one of the components of $x_b$ is zero.