HOME

Degenerate pivots and cycling

Table of Contents

Degenerate pivots

In each pivot of the Simplex Method we are attempting to do two things simultaneously: (1) maintain feasibility of the dictionary (this restricts the choice of exiting variable), (2) increase the value of the objective function (which restricts the choice of entering variable). It’s in fact not always possible to achieve the second goal: sometimes we are forced to perform degenerate pivots that do not increase the objective function, but merely keep it the same. (Following our pivoting rules does at least guarantee that the objective function never decreases.)

When does a degenerate pivot occur? Well, when you pick the entering variable you pick a non-basic variable with positive coefficient in the objective function, so that any actual increase in the entering variable will also increase the objective function. This means that a degenerate pivot can only occur if the entering variable stays at zero without actually increasing. How much the entering variable is alowed to increase depends on the formulas for the basic variables in the dictionary: it is stuck at zero only if there is a basic variable whose value in the associated solution is zero and that includes the entering variable with a negative coefficient.

A degenerate dictionary is one in which at least one of the basic variables has the value zero; the associated solution is called a degenerate solution. The above discussion says that a degenerate pivot can only happen starting from a degenerate dictionary, but not every pivot from a degenerate dictionary is degenerate: for a degenerate pivot to occur you don’t just need a basic variable to be zero, you need one that has the entering variable with negative coefficient to have the value zero.

An example of degeneracy

Consider the following LP in standard form:

Maximize \(2x_1 + 2x_2 + x_3\)

subject to \[\begin{array}{*{10}{r}} 2x_1 & & + x_3 & \le 4 \\ x_1 & + x_2 & & \le 1 \\ x_1 & & + x_3 & \le 1 \\ x1, & x2, & x3 & \ge 0 \end{array}\]

Add slack variables to get the initial dictionary (no need for Phase 1 here):

\[\begin{array}{*{10}{r}} x_4 = & 4 & -2 x_1& & - x_3\\ x_5 = & 1 & - x_1& - x_2& \\ x_6 = & 1 & - x_1& & - x_3\\ z = & & +2 x_1& +2 x_2& + x_3\\ \end{array}\]

Now \(x_1\) enters, \(x_5\) exits.

\[\begin{array}{*{10}{r}} x_1 = & 1 & - x_2& & - x_5\\ x_4 = & 2 & +2 x_2& - x_3& +2 x_5\\ x_6 = & & + x_2& - x_3& + x_5\\ z = & 2 & & + x_3& -2 x_5\\ \end{array}\]

Here \(x_3\) enters. Of the basic variables, two limit the increase of the entering variable: \(x_4\) tells us that \(x_3\) can only increase up to \(2\), but \(x_6\) tells us that \(x_3\) can only “increase” up to zero! So we have a degenerate pivot in which \(x_6\) is the exiting variable. The next dictionary is:

\[\begin{array}{*{10}{r}} x_1 = & 1 & - x_2 & - x_5 & \\ x_3 = & & + x_2 & + x_5 & - x_6\\ x_4 = & 2 & + x_2 & + x_5 & + x_6\\ z = & 2 & + x_2 & - x_5 & - x_6\\ \end{array}\]

Notice that this dictionary has the same associated solution as the previous one, namely, \(x_1 = 1\), \(x_2 = 0\), \(x_3 = 0\), \(x_4 = 2\), \(x_5 = 0\), \(x_6 = 0\), \(z = 2\). The difference is not in the values of the variables, but rather in which variables are basic.

Let’s continue: \(x_2\) enters, \(x_1\) exits (a non-degenerate pivot).

\[\begin{array}{*{10}{r}} x_2 = & 1 & - x_1& - x_5& \\ x_3 = & 1 & - x_1& & - x_6\\ x_4 = & 3 & - x_1& & + x_6\\ z = & 3 & - x_1& -2 x_5& - x_6\\ \end{array}\]

And we’ve reached an optimal solution!

Degenerate dictionaries don’t always lead to degenerate pivots

Notice that if instead of the dictionary where we made a degenerate pivot we had instead come across a dictionary like the following, the next pivot would not have been degenerate, even though the dictionary is degenerate:

\[\begin{array}{*{10}{r}} x_1 = & 1 & - x_2& & - x_5\\ x_4 = & 2 & +2 x_2& - x_3& +2 x_5\\ x_6 = & & + x_2& + x_3& + x_5\\ z = & 2 & & + x_3& -2 x_5\\ \end{array}\]

Here, the dictionary is degenerate because the basic variable \(x_6\) is zero in the associated solution, but the pivot we’d make from here has \(x_3\) entering and \(x_4\) exiting. This pivot does increase \(x_3\) (to \(2\)) and is thus non-degenerate.

Cycling

Chvátal has a wonderful example showing that the standard rule can get trapped in a cycle of degenerate pivots!

Maximize \( 10x_1 -57x_2 -9x_3 -24x_4\)

subject to \[\begin{aligned} \frac{1}{2}x_1 -\frac{11}{2}x_2 -\frac{5}{2}x_3 +9x_4 & \le 0 \\ \frac{1}{2}x_1 -\frac{3}{2}x_2 -\frac{1}{2}x_3 +x_4 & \le 0 \\ x_1 & \le 1 \\ x_1, x_2, x_3, x_4 & \ge 0 \end{aligned}\]

Putting in the slack variables:

\[\begin{array}{*{10}{r}} x_5 = & & -\frac{1}{2} x_1& +\frac{11}{2} x_2& +\frac{5}{2} x_3& -9 x_4\\ x_6 = & & -\frac{1}{2} x_1& +\frac{3}{2} x_2& +\frac{1}{2} x_3& - x_4\\ x_7 = & 1 & - x_1& & & \\ z = & & +10 x_1& -57 x_2& -9 x_3& -24 x_4\\ \end{array}\]

Here, \(x_1\) enters and \(x_5\) exits.

\[\begin{array}{*{10}{r}} x_1 = & & +11 x_2& +5 x_3& -18 x_4& -2 x_5\\ x_6 = & & -4 x_2& -2 x_3& +8 x_4& + x_5\\ x_7 = & 1 & -11 x_2& -5 x_3& +18 x_4& +2 x_5\\ z = & & +53 x_2& +41 x_3& -204 x_4& -20 x_5\\ \end{array}\]

Now \(x_2\) enters, \(x_6\) exits.

\[\begin{array}{*{10}{r}} x_1 = & & -\frac{1}{2} x_3& +4 x_4& +\frac{3}{4} x_5& -\frac{11}{4} x_6\\ x_2 = & & -\frac{1}{2} x_3& +2 x_4& +\frac{1}{4} x_5& -\frac{1}{4} x_6\\ x_7 = & 1 & +\frac{1}{2} x_3& -4 x_4& -\frac{3}{4} x_5& +\frac{11}{4} x_6\\ z = & & +\frac{29}{2} x_3& -98 x_4& -\frac{27}{4} x_5& -\frac{53}{4} x_6\\ \end{array}\]

Here \(x_3\) enters, \(x_1\) exits.

\[\begin{array}{*{10}{r}} x_2 = & & + x_1& -2 x_4& -\frac{1}{2} x_5& +\frac{5}{2} x_6\\ x_3 = & & -2 x_1& +8 x_4& +\frac{3}{2} x_5& -\frac{11}{2} x_6\\ x_7 = & 1 & - x_1& & & \\ z = & & -29 x_1& +18 x_4& +15 x_5& -93 x_6\\ \end{array}\]

Next \(x_4\) enters, \(x_2\) exits.

\[\begin{array}{*{10}{r}} x_3 = & & +2 x_1& -4 x_2& -\frac{1}{2} x_5& +\frac{9}{2} x_6\\ x_4 = & & +\frac{1}{2} x_1& -\frac{1}{2} x_2& -\frac{1}{4} x_5& +\frac{5}{4} x_6\\ x_7 = & 1 & - x_1& & & \\ z = & & -20 x_1& -9 x_2& +\frac{21}{2} x_5& -\frac{141}{2} x_6\\ \end{array}\]

Then \(x_5\) enters, \(x_3\) exits.

\[\begin{array}{*{10}{r}} x_4 = & & -\frac{1}{2} x_1& +\frac{3}{2} x_2& +\frac{1}{2} x_3& - x_6\\ x_5 = & & +4 x_1& -8 x_2& -2 x_3& +9 x_6\\ x_7 = & 1 & - x_1& & & \\ z = & & +22 x_1& -93 x_2& -21 x_3& +24 x_6\\ \end{array}\]

Now \(x_6\) enters, \(x_4\) exits.

\[\begin{array}{*{10}{r}} x_5 = & & -\frac{1}{2} x_1& +\frac{11}{2} x_2& +\frac{5}{2} x_3& -9 x_4\\ x_6 = & & -\frac{1}{2} x_1& +\frac{3}{2} x_2& +\frac{1}{2} x_3& - x_4\\ x_7 = & 1 & - x_1& & & \\ z = & & +10 x_1& -57 x_2& -9 x_3& -24 x_4\\ \end{array}\]

And we’ve returned to the very first dictionary!

The moral of the story is that using the standard pivoting rule can lead to cycling. This is not really a problem for two different reasons:

  1. There are other pivoting rules that do guarantee termination, such as Bland’s Rule.
  2. Cycling with the standard rule is pretty unlikely, in particular, you shouldn’t fear degenerate pivots as they normally do not lead to cycling. Cycling is so rare, many computer implementations don’t bother checking for it![citation needed]

So we’ll stick with the standard rule for quizzes and such.

In this particular example, we could have chosen to pivot differently at the last step: instead of following the standard rule and choosing \(x_6\) to enter, we could choose \(x_1\) to enter. Then \(x_4\) would still exit and instead of coming back to the first dictionary we would have:

\[\begin{array}{*{10}{r}} x_1 = & & +3 x_2& + x_3& -2 x_4& -2 x_6\\ x_5 = & & +4 x_2& +2 x_3& -8 x_4& + x_6\\ x_7 = & 1& -3 x_2& - x_3& +2 x_4& +2 x_6\\ z = & & -27 x_2& + x_3& -44 x_4& -20 x_6\\ \end{array}\]

Now the only choice is for \(x_3\) to enter and \(x_7\) to exit, which is finally a non-degenerate pivot! And, luckily, we get an optimal dictionary:

\[\begin{array}{*{10}{r}} x_1 = & 1 & & & & - x_7\\ x_3 = & 1 & -3 x_2& +2 x_4& +2 x_6& - x_7\\ x_5 = & 2 & -2 x_2& -4 x_4& +5 x_6& -2 x_7\\ z = & 1 & -30 x_2& -42 x_4& -18 x_6& - x_7\\ \end{array}\]

Omar Antolín Camarena