Lecture 6: Simplex Method (cont’d)

Ming Yan

School of Data Science (SDS)

The Chinese University of Hong Kong, Shenzhen

June 17, 2022

Ming Yan MAT 3007 June 17, 2022 1 / 42

Recap: Simplex Method

Start with a BFS

Compute reduced cost c̄N
If all reduced costs c̄N 0, optimal; else, select an entering variable xj
Compute dB ; if dB 0, unbounded
Compute ✓⇤ using min-ratio test and select the exiting variable
Create the new basis and compute the new BFS

Ming Yan MAT 3007 June 17, 2022 2 / 42

Recap through Example

We want to solve:

maximize 6x1 + 4x2

x1 ,x2

subject to x1 + x2  6
2x1 + x2  9
2x1 + 3x2  16
x1 , x2 0.
☆

Ming Yan MAT 3007 June 17, 2022 3 / 42

Recap through Example: Starting with a BFS

Observation:
All constraints are  constraint. We need to add slack variables on
the left-hand side of constraints to obtain the standard form.
If we use the slack variables to form the initial basis, it will be an
identity matrix, i.e., AB = IM with B = {3, 4, 5}.
.

The right-hand side of the constraints are all nonnegative, which will
provide a BFS automatically:

xB = AB 1 b = I 1
b = Ib = b 0.
= =
2 3 2 3
x3 6
Initial B = {3, 4, 5}, initial BFS xB = x4 = 9 5 .
4 5 4
x5 16

Ming Yan MAT 3007 June 17, 2022 4 / 42

Simplex Example: Step 1

1 Begin with an initial BFS: (Point “A” )

BVs : x3 , x4 , x5
NBVs : x1 , x2
2 3
1 0 0
AB = AB 1 = 40 1 05
0 0 1
2 3 2 3
x3 6  
4 5 1 4 5 x1 0
xB = x 4 = A B b = 9 xN = = .
x2 0
x5 16
- 1
2 c̄> >
N = cN c>
B AB AN =?
c̄N ⇤ 0? Which non-basic variable xj can enter?
3 dB = AB 1 A·j =? Is the problem unbounded?
4 ✓⇤ =? and ` =?. The leaving variable is ?

Ming Yan MAT 3007 June 17, 2022 5 / 42

Next Iteration

1 (Point “B”)
BVs : x1 , x3 , x5 NBVs : x2 , x4
2 3 2 3
1 1 0 0 1/2 0
AB = 4 2 0 0 5 AB 1 = 4 1 1/2 05
2 0 1 0 1 1
2 3 2 3
x1 9/2  
x 0
xB = 4x3 5 = 43/25 xN = 2 = .
x4 0
x5 7
Aside: z = c> x = c>
€
>
B xB = 27. Also,
z ⇤
z + c̄j · ✓ = 0 6 · 9/2 = 27.
=
1
2 c̄> >
N = cN c>
B AB AN =?
-
c̄N ⇤ 0? Which non-basic variable xj can enter?
3 dB = AB 1 A·j =? Is the problem unbounded?
4 ✓⇤ =? and ` =?. The leaving variable is ?
Ming Yan MAT 3007 June 17, 2022 6 / 42
Stopping Criteria

1 (Point “C” )
BVs : x1 , x2 , x5 NBVs : x3 , x4
2 3 2 3
1 1 0 1 1 0
4
AB = 2 1 0 5 1
AB = 24 1 05
2 3 1 4 1 1
2 3 2 3
x1 3  
4 5 4 5 x3 0
xB = x 2 = 3 xN = = .
x4 0
x5 1

B xB = °
Aside: z = c> x = c> > 30. Also,
z ⇤
z + c̄j · ✓ = 27 3 · 1 = 30.
1
2 c̄> >
N = cN c>
B AB AN =?
3 Now c̄N 0? The current BFS is optimal?
-

Ming Yan MAT 3007 June 17, 2022 7 / 42

Interpreting Simplex Method

Reduced cost: the rate of objective value improvement by moving a

unit length on the improving direction
Step length: how far we can move
Stopping criteria: no improvement can be made
Every step you can perform some sanity check:
Is my objective value improving? Is it the same as step length ⇥
reduced cost?
Is my objective value matching c>
B xB
We cannot have a negative element in AB 1 b
You can check the dimension of Ax = AB xB + AN xN = b, xB = AB 1 b,
dB = AB 1 A·j , c̄>
N = cN
>
c> 1
B AB AN

ABXB = b XB= AI't

CBT ABYAN
'
C- = Cnt _

CBTXB
dB
Ming Yan = -
MAT 3007
= CRABB
June 17, 2022 8 / 42
Simplex Method: Discussion

Open questions:
How do we find the starting BFS?
What would happen if xB(`) = 0?
Given several j with c̄j < 0, which xj should we choose to enter the
basis?
Suppose there are multiple ` with the same ✓⇤ = xB(`) /dB(`) , how
should we update the basic indices?
Previous matrix manipulation steps seem hard: can we have a better
way in practice? ! Tableau Method!

Ming Yan MAT 3007 June 17, 2022 9 / 42

 Tableau Method

Ming Yan MAT 3007 June 17, 2022 10 / 42

Tableau Method

You will be driven crazy after a few rounds of Simplex method ! matrix
inversion by hand is tedious and it is easy to make mistakes during
calculation!
We are going to introduce the simplex tableau, which is a practical way to
implement the simplex method.
The simplex tableau maintains a table of numbers.
It visualizes the procedures of the simplex algorithm and facilitates
the computation.
After learning the simplex tableau, one should be able to solve
small-sized linear optimization problems by hand more easily.

Ming Yan MAT 3007 June 17, 2022 11 / 42

Simplex Tableau

We keep a table with the following structure:

reduced cost → →
-

CÉXB
c> O c> 1 >
B AB A OcB AB b
1
1 1
AB A AB b
~

Ars"[ABAN ]
¥,
I ,
Ari'AN
Any
"
AX = b GÉAB
"

i:iii¥i•¥*¥%
*

Ming Yan MAT 3007 June 17, 2022 12 / 42

Simplex Tableau

We keep a table with the following structure:

1 1
c> c> B AB A c>
B AB b
1 1
AB A AB b
What do they mean? (with some columns reordering in [B; N])

1
0>
m⇥1 c>
N c>
B AB AN (Reduced Cost) c>
B xB (Negative Objective

"
Im⇥m AB 1 AN (Improving direction) xB (Solution)
Here, 0m⇥1 2 Rm⇥1 is a vector of m zeros and Im⇥m is the
m-dimensional identity matrix.
This form of an LP is called the canonical form:
The constraint matrix for the basic variables (not necessarily the first
m columns) is an identity matrix.
The objective function part for the basic variables is zero.

Ming Yan MAT 3007 June 17, 2022 12 / 42

Simplex Tableau ! Simplex Algorithm?

The simplex tableau will maintain a canonical form for each iteration until
we reach optimality.
If in a simplex tableau, the numbers in the top left row (reduced cost) are
all nonnegative, then we have reached optimality!
With simplex tableau, how do we:
compute reduced costs and choose the incoming basis?
compute the step length and choose the outgoing basis?
update the tableau after every iteration?
Pivoting: a step going from one canonical form to another.

Ming Yan MAT 3007 June 17, 2022 13 / 42

Simplex Tableau: Process Showcase with Example

Let’s reuse our favorite example:

minimize 6x1 4x2

x1 ,x2

subject to x1 + x2 + x3 = 6
2x1 + x2 + x4 = 9
2x1 + 3x2 + x5 = 16
x1 , x2 , x3 , x 4 , x 5 0.

☒
Pivot column: entering column
Pivot row: identified binding outgoing variable by min-ratio test
Pivot element: changed to one to update the canonical form

Ming Yan MAT 3007 June 17, 2022 14 / 42

Simplex Tableau: Example Revisited

1
0>
m⇥1 c>
N c>
B AB AN c>
B xB
1
Im⇥m AB AN xB
Starting simplex tableau:

←⑧
¥-40
-6 -4 0
"
0 0 0
•
-6 -4 0 0 0 0
1 1 1 0 0 6 1 1 1 0 0 6
2 1 0 1 0 9 2 1 0 1 0 9
2 3 0 0 1 16 2 3 0 0 1 16

%
A b

1%-1%1
We can select any column with a negative value in the first row (negative
reduced cost). For example, let’s select the first column to enter (smallest

1¥)
reduced cost).
E-
Ming Yan MAT 3007 June 17, 2022 15 / 42
Simplex Tableau: Example Revisited

1
0>
m⇥1 c>
N c>
B AB AN c>
B xB
1
Im⇥m AB AN xB
To choose an exiting column, we need to perform min-ratio test:
⇢
⇤ xi
✓ = min dB = AB 1 A·j
i2B:di <0 di

In the simplex tableau, this is equivalent to:

( )
x i
✓⇤ = min : [AB 1 A·j ]i > 0
i2B:di <0 [AB 1 A·j ]i

! We compare the quotient between the last column and the pivot
column and select the row with the smallest quotient value, while the
value of that row at the pivot column is positive.

Ming Yan MAT 3007 June 17, 2022 16 / 42

Simplex Tableau: Example Revisited

-6 -4 0 0 0 0 ② A
-6 -4 0 33
0 0 2277
0
1 1 1 0 0 6 10 1Iz 1 K
-
0 0 6Asi ! 6/1 = 6
2 1 0 1 0 9 2☆ 112 0 112 0 912 ! 9/2 = 4.5
2 3 0 0 1 16 •
2 22
3 0 A0 1 16 ! 16/2 = 8
$
Select the second row as the pivot row, and the intersection element is
called the pivot element.
Then the column in the current basis whose i-th element is 1 is the
outgoing basis. In this case column 4 (corresponding to x4 ).

Ming Yan MAT 3007 June 17, 2022 17 / 42

Simplex Tableau: Example Revisited

Next we need to change the current canonical form to another, by

transforming the entering column to a column with only one element
(pivot element) 1 and the rest of elements 0.
Divide each element in the pivot row by the pivot element. Add proper
multiples of the pivot row to each other rows so that all other elements in
the pivot column become zeros (including the top row).

Ming Yan MAT 3007 June 17, 2022 18 / 42

Simplex Tableau: Example Revisited

Next we need to change the current canonical form to another, by

transforming the entering column to a column with only one element
(pivot element) 1 and the rest of elements 0.
Divide each element in the pivot row by the pivot element. Add proper
multiples of the pivot row to each other rows so that all other elements in
the pivot column become zeros (including the top row).
In our case, we need to divide row 3 (pivot row) by 2, and then add 6
times row 3 from row 1 (reduced cost), subtract 1 times row 3 from row 2,
and 2 times row 3 from the bottom row.
-6 -4 0 0 0 0 0 0
-1 22
0 2 3 0 30
27

{
"

1 1 1 0 0 6 0 ⑨
0.5 22
1 N
-0.5
-
0 333
1.5 3

1 0.5 0 0.5 0 4.5 1 •

0.5 -
0M 0.5
N 0 33
4.5 s

2 3 0 0 1 16 0 ⑨2 -44 A
0 -1 1 •7 3¥

Ming Yan MAT 3007 June 17, 2022 18 / 42

Simplex Tableau: Example Revisited

0 -1 0 3 0 27
0 0.5 1 -0.5 0 1.5
1 0.5 0 0.5 0 4.5
0 2 0 -1 ◦1 7

What does this tableau mean? (Point B in the previous figure)

Next step?

Ming Yan MAT 3007 June 17, 2022 19 / 42

Simplex Tableau: Example Revisited

0 -1 0 3 0 27
0 0.5 1 -0.5 0 1.5
1 0.5 0 0.5 0 4.5
0 2 0 -1 1 7

What does this tableau mean? (Point B in the previous figure)

Next step?
0 -1 0 3 0 27 0 0 2 2 0 30
0 1 2 -1 0 3 0 1 2 -1 0 3
1 0.5 0 0.5 0 4.5 1 0 -1 1 0 3
0 2 0 -1 1 7 0 0 -4 1 1 1
We can also apply the same procedure to Phase-I models.

Ming Yan MAT 3007 June 17, 2022 19 / 42

 A
Finding an initial BFS!

Ari's
ai

GiAÑb
"
CBT CBTAB Am
Ming Yan MAT 3007 June 17, 2022 20 / 42
Simplex Method: Discussion

Open questions:
How do we find the starting BFS? ! Two-phase Method!
What would happen if xB(`) = 0?
Given several j with c̄j < 0, which xj should we choose to enter the
basis?
Suppose there are multiple ` with the same ✓⇤ = xB(`) /dB(`) , how
should we update the basic indices?
Previous matrix manipulation steps seem hard: can we have a better
way in practice?

Ming Yan MAT 3007 June 17, 2022 21 / 42

Finding an Initial BFS

We have discussed that if the LP has the following form (no equality
constraints), it is easy to obtain an initial basis:

minimize c> x
x
subject to Ax  b (b 0)
x 0,

We can add a set of slack variable s and start with the slack variables
being the basic variables.

minimize c> x
x,s

subject to Ax + Is = b
x 0, s 0.

Therefore, the initial basis matrix is the identity matrix I. s = b 0

Ming Yan MAT 3007 June 17, 2022 22 / 42
Finding an Initial BFS

However, in general, it is not necessarily easy to get an initial BFS from

the standard form. For example:

minimize x1 +x2 +x3

x
subject to x1 +2x2 +3x3 = 3
4x2 9x3 = 5
+3x3 +x4 = 1
x1 , x2 , x3 , x4 0

One could enumerate di↵erent bases AB to see if AB 1 b 0, but it

-
may take a long time for a large problem.
In fact, in terms of computational complexity (which we will define
later), finding a BFS is as hard as finding the optimal solution!
We need an initialization process to get a BFS, or detect infeasibility.

Ming Yan MAT 3007 June 17, 2022 23 / 42

 Two-phase Simplex Method

In the two-phase simplex method, we first solve an auxiliary problem called

phase-I model (e is an all-one vector): It 7-
✗

min CTX 5. e. A✗=b

.

minimize e> y
5. t AX=b x,y ×≥ 0

=-
.

×≥o subject to Ax + Iy = b Ax-110=5

x, y 0 × ≥o

Without loss of generality, we can assume b 0 (otherwise, we 0=0

pre-multiply that row by 1).
Trivial BFS for this auxiliary problem: x = 0, y = b 0.
We can apply the simplex method to solve it. Suppose the optimal
value of phase-I model is denoted by w ⇤ and the optimal solution by
x⇤ , y ⇤ .

Ming Yan MAT 3007 June 17, 2022 24 / 42

?⃝
Two-phase Simplex Method

Theorem: Feasibility
The original problem is feasible if and only if w ⇤ = 0.

There are three possible scenarios after we solve the phase-I model using
the simplex method:
w ⇤ 6= 0, y⇤ 6= 0. ! Infeasible! -
=
w ⇤ = 0, y⇤ = 0, all y ⇤ nonbasic. ! We have obtained a BFS x⇤ !
-

w ⇤ = 0, y⇤ = 0, some y⇤ basic. !
We can obtain a BFS by substituting the basic column in y⇤ with any
non-basic column in x⇤ as long as they form an independent matrix.
This corresponds to degeneracy in x⇤ .

AE×pitEnY?b ÷
Ming Yan MAT 3007 June 17, 2022 25 / 42
Procedure of the Two-Phase Method

Phase I:
1. Construct the auxiliary problem such that b 0.
2. Solve the auxiliary problem using the simplex method.
• If we reach an optimal solution with optimal value greater than 0, then
the original problem is infeasible.
3. If the optimal value is 0 with optimal solution x⇤ ! Phase II.

Phase II:
Solve the original problem starting from the BFS x⇤ :
If x⇤ is degenerate, then we need to supplement some indices to make
it a BFS for the original problem

Ming Yan MAT 3007 June 17, 2022 26 / 42

 Find the Next BFS!

Ming Yan MAT 3007 June 17, 2022 27 / 42

Simplex Method: Discussion

Open questions:
How do we find the starting BFS?
What would happen if xB(`) = 0? ! Degeneracy!
=

Given several j with c̄j < 0, which xj should we choose to enter the
Tr
basis?
Suppose there are multiple ` with the same ✓⇤ = xB(`) /dB(`) , how
r =
should we update the basic indices?
Previous matrix manipulation steps seem hard: can we have a better
way in practice?

Ming Yan MAT 3007 June 17, 2022 28 / 42

Degeneracy

We have seen that the objective value will strictly decrease after one
simplex method iteration if the initial BFS is nondegenerate.
However, it is possible that the objective stays the same.
Since the change of the objective value (if xj enters the basis) is ✓⇤ c̄j and
we have c̄j < 0, this can only happen if ✓⇤ = 0.
Recall that ⇢
⇤ xi
✓ = min .
i2B:di <0 di
If for some i’s with di < 0, there is xi = 0 then we obtain ✓⇤ = 0.
! This may happen when there are 0s in the BFS x.

Ming Yan MAT 3007 June 17, 2022 29 / 42

Degeneracy

Degeneracy
We call a basic feasible solution x (non)degenerate if (none) some of the
basic variables are 0.

Degeneracy can happen. We need to consider what consequences it

may have in the algorithm! ✗it 2×2=8
An example:

00
-
*

{
x1 +2x2 +s1 = 8
x1 x2 +s2 = 4
x1 +x2 +s3 = 4
x1 , x2 , s1 , s2 , s3 0

If we choose the basic indices to be {1, 2, 4}, then the corresponding basic
solution is (0, 4, 8). It is degenerate.
=

! The number of non-zeros at the BS is strictly less than m.

Ming Yan MAT 3007 June 17, 2022 30 / 42
Illustration of Degeneracy

:
HE
2
x2

4
5 0 5 10
x1

More than 2 lines intersect at one point.

In general, at a degenerate point, more than k planes intersect at a
k-dimensional space.
Ming Yan MAT 3007 June 17, 2022 31 / 42
Degeneracy

Assume we encounter degeneracy at some point:

Given a BFS x with negative reduced cost c̄j < 0 and ✓⇤ = 0. And i
is the index that achieves min { xi /di }. Thus, xi = 0.
i2B:di <0 -

We can still change the basic index from i (i leaving the basis) to j (j
entering the basis) and proceed to the next iteration.
Although the iterate and the objective value do not change, the basis
changes. Therefore, the reduced costs vector will change in the next
iteration – issue seems resolved?

We need to guarantee that there is not any cycle, i.e., we will not visit the
same BFS more than once:
This can only occur in case of degeneracy, since otherwise the
objective value will strictly decrease!

Ming Yan MAT 3007 June 17, 2022 32 / 42

Example of Cycling

If not dealt properly, cycling can happen. Consider the LP:

✓ ◆ ✓ ◆
2 9 1 9 1 0 0
A= b=
1/3 1 1/3 2 0 1 0
>
c = ( 2, 3, 1, 12, 0, 0).

If we set B = {5, 6} initially, then the sequence shown below leads to a

cycle (objective value doesn’t change, and there is always an index with
negative reduced cost):
min .
CTX
✗
sit . Ax = b

Ming Yan MAT 3007 June 17, 2022 33 / 42

Example of Cycling

If not dealt properly, cycling can happen. Consider the LP:

✓ ◆ ✓ ◆
2 9 1 9 1 0 0
A= b=
1/3 1 1/3 2 0 1 0
>
c = ( 2, 3, 1, 12, 0, 0).

If we set B = {5, 6} initially, then the sequence shown below leads to a

cycle (objective value doesn’t change, and there is always an index with
negative reduced cost):
-2p ⑧ -3 10 12⑥ 0 33 0 0

y
•
-2 -9 -222
1 -
9 1 0 0
1/3 1 -1/3 -2 0 1 0
Select x2

Ming Yan MAT 3007 June 17, 2022 33 / 42

Ming Yan MAT 3007 June 17, 2022 34 / 42
cont’d

-2 -3 1 12 0 0 0
-2 -9 1 9 1 0 0
1/3 1 -1/3 -2 0 1 0
Select x2
-1 0 0 6 0 3 0
1 0 -2 -9 1 9 0
1/3 1 -1/3 -2 0 1 0
Select x1
0 0 00
-2 -3 1 12 0
1 0 -2 -9 1 9 0
0 1 1/3 ᵗ# 1 -1/3 -2 0
Select x4
0 3 ☐-1 0 0 6 0
1 9 1 0 -2 -9 0
0 1 1/3 1 -1/3 -2 0

Ming Yan MAT 3007 June 17, 2022 35 / 42

cont’d

0 3 -1 0 0 6 0
1 9 F 1 0 -2 -9 0
0 1 1/3 1 -1/3 -2 0
Select x3

:
1 12 0 0 -2 -3 0
1 9 1 0 -2 -9 0
-1/3 -2 0 1 1/3 1 0
Selectx6
0 6 0 3 -1 0 0
-2 -9 1 9 1 0 0
-1/3 -2 0 1 1/3 1 0
Select x5
-2 -3 1 12 0 0 0
-2 -9 1 9 0 1 0 0
1/3 1 -1/3 -2 0 1 0

Ming Yan MAT 3007 June 17, 2022 36 / 42

cont’d

Step # 1 2 3 4 5 6
Exiting x6 x5 x2 x1 x4 x3
Entering x2 x1 x4 x3 x6 x5
4.6$Basis {5, 2}
-
{1, 2} {1, 4} {3, 4} {3, 6} {5, 6}

We will show that cycle can be avoided by designing how to choose

incoming/outgoing basis when there are multiple choices.

Ming Yan MAT 3007 June 17, 2022 37 / 42

Pivoting Rules: Choosing the Entering Basis

In the description of the algorithm, we said that at each feasible point, we

can choose any j with negative reduced cost to enter the basis in the next
iteration.
Sometimes, there are more than one j with c̄j < 0. In this case, we need
to introduce some rules to choose the entering basis.

Here are several possible rules:

1 Smallest Index Rule: Choose the smallest index j with c̄j < 0.
2 Most Negative Rule: Choose the smallest c̄j .
3 Most Decrement Rule: Choose j with the smallest ✓⇤ c̄j .
Question: at optimality, what does c̄j = 0 for one or more non-basic
variables infer?

Ming Yan MAT 3007 June 17, 2022 38 / 42

Pivoting Rules: Choosing the Exiting Basis

Recall that ⇢
xi
✓⇤ = min .
i2B|di <0 di
We choose one index that attains this minimum to leave the basis.

It is possible that there are two or more indices that attain the minimum
(tie). Then we also need a rule to decide the new basis.
The most commonly used rule is the smallest index rule.

When this tie happens, the next BFS will be degenerate. (Why?)

Ming Yan MAT 3007 June 17, 2022 39 / 42

Bland’s Rule

Theorem: Bland’s Rule

If we use the smallest index rule for choosing both the entering basis and
the exiting basis, then no cycle will occur in the simplex algorithm.

Using the Bland’s rule when applying the simplex method, we can
guarantee to stop within a finite number of iterations at an optimal
solution.
However, this could slow the algorithm down. In practice, it is hard to
observe such cycling phenomenon, and we can assume using the
smallest reduced cost is safe, even though degeneracy happens very
often in real-life linear programs.

Ming Yan MAT 3007 June 17, 2022 40 / 42

The circle example revisited
→ →
-2 -3 1 12 0 0 0
-2 -9 1 9 1 0 0
*
1/3 1 -1/3 -2 0 1 0
Select x1
0 3 0 -1 0 0 6 0
0 -3 -1 -3 1 6 0
1 3 -1 -6 0 3 0
Then d = [1, 0, 1, 0, 1, 0]> and we have Ad = 0 and cEl
d = 1. The
n solution is unbounded.

É¥ ]
-

! optimal value is -
is

5th
%

Ming Yan MAT 3007 June 17, 2022 41 / 42

Summary
AA Ax = b ≥o
Closed questions:
How do we find the starting BFS? ! Two-phase Method!
What would happen if xB(`) = 0? ! Degeneracy!
Given several j with c̄j < 0, which xj should we choose to enter the
basis? ! Pivoting Rules
Suppose there are multiple ` with the same ✓⇤ = xB(`) /dB(`) , how
should we update the basic indices? ! Pivoting Rules
Previous matrix manipulation steps seem hard: can we have a better
way in practice? ! Tableau Method!

Ming Yan MAT 3007 June 17, 2022 42 / 42