Summer 2011

Optimization I Lecture 5

The Simplex Method

1 An iteration of the simplex method

1.1 Preliminaries
The following facts will be useful:
Pn
• Let A ∈ Rm×n , d ∈ Rn . Then Ad = j=1 Aj d j .
• Supppose
 B(1), . . . , B(m)are indices such that dj = 0 if j6= B(1), . . . , B(m). Let dB denote the vector
dB(1) | | |
 .. 
, and let B =  AB(1) AB(2) . . . AB(m)  .
 . 
d | | |
B(m)
Then Ad = BdB .
• If B is an invertible matrix, then B−1 AB(i) = ei , where ei is the i-th unit vector.
We also recall from last time that x is a basic feasible solution to an LP in standard form, if and only if x
| | |
satisfies Ax = b, x ≥ 0, and there exist indices B(1), . . . , B(m) such that B =  AB(1) AB(2) . . . AB(m) 
| | |
contains m linearly independent columns, and xj = 0 if j 6= B(1), . . . , B(m).

1.2 Choosing which nonbasic variable to increase

Let d be a vector, which has a 1 in position j and 0 for every other nonbasic variable. We consider the vector
x + θd – this is the vector that increases xj by θ, and keeps all other nonbasic variables at 0 (and we will
determine what it does to the basic variables in a moment).
We want x + θd to be a basic feasible solution, that is better than our current bfs x.
Let’s first check what we need to do to make sure x + θd is feasible:
• We need A(x + θd) = b. But our current solution is feasible, i.e., Ax = b. So we need Ad = 0. Recall
that d has a 1 in position j and 0 for every other nonbasic variable, and we have not yet determined
the other entries. So Ad = BdB + Aj . Hence, we need BdB = −Aj , or (since B is invertible!)
dB = −B−1 Aj .
• We need x + θd ≥ 0. For the nonbasic variables, we are sure this holds for any θ ≥ 0. For the basic
variables, we need xB + θdB ≥ 0. There are two things that can happen:
– There exists some i such that xB(i) = 0 and dB(i) < 0. Then, we must let θ = 0. Note that it
must be the case that the current bfs is degenerate, since xB(i) = 0!
– There exists no i such that xB(i) = 0 and dB(i) < 0. Then, we can find some θ > 0, such that
x + θd is a feasible solution.
How does moving in the direction d change the objective value?

cT (x + θd) = cT x + θcT d = cT x + θ(cj + cTB dB ) = cT x + θ(cj − cTB B−1 Aj ).

We note a couple of things:

1
 • You may have expected that increasing xj by θ increases the objective by θxj , but we see it only
increases the objective by θ(cj − cTB B−1 Aj )! This is caused by the fact that we have to simultaneously
change the basic variables, to ensure that Ax = b.
• We call cj − cTB B−1 Aj the reduced cost of the variable j, and denote it by c̄j .

• Note that if j = B(i), then c̄j = 0, since B−1 AB(i) = ei , so cj − cTB ei = cj − cB(i) = 0.
Theorem 1. Let AB(1) , . . . , AB(m) be a basis, let x be the corresponding basic feasible solution and let
c̄j = cj − cTB B−1 Aj for j = 1, . . . , n. If x is not optimal, then there exists some j such that c̄j < 0.
Proof. Suppose y is feasible and cT y < cT x.
Let d = y − x. We know three things: Ad = 0, cT d < 0, and dj ≥ 0 for j 6= B(1), . . . , B(m).
So X X
BdB + Aj dj = 0 ⇔ dB = −B−1 Aj d j
j6=B(1),...,B(m) j6=B(1),...,B(m)

and X
cT d < 0 ⇔ cj dj + cTB dB < 0.
j6=B(1),...,B(m)

We can substitute dB = −B−1 j6=B(1),...,B(m) Aj dj into this inequality, to get

P

X X
cj dj − cTB B−1 Aj dj < 0
j6=B(1),...,B(m) j6=B(1),...,B(m)
X
⇔ dj (cj − cTB B−1 Aj ) < 0
j6=B(1),...,B(m)
X
⇔ dj c̄j < 0.
j6=B(1),...,B(m)

So, since dj ≥ 0 for j 6= B(1), . . . , B(m) it cannot be the case that c̄j ≥ 0 for all j.

1.3 Moving to a new bfs from a (non-degenerate) bfs.

In the previous subsection, we found out how to determine if there is a nonbasic variable xj , such that
increasing xj will improve the solution: we just check if c̄j = cj − cTB B−1 Aj < 0.
Suppose we find j such that c̄j < 0, and suppose the current solution x is non-degenerate. Let d be the
vector we described above, with dj = 1, dj 0 = 0 for every j 0 6= j, B(1), . . . , B(m) and dB = −B−1 Aj . Let
x + θd. How large can θ be? We need
xB + θdB ≥ 0

• if dB ≥ 0, then we let θ∗ = ∞. Since c̄j < 0, this means the objective decreases by c̄j θ∗ – in other
words, the optimal objective value is −∞.

• Otherwise, let
θ∗ = min −xB(i) /dB(i) .
i=1,...,m:dB(i) <0

Note that θ∗ > 0 because we assumed that x is non-degenerate.

In the first case, we have detected that the optimal value is −∞. In the second case, we move to the new
solution xnew = x + θ∗ d.
• Note that xj was non-basic in the old solution, and that xnew
j > 0. We say that j enters the basis.

2
 • Note that it must be the case that there is some ` such that xB(`) > 0 and xnew
B(`) = 0: Indeed, there is
some ` such that θ∗ = −xB(`) /dB(`) , and for this `, xnew
B(`) = 0. We say that x B(`) leaves the basis.
 
| | | |
• So, if our old basis matrix is B =  AB(1) AB(2) . . . AB(`) . . . AB(m) . Then our new basis
 | | | |
| | | |
matrix is Bnew =  AB(1) AB(2) . . . Aj . . . AB(m) .
| | | |
Lemma 2. Bnew is a basis corresponding to the new solution xnew = x + θ∗ d.
Proof. Note that Bnew contains m columns, and that it contains all the columns that correspond to the
non-zero variables in xnew . To check that the columns are linearly independent, we must check that Aj is
not a linear combination of AB(1) , . . . , AB(`−1) , AB(`+1) , . . . , AB(m)P
.
Suppose by contradiction it is a linear combination. Then Aj = k6=` γk AB(k) or B−1 Aj = k6=` γk B−1 AB(k) .
P

Note that B−1 AB(k) is the k-th unit vector ek , so the right hand side is k6=` γk ek . Note that the right
P
hand side must have a 0 in the `-th entry, since e` is not part of the sum. On the other hand, the left hand
side is −dB and we know that dB(`) > 0, so its `-th entry is non-zero.

1.4 An iteration of the simplex method

We can now put together an iteration of the simplex method:
1. We start with a basis AB(1) , . . . , AB(m) and an associated bfs x.
2. We compute c̄j = cj − cTB B−1 Aj for every non-basic variable. If c̄j ≥ 0 for all j, we conclude x is
optimal, and the algorithm terminates.
3. Otherwise, choose j such that c̄j < 0. Variable xj enters the basis.
4. Let u = B −1 Aj (note that this is −dB ). If ui ≤ 0 for all i, then the optimal value is −∞, and the
algorithm terminates.
5. Otherwise, set θ∗ = mini:ui >0 xB(i) /ui , and let ` be such that θ∗ = xB(`) /u` . Variable xB(`) leaves the
basis.
6. The new basis is obtained by replacing AB(`) by Aj , and the new bfs by setting xnew
j = θ∗ and
new ∗
xB(i) = xB(i) + θ ui for i = 1, . . . , m.
Theorem 3. Suppose we have an initial basic feasible solution and there is no degeneracy. Then the simplex
method terminates in finite time and it either finds either an optimal solution, or it correctly reports that the
optimal value is −∞.
Proof. If the Simplex Method terminates in Step 2, then c̄j ≥ 0 for all j. Hence, by Theorem 1, the current
bfs is optimal. If the Simplex Method terminates in Step 4, then the vector d (which we recall has dB = −u,
dj = 1 and dj 0 = 0 for all j 0 6= j, B(1), . . . , B(m)) satisfies that x+θd is feasible for all θ ≥ 0 and cT d = c̄j < 0.
Hence the optimum is −∞.
Finally, by Lemma 2, in each iteration, our current solution x is a basic feasible solution. Since there is
no degeneracy, the objective value cT x strictly decreases in each iteration. So we consider each basic feasible
solution at most once, and since there is a finite number of bfs, the algorithm must have a finite number of
iterations.
We are left with a couple of questions.
• How do we find an initial bfs? [Initialization]

3
• What do we do if our current bfs is degenerate? [Anticycling Rules]
Note that we can still execute our iteration in Section 1.4; the only problem is that we may have θ∗ = 0.
This means that we do not actually move to a different bfs, just to a different basis. We’ll call this a
degenerate pivot. Sometimes you have to do such a sequence of basis changes before you can move to a
different solution. The danger, however, is cycling: the algorithm may keep changing bases but never
leave the current solution.
In practice, this fortunately does not happen. We’ll also see a way to deal with this problem in theory.
An example of cycling is given here: [Link]
(We’ll see how to interpret these tables next week).
• If we have multiple non-basic variables with c̄j < 0, which one should we choose? [Pivot Selection]

• How fast is this algorithm? [Implementation Issues, Number of Iterations]