Degeneracy in Linear Programming (operations & analytics tutoring)

Why Tutoring - California Graduate Tutor
Degeneracy in Linear Programming (operations & analytics tutoring)
Submit Homework

Degeneracy is a subtle but important concept in linear programming and operations analytics. It occurs when a basic variable in a simplex tableau takes the value zero, even though it is part of the basis. Degeneracy can cause stalling or even cycling in the simplex method.

Students often struggle to understand why degeneracy happens and how to detect or prevent it. For help with simplex, feasibility, or optimization modeling, visit the tutoring services page.

Degeneracy: A basic variable equals zero, causing simplex to stall or potentially cycle.

Degeneracy does not make a problem infeasible — it simply means the algorithm is sitting at a corner point where multiple constraints intersect.

Why Degeneracy Matters

Degeneracy is important because it:

  • can cause simplex to repeat the same BFS (stalling)
  • can lead to cycling without anti‑cycling rules
  • affects pivot choices and tableau updates
  • reveals geometric structure of LP corner points

Understanding Degeneracy Step by Step

  1. Start with a BFS (basic feasible solution).
    A BFS corresponds to a corner point of the feasible region.
  2. Check basic variable values.
    If any basic variable equals zero → degeneracy.
  3. Interpretation:
    More constraints intersect at the corner than the dimension requires.
  4. Effect on simplex:
    Pivoting may not improve the objective value → stalling.
  5. Worst case:
    Simplex may revisit the same BFS repeatedly → cycling.
  6. Prevention:
    Use anti‑cycling rules such as Bland’s Rule.

Numerical Example

Consider the LP: Maximize z = 3x₁ + 2x₂ subject to: x₁ + x₂ ≤ 4 x₁ ≤ 2 x₂ ≤ 2 x₁, x₂ ≥ 0

At the corner (2, 2), three constraints bind: x₁ + x₂ = 4 x₁ = 2 x₂ = 2 But only two variables exist → degeneracy.

In the simplex tableau, one of the basic variables will be zero, even though the point is feasible and optimal.

If simplex pivots poorly, it may bounce between equivalent BFSs without improving z.

Common Mistakes

  • Thinking degeneracy means infeasibility (it doesn’t)
  • Ignoring zero basic variables in the tableau
  • Failing to use anti‑cycling rules
  • Confusing degeneracy with unboundedness

Why This Matters in Optimization

Degeneracy is central to:

  • understanding simplex behavior
  • preventing cycling in LP solvers
  • interpreting corner points in high‑dimensional LPs
  • operations research and supply chain modeling

Related Topics

Speak Directly to a Tutor — Send Your Message Below

No call centers. No delays. Your message goes straight to the tutor.

Get help with simplex degeneracy, cycling, feasibility, and optimization modeling.