Degenerate Basic Feasible Solutions

A degenerate basic feasible solution is a BFS where at least one basic variable is zero.

Definition

A BFS associated with basis $B$ is degenerate if

It is nondegenerate if $x_B>0$.

Meaning

In a nondegenerate BFS, exactly $n-m$ variables are zero: the nonbasic variables.

In a degenerate BFS, more variables are zero because at least one basic variable is also zero.

Geometric Meaning

Degeneracy means more constraints are active at a vertex than necessary to define it. The same vertex can correspond to several bases.

Simplex Consequence

Degeneracy can make the minimum ratio test return

Then the basis changes but the point may not move. This is called stalling.

Cycling

In rare cases, degenerate pivots can cause simplex to revisit a previous basis. Pivot rules such as the smallest-subscript rule avoid this.

Checklist

You should be able to spot zero basic variables and explain stalling.

See Also

• Basic Feasible Solutions
• Degeneracy in Simplex
• Minimum Ratio Test

Exam checkpoint

For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.