Degenerate Basic Feasible Solutions

A corner with more constraints through it than it strictly needs looks unremarkable on a drawing. To an algorithm expecting every basis swap to move somewhere, it is a trap.

You have already met the fact in passing: the correspondence between corners and bases is not one-to-one, because a corner with too few positive components can be described by several bases. That was stated where the correspondence was established, and stating it is not the same as being able to recognise it.

The reason to give it a unit is that the recognition is separable. A learner who computes basic feasible solutions accurately can still fail to notice that one of them is degenerate, and the consequence, a basis change that does not move, looks like a bug in the arithmetic rather than a property of the geometry.

This unit assumes you can construct a basic solution, take an active set, and state the correspondence between extreme points and bases.

The picture above explains where degeneracy comes from. What it does not explain is why an algorithm cares.

Simplex expects each swap to be a move. It raises a nonbasic variable and stops when the first basic variable hits zero. At a degenerate corner one is already there, so the permitted step is zero: the basis changes, the point does not, the objective does not. From inside the method this is indistinguishable from progress until it happens again.

The termination argument is what breaks. Simplex terminates because the objective strictly improves at every step, so no basis can repeat, and there are finitely many. A zero-length step improves nothing, a basis can recur, and the method can cycle indefinitely between bases naming one point. Bland's rule and the lexicographic rule restore termination by constraining which column enters and which leaves, not by removing the degeneracy.

It is the ordinary case, not a pathology. Any redundant constraint through an existing corner produces one, and symmetric formulations produce many. The practical effect is mild, since solvers handle it, but it explains why iteration counts and corner counts differ, and why a solver can report many iterations on a small problem.

The canonical statement defines degeneracy and gives both readings. What it does not say is what degeneracy costs an algorithm, which is the only reason the unit exists.

A basis swap need not move. The simplex method advances by exchanging one basis column for another and stepping as far as the ratio test allows. When a basic variable already sits at zero, that permitted step is zero: the basis changes, the point does not, and the objective is unchanged. An iteration has occurred and no progress has been made.

Which is why termination needs an argument. The usual proof that simplex terminates counts corners and observes that the objective strictly improves, so no corner repeats. Degeneracy breaks the premise. A sequence of degenerate pivots can return to a basis already visited, and the method cycles. Anti-cycling rules, Bland's among them, restore termination by fixing the entering and leaving choices rather than by removing the degeneracy.

It is common, not exotic. Any constraint that happens to pass through a corner already determined by others produces one, and redundant or symmetric formulations produce them routinely. The practical consequence is not that a solver fails but that an iteration count stops being a measure of progress.

Take

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

A nondegenerate point. Basis $\{2,4\}$ gives $x_2=2$, $x_4=2$, so $x=(0,2,0,2)$. Two positive components, and $m=2$. Not degenerate, and this basis is the only one describing this point.

A degenerate point. Take $x=(2,0,0,0)$. Check: $2+0+0=2$ and $2+0=2$, all components nonnegative, feasible. Only one component is positive, and . Degenerate.

Its several bases. Only $A_1$ is forced into the basis. The second member may be $A_2$, or $A_3$, or $A_4$. Each is independent of $A_1$, and each yields the same point $(2,0,0,0)$:

• $B=\{1,2\}$: solve $x_1+x_2=2$, $x_1=2$ $\Rightarrow$ $x_1=2$, $x_2=0$.
• $B=\{1,3\}$: solve $x_1+x_3=2$, $x_1=2$ $\Rightarrow$ $x_1=2$, $x_3=0$.
• $B=\{1,4\}$: solve $x_1=2$, $x_1+x_4=2$ $\Rightarrow$ $x_1=2$, $x_4=0$.

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

The active-set view. At $(2,0,0,0)$ the two structural equalities are active, as always, and three nonnegativity restrictions are active as well, $x_2$, $x_3$ and $x_4$ are all zero. In ${\mathbb{R}}^4$ a vertex needs rank $4$; here the active normals number five. One more than necessary, which is the geometric statement of the same fact.

Problem. A simplex iteration has basis $B=\{3,4\}$ with $x_3=6$, $x_4=6$, an entering variable $x_1$ with direction $u=(2,2{)}^{\mathsf{T}}$ and ${\overline{c}}_1=-4$. Carry out the iteration and the one after it.

Goal. See where degeneracy enters and what it costs.

Relevant principle. A tie in the minimum ratio leaves a basic variable at zero, which is degeneracy; a subsequent step of length zero moves the basis without moving the point.

Step 1: the ratio test. Both components of $u$ are positive, so both rows qualify:

A tie. ${\theta }^{\ast }=3$, attained in both rows.

Step 2: choose a leaving variable. Either is valid. Take $x_3$ to leave.

Step 3: the new point. $x_1=3$; the remaining basic variable becomes $x_4=6-3(2)=0$. So $x=(3,0,0,0)$ with basis $\{1,4\}$, and the objective fell by $3\times 4=12$.

Step 4: notice what happened. $x_4$ is a basic variable sitting at zero. Only one component of the point is positive, against $m=2$. The new basic feasible solution is degenerate, and it was the tie that produced it, since both variables reached zero together while only one could leave.

Step 5: the next iteration. Suppose $x_2$ now enters with ${\overline{c}}_2=-1$ and direction $u^{\prime }=(1,1{)}^{\mathsf{T}}$ against the basis $\{1,4\}$. The ratio test:

The minimum is $0$. So ${\theta }^{\ast }=0$, $x_4$ leaves, $x_2$ enters at value zero.

Step 6: the new point. $x_2=0$, and $x_1=3-0(1)=3$. The point is $(3,0,0,0)$, exactly where it was. The basis changed from $\{1,4\}$ to $\{1,2\}$; the objective fell by $0$.

What this iteration accomplished. Nothing, in terms of position or value. It was not wasted in principle, the new basis may admit an improving direction the old one did not, but the step itself moved nowhere. That is stalling.

The danger. If a sequence of such steps returns to a basis already visited, the method cycles and never terminates. Bland's rule, choosing the entering and leaving variables by smallest index, guarantees this cannot happen, at the cost of usually taking more iterations.

Check. $(3,0,0,0)$ against the constraints of Step 3's system: the point satisfies them, every component is nonnegative, and exactly one is positive. Still feasible, still degenerate.

Not degeneracy: nonbasic variables at zero. Every basic solution has at least $n-m$ zero components, because that many variables were set to zero to make the system square. That is the construction working normally. Degeneracy is a basic variable at zero, which is one more zero than the construction requires.

Not degeneracy: several optimal solutions. Multiple optima mean several distinct points attain the best value, and come from the objective being parallel to a binding constraint. Degeneracy means several bases describe one point, and is a property of the constraints alone. A program can have either, both, or neither, and the two are routinely confused because both involve the word 'multiple'.

Not an error: a degenerate optimum. If the method terminates at a degenerate basic feasible solution with all reduced costs nonnegative, that point is optimal. Degeneracy makes the route there less direct; it does not cast doubt on the destination.

Not a cause of degeneracy: the objective. Degeneracy is determined by $A$, $b$ and the sign restrictions. Changing the objective changes which corner is optimal and changes nothing about which corners are degenerate.

Not the same as cycling. Stalling, a zero-length step, is common and usually harmless. Cycling is a closed loop of stalls, is rare, and is fatal without an anti-cycling rule. Every cycle is made of stalls; almost no stall belongs to a cycle.

The correspondence between extreme points and bases runs one way more strongly than the other, and reading it as a pairing produces a specific wrong prediction: that changing basis always moves you somewhere new.

What is true in both directions. Every basic feasible solution is an extreme point, and every extreme point arises from at least one basis.

What is not true. That each extreme point arises from exactly one. 'At least one' is the correct phrase and the words are load-bearing.

The counterexample, concretely. For the system of the example above, the point $(2,0,0,0)$ is described by $\{1,2\}$, by $\{1,3\}$, and by $\{1,4\}$. Three bases. One point. Each satisfies the definition of a basis, and each construction yields the same four numbers.

The wrong prediction it licenses. A learner holding the pairing view expects every iteration of the simplex method to arrive at a new corner with a strictly better objective, and therefore expects the iteration count to bound the number of corners visited. Both expectations fail at a degenerate corner: the basis changes, the point does not, and the objective is unchanged.

How to tell which situation you are in. Count the strictly positive components against $m$. Fewer than $m$ means degenerate, means several bases, means a swap might not move you. It is a count you can take in a moment, and it explains a class of behaviour that otherwise reads as the algorithm malfunctioning.

The reliable statement. Extreme points and bases are related by a map from bases onto extreme points. It is surjective and it is not injective, and degeneracy is precisely the failure of injectivity.

1. For $x_1+x_2+x_3=3$, $x_1+x_4=3$, $x\ge 0$, show that $(3,0,0,0)$ is a basic feasible solution and decide whether it is degenerate. How many bases describe it?

2. In the same system, find a basic feasible solution that is not degenerate and say how many bases describe that one.

3. A ratio test produces ratios $5$, $5$, and $8$. What can you say about the basic feasible solution reached after the step, before computing it?

4. Explain why a step of length zero can still be useful to the algorithm, even though the point does not move.

5. A colleague says a program has a degenerate solution because two different corners gave the same objective value. What have they described instead, and what would degeneracy have looked like?

A basic feasible solution is degenerate when fewer than $m$ of its components are strictly positive, equivalently, when a basic variable sits at zero.

Three readings of one fact. Algebraically, several bases describe the same point, because the columns of the zero components can complete the basis in more than one way. Geometrically, more constraints are active at the point than are needed to determine it, three lines through one crossing rather than two. Algorithmically, a basis change can leave the point where it was.

The signal to watch for is a tie in the minimum ratio test: two basic variables reaching zero together, only one of which can leave. The consequence is a zero-length step, which is stalling, and in rare cases a closed loop of them, which is cycling and requires an anti-cycling rule to prevent.

Degeneracy is not an error and does not invalidate a solution. A degenerate optimum is still an optimum. It is also not the same as multiple optima, which concern several distinct points attaining one value and depend on the objective, while degeneracy depends only on the constraints.

The count is the diagnostic, and it takes a moment: positive components against $m$.