Degeneracy occurs in linear programming when a basic feasible solution has one or more basic variables equal to zero. This means the solution sits at a corner point where more constraints intersect than are needed to define that corner. Degeneracy affects how the simplex method moves through the feasible region and can lead to issues such as cycling or repeated corner points. This page explains why degeneracy happens and why it matters for solving linear programs.
Many graduate students across New York City — including those at NYU, Columbia University, Baruch College (CUNY), Fordham University, Pace University, Cornell Tech, and Stevens Institute of Technology — often find that quantitative, optimization, and analytics problems become far more challenging once you begin applying modeling structure, equilibrium logic, and formal reasoning. This page provides a clear, online-friendly, graduate-level explanation designed to help NYC students understand both the technical steps and the intuition behind them.
If you need broader support, explore our Business Analytics Tutoring for more NYC-focused graduate problem breakdowns. You can also reach out anytime through our Contact Page.
Degeneracy Happens When Extra Constraints Meet at a Corner
A corner point in two dimensions is normally defined by two binding constraints. In higher dimensions, a corner is defined by as many binding constraints as there are variables. Degeneracy occurs when:
- more constraints bind than are mathematically necessary,
- the intersection of constraints collapses onto a single point,
- one or more basic variables become zero.
This creates a “tight” corner where multiple constraints overlap.
Slack or Surplus Variables Become Zero at the Same Time
Degeneracy often arises because several slack or surplus variables are zero simultaneously. This means multiple constraints are binding at the same point. For example:
- labor is fully used,
- machine time is fully used,
- material is fully used,
- and a minimum production requirement is also binding.
When too many constraints bind at once, degeneracy appears naturally.
Degeneracy Causes the Simplex Method to Stall or Repeat
In a degenerate corner, the simplex method may pivot to a new basis without improving the objective function. This happens because the entering variable increases from zero, but the leaving variable also becomes zero immediately.
Consequences include:
- the objective function does not improve,
- the algorithm may revisit the same corner,
- in rare cases, the algorithm may cycle.
Anti-cycling rules (like Bland’s rule) exist specifically to handle degeneracy.
Degeneracy Does Not Change the Feasible Region
Degeneracy is a property of the geometry of the feasible region, not a sign of an error. It simply means the feasible region has “sharp” corners where many constraints meet. The region is still convex, and the optimal solution is still valid.
Degeneracy affects the path the simplex method takes, not the existence of an optimal solution.
Economic Interpretation: Multiple Scarce Resources Bind at Once
Degeneracy often reflects a real-world situation where several resources are simultaneously scarce. For example:
- labor is fully used,
- budget is fully used,
- raw materials are fully used,
- and a minimum production requirement is binding.
This means the firm is operating at a point where many constraints are tight, creating a degenerate corner.
Final Summary
Degeneracy occurs when more constraints bind at a corner point than are needed to define it, causing one or more basic variables to be zero. It affects the simplex method by creating repeated pivots or cycling, but it does not change the feasible region or the validity of the optimal solution. Degeneracy reflects situations where multiple resources are simultaneously scarce, making it an important concept in both the mathematics and economics of linear programming.
This explanation belongs to the broader Linear Programming and Optimization pillar.
If you want help working through these ideas for coursework or exams, you can talk directly to a tutor, not a marketer.
Call/Text: 646-543-0832
Email: tutor@mytutornyc.com
