Degeneracy¶

Definition¶

A degenerate basic feasible solution has at least one basic variable equal to zero. A degenerate pivot has a zero step length (the minimum-ratio test gives $\theta=0$ $0$ , so the entering variable stays at zero) and can change the basis without changing the solution vector or objective value.

Interpretation¶

Degeneracy happens when a corner of the feasible region lies on more constraint lines than are needed to fix it. In two variables two lines suffice; when a third passes through the same point, more variables are zero there than a basic solution sets to zero, so some basic variable takes the value $0$ .

A feasible region where three constraint lines pass through the same corner (20, 60), so a basic variable there takes the value 0.

At $(20,60)$ the lines $2x_s+x_t=100$ $100$ , $x_s+x_t=80$ and $x_t=60$ meet, so $s_1=s_2=s_4=0$ $0$ . The augmented form has six variables and four equations, so only two variables are nonbasic and at least one of the three zero slacks is basic. Any two of $s_1,s_2,s_4$ can be the nonbasic pair, and each choice gives the same point: one corner, three bases.

In the simplex method, degeneracy shows up in the minimum-ratio test. A tie means that two basic variables reach zero at the same moment; only one leaves, and the other stays basic with value $0$ . If a later ratio test gives $\theta=0$ $0$ , the pivot exchanges variables without moving: the point and $z$ stay the same.

Being basic is a matter of the chosen basis, not of the value, so a basic variable can be zero. At a degenerate corner the optimality test can even show a negative coefficient although the point is optimal; further degenerate pivots can then reach a basis that passes the test. The real risk is cycling, described in the Examples.

Key Results¶

A tie for the minimum ratio can produce a degenerate basic feasible solution.
Zero ratios must be considered when the pivot-column coefficient is positive.
The basic/nonbasic distinction is determined by the basis, not by whether a value is zero.

Examples¶

At the illustrated point $(20,60)$ , $s_1=s_2=s_4=0$ $0$ . The augmented model has two nonbasic variables, so at least one of these three zeros is basic. Without an anti-cycling rule (a tie-breaking rule for the entering and leaving variables, such as Bland's smallest-index rule), repeated degenerate pivots can cause simplex to cycle, that is, return to an earlier basis and repeat indefinitely.

With $x_1-x_2\le1$ and $2x_1+x_2\le2$ $2$ , increasing $x_1$ gives tied ratios of 1.
At $(x_1,x_2,s_1,s_2)=(1,0,0,0)$ $(1, 0, 0, 0)$ , exchanging $s_2$ for $x_2$ leaves the point and the objective value unchanged.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Aliases: degenerate basic feasible solution Symbols: theta

Last updated: 27 October 2026 11:52