What does it mean for a solution to be degenerate?

Question

For example, when applying the stepping stone method to the basic feasible solution of a transportation problem, the number of occupied cells needs to be m+n-1 for the solution to not be degenerate. Where m= no. of rows, n= no. of columns. What does it mean for a solution to be degenerate? Does it mean that the solution is optimal?

Answer 1

Degeneracy has no direct connection with optimality. A corner point solution is degenerate when the number of binding constraints at that point (including sign restrictions) exceeds the dimension of the space. For example, suppose that you have three variables (so the feasible region lives in $\Re^3$). Each binding constraint corresponds to a plane. You need three affinely independent planes to intersect in order to define a corner point. That means at least three constraints must be binding to define the point. However, you may have more than three constraint planes intersecting at that point, in which case it is called degenerate.

The two most common concerns with degenerate corners of linear program feasible regions are that (a) the simplex method may get confused about which constraint to back off in its next move (potentially leading to "cycling") and (b) if the corner is optimal, the dual problem will typically have multiple optimal solutions (so there is ambiguity in the "shadow prices").

Answer 2

For the transportation problem in particular, degeneracy means that you have in effect glued together two independent problems. There's a proper subset of the sources for which the sum of the quantities equals that for a proper subset of the sinks. Then you can satisfy the shipping constraints by separately solving the problem for the sources and sinks in those subsets and then for their complements.