Practice: Degenerate Basic Feasible Solutions

The columns are $A_1=(1,1{)}^{\mathsf{T}}$, $A_2=(1,0{)}^{\mathsf{T}}$, $A_3=(1,0{)}^{\mathsf{T}}$, $A_4=(0,1{)}^{\mathsf{T}}$, with $m=2$, $n=4$.

(a) Feasible, and basic. $3+0+0=3$ and $3+0=3$: both equalities hold, every component nonnegative. The only positive component is $x_1$, whose column $A_1$ is a single nonzero vector and therefore independent. So $\overline{x}$ is a basic feasible solution.

(b) Degenerate. One strictly positive component against $m=2$. Fewer than $m$, so yes.

(c) The bases. Only $A_1$ is forced in. The second member may be any column independent of $A_1$:

• $B=\{1,2\}$: , determinant $-1\ne 0$. Solving gives $x_1=3$, $x_2=0$.
• $B=\{1,3\}$: identical structure since $A_3=A_2$. Gives $x_1=3$, $x_3=0$.
• $B=\{1,4\}$: , determinant $1\ne 0$. Gives $x_1=3$, $x_4=0$.

Three bases, one point. In each the second basic variable sits at zero, which is the definition being met.

(d) Active sets. Both structural equalities are active, as always. Three nonnegativity restrictions are active, $x_2$, $x_3$ and $x_4$ are all zero. That is five active constraints in ${\mathbb{R}}^4$, where a vertex needs rank $4$. One more active constraint than necessary, which is the geometric statement of the same fact.

The error. The correspondence between extreme points and bases is not one-to-one. Every basic feasible solution is an extreme point, and every extreme point arises from at least one basis, but a degenerate corner, one with fewer than $m$ strictly positive components, arises from several.

Why that breaks both predictions. At a degenerate corner a basis swap can exchange one active constraint for another and land on the same point. The basis is new, the point is not, the step length is zero, and the objective is unchanged. So twelve iterations may have visited fewer than twelve corners, and the objective need not have improved at every step.

A concrete case. For $x_1+x_2+x_3=3$, $x_1+x_4=3$, $x\ge 0$, the point $(3,0,0,0)$ is described by $\{1,2\}$, $\{1,3\}$ and $\{1,4\}$. Moving between any two of those bases is an iteration that goes nowhere.

What the log might show. The same variable values at consecutive iterations with different basis index sets, and an objective column that does not change. That is stalling.

What it does not mean. Not a bug, and not an invalid answer. Occasional stalling is ordinary. The pathological case is cycling, where a sequence of zero-length steps returns to a basis already visited and repeats indefinitely; it is rare and is prevented by an anti-cycling rule such as Bland's, which selects entering and leaving variables by smallest index.

The correct general statement. Iterations bound corner visits from above, never below, and the objective is non-increasing for a minimisation rather than strictly decreasing.

What the tie predicts. Two basic variables reach zero at the same step length ${\theta }^{\ast }=7$. Only one of them can leave the basis; the other remains basic at value zero. So the next basic feasible solution has a basic variable at zero and is therefore degenerate, and this is known before computing the point.

Which leaves. Either tied row may be chosen. Both choices are valid and both lead to the same point; they differ only in which basis describes it, and the two resulting bases are among the several that name that corner.

The iteration after that. If the next entering variable has a positive direction component in the row whose basic variable sits at zero, that row's ratio is $0/u_i=0$. The minimum ratio is then $0$, so ${\theta }^{\ast }=0$: the entering variable enters at value zero, the leaving variable departs, and the point does not move. The objective falls by ${\theta }^{\ast }|{\overline{c}}_j|=0$, unchanged. That is stalling.

What to watch for on recurrence. Repeated zero-length steps are not in themselves an error, and usually the method escapes after one or two. The concern is cycling: a sequence of such steps returning to a basis already visited, which repeats forever and never terminates. The symptom in a log is the same variable values recurring across many iterations with the basis index set changing and the objective column flat.

The remedy. An anti-cycling rule, most simply Bland's: choose the entering variable with the smallest index among those with negative reduced cost, and break leaving ties by smallest index. This guarantees termination. The cost is that entering variables are chosen by index rather than by steepest improvement, so the method usually takes more iterations. A guarantee obtained at the cost of average-case speed.

Why this is the transfer. The definition of degeneracy is a count of positive components, met statically. Here it arrives as a tie in an arithmetic test, several steps before the count could be taken, and recognising it there is what makes the subsequent zero step legible rather than alarming.