Introduction to Algorithms, Third Edition

Termination
In the example given in the beginning of this section, each iteration of the simplex
algorithm increased the objective value associated with the basic solution. As Ex-
ercise 29.3-2 asks you to show, no iteration of S
IMPLEX
can decrease the objective
value associated with the basic solution. Unfortunately, it is possible that an itera-
tion leaves the objective value unchanged. This phenomenon is called
degeneracy
,
and we shall now study it in greater detail.

---

29.3
The simplex algorithm
875
The assignment in line 14 of P
IVOT
,
y
D
C
c
e
y
b
e
, changes the objective value.
Since S
IMPLEX
calls P
IVOT
only when
c
e
> 0
, the only way for the objective
value to remain unchanged (i.e.,
y
D
) is for
y
b
e
to be
0
. This value is assigned
as
y
b
e
D
b
l
=a
le
in line 3 of P
IVOT
. Since we always call P
IVOT
with
a
le
¤
0
, we
see that for
y
b
e
to equal
0
, and hence the objective value to be unchanged, we must
have
b
l
D
0
.
Indeed, this situation can occur. Consider the linear program
´
D
x
1
C
x
2
C
x
3
x
4
D
8
x
1
x
2
x
5
D
x
2
x
3
:
Suppose that we choose
x
1
as the entering variable and
x
4
as the leaving variable.
After pivoting, we obtain
´
D
8
C
x
3
x
4
x
1
D
8
x
2
x
4
x
5
D
x
2
x
3
:
At this point, our only choice is to pivot with
x
3
entering and
x
5
leaving. Since
b
5
D
0
, the objective value of
8
remains unchanged after pivoting:
´
D
8
C
x
2
x
4
x
5
x
1
D
8
x
2
x
4
x
3
D
x
2
x
5
:
The objective value has not changed, but our slack form has. Fortunately, if we
pivot again, with
x
2
entering and
x
1
leaving, the objective value increases (to
16
),
and the simplex algorithm can continue.
Degeneracy can prevent the simplex algorithm from terminating, because it can
lead to a phenomenon known as
cycling
: the slack forms at two different itera-
tions of S
IMPLEX
are identical. Because of degeneracy, S
IMPLEX
could choose a
sequence of pivot operations that leave the objective value unchanged but repeat
a slack form within the sequence. Since S
IMPLEX
is a deterministic algorithm, if
it cycles, then it will cycle through the same series of slack forms forever, never
terminating.
Cycling is the only reason that S
IMPLEX
might not terminate. To show this fact,
we must first develop some additional machinery.
At each iteration, S
IMPLEX
maintains
A
,
b
,
c
, and
in addition to the sets
N
and
B
. Although we need to explicitly maintain
A
,
b
,
c
, and
in order to
implement the simplex algorithm efficiently, we can get by without maintaining
them. In other words, the sets of basic and nonbasic variables suffice to uniquely
determine the slack form. Before proving this fact, we prove a useful algebraic
lemma.

---

876
Chapter 29
Linear Programming