Degenerate Basic Feasible Solutions

A basic feasible solution is degenerate when fewer than $m$ of its components are strictly positive. Geometrically, more constraints are active at that corner than are needed to pin it down; algebraically, several different bases describe the same point. The practical consequence is that a basis change can leave the point where it was, which is how the simplex method stalls and, in rare cases, cycles.

Definition

Let $x$ be a basic feasible solution of $A x = b$ , $x \geq 0$ , with $A$ of rank $m$ .

$x$ is degenerate when strictly fewer than $m$ of its components are positive, equivalently, when at least one basic variable takes the value zero.

The algebraic consequence. A basis needs $m$ columns, but only the columns of strictly positive components are forced into it. If just $k < m$ components are positive, the remaining $m - k$ basis members may be chosen from the columns whose components are zero, and there may be several valid choices. Each yields the same point. So a degenerate corner corresponds to more than one basis.

The geometric consequence. At a nondegenerate corner in $n$ dimensions, exactly $n$ independent constraints are active, just enough to pin the point down. At a degenerate corner, more constraints are active than are needed: an extra constraint passes through the same point. In two variables this is three lines meeting at a single point rather than two.

The algorithmic consequence. The simplex method changes basis expecting to move. At a degenerate corner it may change basis and arrive at the same point, taking a step of length zero. Repeated zero steps are stalling; a closed loop of them is cycling, which terminates nothing and requires an anti-cycling rule such as Bland's rule to prevent.

Formal statement

$x$ is a degenerate basic feasible solution when $| {j : x_{j} > 0} | < m$ . Equivalently, at $x$ the number of independent active constraints exceeds $n$ . A tie in $θ^{*} = min_{i : u_{i} > 0} x_{B (i)} / u_{i}$ produces one; $θ^{*} = 0$ means the step is zero and the point is unchanged.

Assumptions and scope

Degeneracy is a property of a point together with the system describing it, not of the feasible region alone. Adding a redundant constraint through an existing corner introduces degeneracy without changing the region at all.
A degenerate basic feasible solution is still an extreme point and still a legitimate answer. Degeneracy is not an error and does not invalidate the solution.
Several bases describing one point does not mean several points. The correspondence between extreme points and bases is onto but not one-to-one, and only in that direction.
A tie in the minimum ratio test produces a degenerate solution at the next step. Either tied row may be chosen; both choices are valid and lead to the same point.
Stalling is common and harmless in itself; cycling is rare and fatal. Anti-cycling rules such as Bland's rule guarantee termination, at the cost of choosing entering variables by index rather than by steepest improvement.

Worked material

Example

A degenerate corner and a nondegenerate one

Take

\begin{aligned} x_{1} + x_{2} + x_{3} & = 2, \\ x_{1} + x_{4} & = 2, \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0, \end{aligned}

with $m = 2$ and columns $A_{1} = (1, 1)^{T}$ , $A_{2} = (1, 0)^{T}$ , $A_{3} = (1, 0)^{T}$ , $A_{4} = (0, 1)^{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 $1 < m = 2$ . 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 $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.

Non-example

What degeneracy is not

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.

Contrast

One corner, several bases

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.

Common errors

Common misconception

Every basic feasible solution corresponds to exactly one basis, so two different bases always identify two different corners of the feasible region.

Degenerate Basic Feasible Solutions

Assumptions and scope

Worked material

A degenerate corner and a nondegenerate one

What degeneracy is not

One corner, several bases

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history