Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Simplex Method

Degeneracy, Cycling and Bland's Rule

Understand degenerate vertices, stalling and cycling in the simplex method, run Beale's classic cycling example in exact fractions and fix it with Bland's rule.

The simplex method as we described it always improves the objective, so it can never revisit a vertex... if every pivot strictly improves. That promise breaks at degenerate vertices, where pivots can make zero progress, and in extremely rare cases the algorithm can loop forever. This lesson explains degeneracy, shows a real cycle in exact arithmetic, and fixes it with Bland's rule.

What is degeneracy?

In standard form with m equations, a basic feasible solution has m basic variables. It is degenerate if at least one basic variable equals zero. Geometrically: more constraints than necessary pass through the vertex. In 2D, three constraint lines meeting at one point; in 3D, four planes through one vertex (an apex of a pyramid, for example).

Our bakery was not degenerate. But change the data so that three constraints meet at a point:

TEXT
maximize 3x + 2y   subject to  x <= 4,  y <= 4,  x + y <= 8,  x, y >= 0

At (4, 4) all three constraints are tight: the slack of every one is zero, but only two of the three slack variables can be non-basic. So one slack stays in the basis at value 0. The ratio test in the pivot that reaches this vertex produces a tie for the minimum ratio, which is the typical sign of degeneracy.

Python A degenerate vertex

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the pivot that creates the tie, one basic variable has value 0. The solution is correct (the LP is solved), but the basis contains a "zero" variable.

Why degeneracy matters

  • Stalling. A pivot at a degenerate vertex can change the basis without changing the solution, because the entering variable can rise by 0. The objective stays the same for one or more pivots.
  • Cycling. In rare cases the algorithm returns to a basis it has already visited, and with a deterministic rule it will repeat forever.
  • Non-unique duals. A degenerate primal solution can have several optimal dual solutions, so shadow prices need care.

Cycling is extremely rare in real models (it was first constructed artificially by Hoffman in 1953 and Beale in 1955) but degeneracy itself is common, because real models have many tight, structured constraints (transportation and assignment problems are heavily degenerate).

A real cycle: Beale's example

Beale's LP has seven variables and three equations. With the rules "enter the variable with the most negative reduced cost, break ties by lowest index; in the ratio test take the first tied row", the algorithm repeats a basis after six pivots and never terminates. We run it with Python Fraction numbers so no rounding can hide or cause the loop.

TEXT
minimize   -3/4 x4 + 20 x5 - 1/2 x6 + 6 x7
subject to  x1 + 1/4 x4 - 8 x5 -   x6 + 9 x7 = 0
            x2 + 1/2 x4 - 12 x5 - 1/2 x6 + 3 x7 = 0
            x3 + x6 = 1
            all x >= 0
Python Beale's cycling example in exact arithmetic

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every pivot in the cycle has a ratio of 0 (the right-hand sides of rows 1 and 2 are 0), so the objective never moves. The trouble is purely combinatorial: the rule keeps choosing among tied candidates in an order that returns to the start.

Bland's rule

Bland's rule (Robert Bland, 1977) removes the ambiguity completely:

  1. Entering variable: among all variables with a negative reduced cost (improving), choose the one with the smallest index.
  2. Leaving variable: among rows tied in the ratio test, choose the one whose basic variable has the smallest index.

With this rule simplex provably terminates, because a cycle would need a variable to be both the smallest-index improving candidate and the smallest-index leaving candidate in a way that is contradictory. The price: it ignores steepness, so it typically takes more pivots (we saw about 4 vs 2 on random problems in the last lesson). Practical codes use fast rules, and switch to Bland (or to perturbation) only after many consecutive degenerate pivots.

Other cures

  • Perturbation. Add a tiny random amount to each right-hand side, b_i + ฮต_i. This removes ties, so every vertex is non-degenerate; at the end, remove the perturbation. Modern solvers use this. The lexicographic rule is a systematic version of it.
  • Lexicographic ratio test. Break ties by comparing whole rows of the inverse basis.
  • Dual simplex or interior point. Different algorithms, different degeneracy behaviour.
Python HiGHS has no trouble with Beale's LP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result -1.25 is the same -5/4 found by Bland's rule: production solvers handle degeneracy internally, so you will rarely see cycling outside a textbook. It is still essential to understand it when writing or debugging your own solver.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A basic feasible solution is degenerate when

    Degeneracy means a basic variable is zero, so more than the necessary number of constraints are tight at the vertex.
  2. 2. What does a tie in the ratio test usually signal?

    When two rows reach zero at the same step, the next solution has a basic variable at zero.
  3. 3. Bland's rule picks

    Always choosing the smallest index in both choices guarantees that no basis repeats.
  4. 4. How does perturbing the right-hand sides prevent cycling?

    With generic small perturbations every ratio-test minimum is unique, so pivots strictly improve.

Summary

  • Degenerate vertices have a basic variable at zero; pivots there can stall.
  • Cycling (revisiting a basis) is possible in theory (Beale's example) but rare in practice.
  • Bland's rule (smallest index everywhere) guarantees termination but is slower.
  • Perturbation and lexicographic rules are other cures; real solvers use them.
  • Transportation and assignment problems are highly degenerate yet solve fine.

Next: Unbounded and Infeasible LPs