Why does degeneracy occur in linear programming?

What Is Degeneracy in Linear Programming?

A basic feasible solution (BFS) is degenerate when one or more of its basic variables take the value zero.

In other words, simplex has selected a variable to enter the basis, but the resulting solution does not move to a new point — the algorithm stays at the same corner of the feasible region.

This leads to:

• zero-valued pivots
• no improvement in the objective
• potential stalling or cycling

Why Does Degeneracy Occur?

1. More than m constraints intersect at the same point

In an LP with m constraints, a BFS normally lies at the intersection of exactly m binding constraints. Degeneracy occurs when more than m constraints are tight at the same point.

2. A basic variable becomes zero

When solving the system of equations for the BFS, one or more basic variables may equal zero. This creates a degenerate pivot.

3. Redundant or nearly parallel constraints

If constraints overlap or nearly overlap, they can force simplex to select a basis that does not change the solution point.

4. Geometry of the feasible region

Degeneracy is a geometric phenomenon — the feasible region has a “sharp” corner where multiple constraints meet.

How to Detect Degeneracy in the Simplex Method

• A basic variable equals zero in the BFS.
• Minimum ratio test gives a tie (multiple constraints hit zero simultaneously).
• Pivot element is zero or extremely small.
• Objective value does not improve after a pivot (stalling).
• Simplex revisits the same basis (cycling risk).

Rules like Bland’s Rule prevent cycling by enforcing a consistent pivot selection order.

Numerical Example

Consider the LP:

\[ \text{Max } z = x_1 + x_2 \]

\[ \begin{aligned} x_1 + x_2 &\le 4 \\ x_1 &\le 2 \\ x_2 &\le 2 \\ x_1, x_2 &\ge 0 \end{aligned} \]

The point (2,2) satisfies all three constraints, but only two are needed to define a BFS. The extra constraint makes the BFS degenerate.

Simplex may pivot but remain at (2,2), causing stalling.