CSC 445/545 – Summer 2021
The Revised Simplex Method
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
June 20, 2021
Revised Simplex Method
This lecture will present a linear-algebraic interpretation of the simplex method, which is well suited to implementation using numerical linear algebra operations.
The Revised Simplex Method is a derivative of the Simplex Method which leverages certain properties of the linear algebraic interpretation to reduce the work required at each step.
Note: The Revised Simplex Method is not the name for linear algebraic Simplex implementations in general. Most of this lecture actually covers the “regular” Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 2
Initial Observations (1)
max. 3×1+6×2+2×3
s.t. 4×1 − x2 +2×3 ≤1 max. c·x
−2×1 + x2 − 2×3 ≤ 2 s.t. Ax ≤ b x1 +x3≤3 x≥0
x1,x2,x3 ≥ 0
We are already familiar with writing an LP using matrix and vector notation.
University of Victoria – CSC 445/545 – Summer 2021 3
Initial Observations (2)
max. 3×1+6×2+2×3
max. (3, 6, 2) · (x1, x2, x3)
4 −1 2 x1 1
s.t. −2 1 −2x2 ≤ 2
s.t.
4×1 − x2 +2×3 −2×1 + x2 −2×3 x1 + x3
x1,x2,x3
≤1 ≤2 ≤ 3 ≥ 0
We are already familiar with writing an LP using matrix and vector notation.
University of Victoria – CSC 445/545 – Summer 2021
4
1 0 1 x3 x1,x2,…,xn
3 ≥ 0
Initial Observations (3)
ζ = 0 + 3×1
w1 = 1 − 4×1
w2 = 2 + 2×1
w3 = 3 − x1
+ 6×2
+ 2×3 − 2×3 + 2×3 − x3
ζ = (3,6,2)·(x1,x2,x3)
w1 1 4 −1 2 x1 w2= 2−−2 1 −2x2 w3 3101×3
+
−
x2 x2
We can represent the initial dictionary using linear algebraic notation as well. Notice the sign changes in the matrix on the right (due to the subtraction)
University of Victoria – CSC 445/545 – Summer 2021 5
Initial Observations (4)
ζ = 0 + 3x + 6x + 2x
ζ = w1
cx
(3,6,2)·(x1,x2,x3)
1 4 −1 2 x1
1
2 3 + x2 − 2×3 − x2 + 2×3 3 1 3
w1 = 1 − 4×1
w2 = 2 + 2×1
w=3−x −x w3 3101×3
w2= 2−−2 1 −2x2
Specifically, the dictionary above is equivalent to
ζ= cTx w= b−Ax
University of Victoria – CSC 445/545 – Summer 2021
6
wbAx
Initial Observations (5)
ζ = 0 + 3x + 6x + 2x
ζ = w1
cx
(3,6,2)·(x1,x2,x3)
1 4 −1 2 x1
1
w1 = 1 − 4×1
2 3 + x2 − 2×3 − x2 + 2×3
w2= 2−−2 1 −2x2 3 1 3
wbAx
w2 = 2 + 2×1
w=3−x −x w3 3101×3
Experiment: What happens to the linear algebraic representation if we use pivoting to put x1, x2, x3 into the basis and remove w1, w2, w3?
University of Victoria – CSC 445/545 – Summer 2021 7
Initial Observations (6)
The dictionary with (w1, w2, w3) basic is
ζ= cTx
w= b−Ax
To exchange wi for xi in the basis, we want a dictionary like
ζ= ??? x= ???,
and since we already know that the dictionary representation changes nothing about the underlying algebraic relationships, we want an equivalent formulation of the initial dictionary, just with x on the left hand side.
Therefore, we can try solving the initial dictionary equations for x.
University of Victoria – CSC 445/545 – Summer 2021 8
Initial Observations (7)
If we assume that the matrix A is invertible, the expression w = b − Ax implies that x =A−1(b−w)=A−1b−A−1w,
which can be substituted into the objective function ζ = cT x
to give
University of Victoria – CSC 445/545 – Summer 2021
9
ζ =cT A−1b−A−1w=cTA−1b−cTA−1w
Initial Observations (8)
For the initial dictionary
ζ =
w1 w2 =
cx
(3,6,2)·(x1,x2,x3)
1 4 −1 2 x1
2 − −2 1 −2 x2
w3 3101×3
wbAx
the inverse of A is
1 1 0 −1 2 2
University of Victoria – CSC 445/545 – Summer 2021
11
A =0 1 2
−1 −1 22
1
Initial Observations (9)
Therefore, the value of x will be
x = A−1b − A−1w
1 1 01 1 1 0 22 22
= 0 1 2 2 − 0 1 2 w −1 −1 1 3 −1 −1 1
22 22 3 1 1 0
University of Victoria – CSC 445/545 – Summer 2021
12
222
= 8 − 0 1
3 −1−1 222
2 w 1
Initial Observations (10)
The new objective function value ζ will be ζ = cT A−1b − cT A−1w
1 1 01 1 1 0 22 22
=3620 1 22−3620 1 2w −1 −1 1 3 −1 −1 1
22 22 = 111 − 1 13 14 w
222 111113
= 2 − 2w1+2w2+14w3
University of Victoria – CSC 445/545 – Summer 2021 13
Initial Observations (11)
Initial dictionary:
ζ =
w1 w2 =
cx
(3,6,2)·(x1,x2,x3)
1 4 −1 2 x1
2−−2 1 −2x2
w3 3101×3
wbAx
Rewritten dictionary:
University of Victoria – CSC 445/545 – Summer 2021
14
ζ=
cT A−1b cT A−1w
111113 − w1+ w2+14w3 2 2 2
x1 3 1 1 0w1 222
x2 = 8− 0 1 2w2
x3 3−1−11w3 222
x A−1b A−1 w
Initial Observations (12)
ζ = 111 − 1w1 − 13w2 − 14w3 222
x1 = 32 − 12w1 − 12w2
x2 = 8 − w2 − 2w3 x3 = 32 + 12w1 + 12w2 − w3
The dictionary above is the result of applying the three pivots (x1 entering, w1 leaving), (x2 entering, w2 leaving) and (x3 entering, w3 leaving) to the initial dictionary.
University of Victoria – CSC 445/545 – Summer 2021 15
Initial Observations (13)
ζ = 111 − 1w − 13w − 14w 2 21 22 3
x1 = 32 − 12w1 − 12w2
x2 = 8 − w2 − 2w3
111 1 13
ζ= 2−2w1−2w2−14w3
x1 3 1 1 0w1 222
x2= 8−0 1 2w2
x3 3 −1 −1 1 w3
x = 3 + 1w + 1w − w 3221223 222
Notice that the pivoted dictionary matches the algebraic formulation exactly.
University of Victoria – CSC 445/545 – Summer 2021 16
Initial Observations (14)
ζ = 111 − 1w1 − 13w2 2 2 2
cT A−1b cT A−1w
− 14w3 x2 = 8 − w2 − 2w3
111113
x1 = 3 − 1w1 − 1w2 222
ζ = − 2
2
w1 + w2 + 14w3 2
311
x1 3 1 1 0w1 222
x2 = 8− 0 1 2w2
x3 3−1−11w3 222
x A−1b A−1 w
x= +w+w−w 3221223
You may have noticed that the steps required
are elementary row operations, and therefore
a type of Gaussian elimination. It turns out that using pivoting to exchange all non-basic and basic variables (as was the case in the example above) is equivalent to inverting the matrix A.
to perform a single pivot in a Simplex dictionary that a sequence of pivot operations is essentially
University of Victoria – CSC 445/545 – Summer 2021 17
Initial Observations (15)
cT A−1b cT A−1w
111 1 13
ζ = 2 − 2w1 − 2w2 − 14w3 ζ= 111 −1w1−13w2−14w3 x=3−1w−1w 222
1 2 21 22 x1 31 1 0w1 x=8−w−2w 222
2 2 3 x2 = 8− 0 1 2w2
x = 3 + 1w + 1w − w x3 3 −1 −1 1 w3 3221223 222
x A−1b A−1 w
The point of this example was to show that the Simplex Method as we already know it is really a combination of ordinary linear algebra operations. We can now use this observation to reconceptualize the algorithm in purely linear algebraic terms.
University of Victoria – CSC 445/545 – Summer 2021 18
Equational Form (1)
Notation Warning: As usual, we have to juggle different notation here. In particular, the names A and c will be defined differently for the discussion of linear algebraic methods, both to avoid having to use weird extra symbols and for consistency with the books (which also suddenly change the meaning of those names for this topic).
University of Victoria – CSC 445/545 – Summer 2021 19
Equational Form (2)
Standard Form
max. 3×1+6×2+2×3 s.t. 4×1 − x2 +2×3 −2×1 + x2 −2×3 x1 + x3
x1,x2,x3
≤1 ≤2 ≤ 3 ≥ 0
Equational Form
3×1 + 6×2 + 2×3
4×1 − x2 +2×3 +x4 =1
−2×1 + x2 −2×3 1×1 + x3
+x5 =2 + x6 = 3
First, it is helpful to use a different representation than the dictionaries that we have used so far.
University of Victoria – CSC 445/545 – Summer 2021 20
Equational Form (3)
Standard Form
max. 3×1+6×2+2×3 s.t. 4×1 − x2 +2×3 −2×1 + x2 −2×3 x1 + x3
x1,x2,x3
≤1 ≤2 ≤ 3 ≥ 0
Equational Form
3×1 + 6×2 + 2×3
4×1 − x2 +2×3 +x4 =1
−2×1 + x2 −2×3 1×1 + x3
+x5 =2 + x6 = 3
The representation on the right is the equational form of the LP. It is basically a rear- ranged form of the (initial) dictionary, with the slack variables integrated into the constraint expressions and the bounds kept separate.
University of Victoria – CSC 445/545 – Summer 2021 21
Equational Form (4)
3×1 + 6×2 + 2×3
4×1 −2×1 1×1
−
+
x2 x2
+ 2×3 − 2×3 + x3
+ x4
= 1
= 2 + x6 = 3
To improve the consistency between optimization variables and slack variables (which, from the point of view of the algorithm, are no different), the slack variables in an LP with n optimization variables and m constraints will be numbered xn+1,xn+2,…,xn+m instead of w1,…,wm.
University of Victoria – CSC 445/545 – Summer 2021 22
+ x5
Equational Form (5)
3×1 + 6×2 + 2×3 + 0x4 + 0x5 + 0x6
4×1 − x2 + 2×3 + x4 + 0x5 + 0x6 = 1 −2×1 + x2 − 2×3 + 0x4 + x5 + 0x6 = 2 1×1 + 0x2 + x3 + 0x4 + 0x5 + x6 = 3
Note that one consequence of this renumbering is that the objective function must be defined as a function of all xi . It is easy to achieve this by setting the coefficients of xn+1, . . . , xn+m to zero.
University of Victoria – CSC 445/545 – Summer 2021 23
Equational Form (6)
Standard Form
max. c ̃Tx ̃
s.t. A ̃x ̃ = b
x ̃ ≥0
The equational form of an LP can be represented algebraically as shown above. Since we will want to use the names A and c in the equational form, the names A ̃ and c ̃ are used in the standard form representation to avoid ambiguity.
University of Victoria – CSC 445/545 – Summer 2021 24
Equational Form
max. cTx
s.t. Ax = b
x≥0
Equational Form (7)
Standard Form
max. c ̃Tx ̃
s.t. A ̃x ̃ = b
x ̃ ≥0
In particular, we have
A=A ̃ Im , ci=
where Im is the m × m identity matrix. University of Victoria – CSC 445/545 – Summer 2021
c ̃ ifi≤n i
Equational Form
max. cTx
s.t. Ax = b
x≥0
0
otherwise
25
Equational Form (8)
Standard Form
max. c ̃Tx ̃
s.t. A ̃x ̃ = b
x ̃ ≥0
(We also have x ̃ = (x1,x2,…,xn) and x = (x1,x2,…,xn+m), but that may have been obvious)
University of Victoria – CSC 445/545 – Summer 2021 26
Equational Form
max. cTx
s.t. Ax = b
x≥0
Equational Form (9)
Equational Form
max. cTx
s.t. Ax = b
x≥0
Notice that equational form (like dictionary form) doesn’t contain any inequalities besides the non-negativity constraints.
University of Victoria – CSC 445/545 – Summer 2021 27
Equational Form (10)
Equational Form
max. cTx
s.t. Ax = b
x≥0
To model the Simplex Method with this representation, we will need to find ways to
Represent which variables are basic and non-basic.
Find the value of each variable given a particular choice of basis.
Choose entering and leaving variables (in accordance with some pivoting rule). Model the pivot operation.
University of Victoria – CSC 445/545 – Summer 2021 28
Managing the Basis (1)
x1 2 4 0 1 0 0 0x2
x3 Ax=1 1 1 0 1 0 0x4
1 0 0 0 0 1 0
0 1 -1 0 0 0 1
Suppose that the variables x2, x4, x5 and x7 are basic.
x5 x 6 x7
University of Victoria – CSC 445/545 – Summer 2021
29
Managing the Basis (2)
x1 x2 2 4 0 1 0 0 0 x2 4 1 0 0 2 0 0 x4
0 1 -1 0 0 0 1 x5 x 6
1 0 0 1 0 -1 0 x1 x 3
x3 x5
Ax=1 1 1 0 1 0 0x4=1 0 1 0 1 1 0x7
1 0 0 0 0 1 0 0 0 0 0 1 0 1
x7
The product Ax is unchanged if the columns of the matrix and rows of the vector x are
permuted (as long as the same permutation is applied to both).
University of Victoria – CSC 445/545 – Summer 2021 30
x6
Managing the Basis (3)
4 1 0 0 2 0 0 x4 x5
Ax=1 0 1 0 1 1 0x7=
AB
AN
xB
x N
0 0 0 0 1 0 1 1 0 0 1 0 -1 0
x1 x 3 x6
x2
Therefore, we can rearrange A and x to separate the basic and non-basic variables, producing the block-decomposition
University of Victoria – CSC 445/545 – Summer 2021
31
Ax =
AB
AN x
= AB xB + AN xN
xB
N
Managing the Basis (4)
Ax=1 1 1 0 1 0 0x4
1 0 0 0 0 1 0
2 4 0 1 0 0 0 x3
0 1 -1 0 0 0 1 x6
ANxN= x3 1 0 1 x6
4 1 0 0x2 1 0 1 0 x4
x1 x2
ABxB = 0 0 0 0x5
1 0 0 1 x7
2 0 0
0 -1 0
7
In practice it isn’t actually necessary to rearrange the real columns of A to achieve this decomposition, since as long as the indices of the basic (and non-basic) variables are known, each sub-matrix can be extracted directly from A.
University of Victoria – CSC 445/545 – Summer 2021 32
x
x 1 5
x 110
Managing the Basis (5)
Question: If we have a particular basis, and form the decomposition Ax = AB xB + AN xN ,
how can we obtain the values of the variables xi ?
University of Victoria – CSC 445/545 – Summer 2021 33
Managing the Basis (6)
Therefore, we can use the equational form
Ax = b
and the decomposition to obtain
Ax = AB xB + AN xN ABxB +ANxN =b.
Assuming that the matrix AB is invertible1, this gives the identity xB = A−1 (b − ANxN) = A−1b − A−1ANxN.
At the beginning of each iteration of the Simplex Algorithm (when we know that the non-basic variables xN are zero), we will have
xB = A−1b − A−1ANxN = A−1b − A−1AN0 = A−1b. BBBBB
1We will demonstrate later that in the context of the Simplex Method, this is a reasonable assumption.
University of Victoria – CSC 445/545 – Summer 2021 34
BBB
Managing the Basis (7)
Similarly, we can separate the objective vector c into cB and cN , such that cTx=c Tx +c Tx ,
BBNN
and by similar logic as the previous slide, conclude that the expansion of the objective function for a particular basis is
c Tx +c Tx =c TA−1b−A−1A x +c Tx =c TA−1b−c TA−1A x +c Tx . BBNNBB BNNNNBBBBNNNN
The numerical objective value will then be the result of evaluating the expression above for the case xN = 0:
ζ∗ =c TA−1b. BB
Notice that this formula incorporates not only the objective coefficient vector c but also the constraint expressions (in the matrix AB) and the constraint bounds (the vector b). This is one illustration of the significance of duality to linear programs.
University of Victoria – CSC 445/545 – Summer 2021 36
Managing the Basis (8)
Finally, for a particular basis, we will need to determine the coefficients of the objective function in terms of the non-basic variables, to facilitate pivot selection. That is, we will need an expansion of the objective function similar to the top row of the dictionary form:
ζ = ζ∗ − zT x
where ζ∗ is a constant and the only non-zero coefficients of z correspond to non-basic
variables (as is the case in dictionary form). Using the same decomposition as on the
previousslides,wecanwritezTx=z Tx +z Tx withtheunderstandingthatz =0 BBNN B
(since basic variables should never have non-zero coefficients in the objective row of a dictionary).
We already have ζ∗ = c T A−1b from the previous slide, so we only need an expression for BB
the coefficients zN in the objective expansion.
University of Victoria – CSC 445/545 – Summer 2021 37
Managing the Basis (9)
The expansion of c T x (from Slide 36) is
cTx=c Tx +c Tx =c TA−1b−c TA−1A x +c Tx .
BBNNBB BBNNNN
Notice that an extra term involving xN was created when the value of xB was substituted
into the equation. We can rearrange the equation on the right to obtain cTx=c TA−1b−c TA−1A −c Tx
where and
BB BBNNN =ζ∗−z Tx
NN
z T =c TA−1A −c T NBBNN
z =(c TA−1A −c T)T =(A−1A )Tc −c . NBBNN BNBN
University of Victoria – CSC 445/545 – Summer 2021
38
Primal vs. Dual (1)
Primal
ζ∗
ζ =c TA−1b − ((A−1A )Tc −c )Tx BB BNBNN
xB = A−1b − A−1ANxN BB
The linear algebraic derivations from the previous slides can be visualized using pseudo- dictionary notation.
University of Victoria – CSC 445/545 – Summer 2021 39
zN
Primal vs. Dual (2)
ζ∗
ζ =c TA−1b − ((A−1A )Tc −c )Tx BB BNBNN
xB = A−1b − A−1ANxN BB
Question: What is the dual dictionary?
Primal
University of Victoria – CSC 445/545 – Summer 2021 40
zN
Primal vs. Dual (3)
−ζ∗
x B
−ξ =−c TA−1b
Dual
(A−1b)Tz BBBB
zN =(A−1AN)TcB −cN − −(A−1AN)TzB BB
Applying the usual negative-transpose transformation to the primal dictionary yields the dual dictionary above, in terms of the dual variables z.
University of Victoria – CSC 445/545 – Summer 2021 41
−
Primal vs. Dual (4)
−ζ∗
x B
−ξ =−c TA−1b
Dual
(A−1b)Tz BBBB
zN =(A−1AN)TcB −cN − −(A−1AN)TzB BB
Notice that there is a lack of “symmetry” in this construction. For example, the primal dictionary has the equation x = A−1b − … while the dual dictionary has the much more
BB
complicated equation zN = (A−1 AN )T cB − cN − … in its place. B
University of Victoria – CSC 445/545 – Summer 2021
42
−
Primal vs. Dual (5)
−ζ∗
x B
−ξ =−c TA−1b
Dual
(A−1b)Tz BBBB
zN =(A−1AN)TcB −cN − −(A−1AN)TzB BB
This lack of symmetry is mostly due to the dual (in the form above) being specified using the natural terminology of the primal problem. For example, the dual above was derived using the equational form of the primal problem (which was constructed by taking the m × n constraint matrix of the primal problem and augmenting it to an m × (n + m) matrix).
University of Victoria – CSC 445/545 – Summer 2021 43
−
Primal vs. Dual (6)
−ζ∗
x B
−ξ =−c TA−1b
Dual
(A−1b)Tz BBBB
zN =(A−1AN)TcB −cN − −(A−1AN)TzB BB
If the dual was constructed ‘from scratch’, the equational form would be constructed by tak- ing an n×m matrix (the negative transpose of the primal constraint matrix) and augmenting it to an n×(m+n) matrix.
University of Victoria – CSC 445/545 – Summer 2021 44
−
Simplex via Linear Algebra (1)
Given a linear program
max. cTx
s.t. Ax = b
x≥0
in equational form, along with a feasible basis B ⊆ {1, 2, . . . , n + m}, with |B| = m, we
can now write the Simplex Algorithm in linear algebraic terms.
In this discussion, we will treat B and N as sets of variable indices, and also adopt the convention that notation like xB refers to a restriction of the vector x to the indices in B. Critically, we do not treat xB as a separate entity, just a subset of the actual vector x (so any changes to xB automatically apply to the corresponding indices of x).
University of Victoria – CSC 445/545 – Summer 2021 45
Simplex via Linear Algebra (2)
The notation used here is essentially the same as that used in Chapter 6 of the Vanderbei book, with one major exception. We will use the names B and N to refer to sets of indices (the basic and non-basic variables), and we will use the names AB and AN to refer to the restrictions of the constraint matrix A to basic and non-basic variables.
The Vanderbei book uses the symbols B and N where we will use B and N, and it uses B and N where we will use AB and AN.
University of Victoria – CSC 445/545 – Summer 2021 46
Simplex via Linear Algebra (3)
Assuming that the basis B is feasible (that is, that AB is invertible and xB = A−1b ≥ 0), B
each step of the Simplex Method involves the following parts.
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector
BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution
B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
University of Victoria – CSC 445/545 – Summer 2021 47
Simplex via Linear Algebra (4)
zN =(A−1AN)TcB −cN. B
value
ζ∗ =c TA−1b BB
1. Compute the objective and the objective coefficient vector
If the basis B corresponds to an optimal solution
(so the algorithm can termi
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The full expansion of the objective function is ζ=ζ∗−z Tx .
NN
If zN ≥ 0, then there is no way to increase the objective value by increasing a non-basic variable. This corresponds to the case where every coefficient is negative in the dictionary version of the algorithm.
zN ≥ 0,
nate).
University of Victoria – CSC 445/545 – Summer 2021 49
Simplex via Linear Algebra (5)
1. Compute the objective and the objective coefficient vector
If the basis B corresponds to an optimal solution
(so the algorithm can termi
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The reason that zN ≥ 0 is the terminating condition (instead of zN ≤ 0 as you might expect)
is that the product z T x is subtracted in the formula for ζ (which flips the sign of the NN
condition).
zN =(A−1AN)TcB −cN. B
value
zN ≥ 0,
University of Victoria – CSC 445/545 – Summer 2021
50
ζ∗ =c TA−1b BB
nate).
Simplex via Linear Algebra (6)
zN =(A−1AN)TcB −cN. B
value
ζ∗ =c TA−1b BB
1. Compute the objective and the objective coefficient vector
If the basis B corresponds to an optimal solution
(so the algorithm can termi
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
If the solution is optimal, then the optimal objective value ζ∗ can be computed and returned (it is not strictly necessary to actually compute ζ∗ if the algorithm has not finished).
zN ≥ 0,
nate).
University of Victoria – CSC 445/545 – Summer 2021 51
Simplex via Linear Algebra (7)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables. 3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The vector zN = (A−1AN )T cB − cN contains the objective coefficients for each non-basic B
variable.
University of Victoria – CSC 445/545 – Summer 2021
52
Simplex via Linear Algebra (8)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables. 3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
To choose the entering variable xj by the largest coefficient rule, we would choose j to be an index of z (not zN, which is a subset of z) with the smallest (negative) value.
To choose the entering variable xj by Bland’s rule, we would choose j to be the first index of a negative value in z.
University of Victoria – CSC 445/545 – Summer 2021 53
Simplex via Linear Algebra (9)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
For example if B = {1,4}, N = {2,3,5} and zN = (7,−3,−4), then we would have z = (0,7,−3,0,−4).
The entering variable chosen with the largest coefficient rule would be x5 and the entering variable chosen with Bland’s rule would be x3.
University of Victoria – CSC 445/545 – Summer 2021 54
Simplex via Linear Algebra (10)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
To choose a leaving variable, we will first need to determine the largest value to which we can increase our entering variable xj .
University of Victoria – CSC 445/545 – Summer 2021 55
Simplex via Linear Algebra (11)
From Slide 34, we know that
when all non-basic variables are equal to zero.
What happens if we increase a non-basic variable xj (j ∈/ B) to a non-zero value?
x =A−1b BB
University of Victoria – CSC 445/545 – Summer 2021 56
Simplex via Linear Algebra (12)
+ 4×2
− 4×2
− 3×2
+ x2
ζ = 0 + 8×1
x4 = 8 − 2×1
x5 = 4 − x1 − x3
x6 =1− x1
x7 = 2
For some context, consider the dictionary above, with basis B = {4, 5, 6, 7}, and suppose x2 is chosen as the entering variable.
+ 2×3
University of Victoria – CSC 445/545 – Summer 2021 57
+ x3
Simplex via Linear Algebra (13)
ζ = x4= x5 = x6 = x7=
0 + 8×1 −2×1 − x1 − x1
+ 4×2
+ 2×3 − x3 + x3
8 4
The leaving variable is determined by a combination of the current values of the basic variables (that is, xB) and the coefficient of the entering variable x2 in each basis row.
University of Victoria – CSC 445/545 – Summer 2021 58
− 4×2
− 3×2
1 2
+ x2
Simplex via Linear Algebra (14)
ζ =0+8×1 x= −2x
xB
∆xB 4
+ 4×2 + 2×3
x=−x −x =−t
x 4
x5
8
8 4 1
41
4
3
− 4×2
− 3×2
5 1
x6=−x1 x7 2 −1
x7 =
3 x 6 1 0 + x3
2
+ x2
In the case where x2 is increased to a (potentially) non-zero value t and all other non- basic variables remain fixed at zero, the value of the basic variables can be modeled by the equation on the right. Notice the sign change resulting from the vector subtraction (this is for consistency with the system of equations derived earlier).
University of Victoria – CSC 445/545 – Summer 2021 59
Simplex via Linear Algebra (15)
ζ = 0 + 8×1 x= −2x
+ 2×3
xB
∆xB 4
+ 4×2
x=−x −x =−t
x 4
x5
8
8 4 1
4 1
4
3
− 4×2
− 3×2
5 1
x6=−x1 x7 2 −1
x7 =
3 x 6 1 0 + x3
2
+ x2
In the derivation on the next few slides, we will refer to the vector of basis coefficients of the entering variable as ∆xB.
Only those basic variables with positive entries in ∆xB are candidates to be the leaving
variable.
University of Victoria – CSC 445/545 – Summer 2021 60
Simplex via Linear Algebra (16)
Working backwards from the conclusion of Slide 34 (or by using the dictionary form on Slide 39), we have
xB =A−1b−A−1ANxN BB
(where the term A−1ANxN normally vanishes since xN = 0). B
In the case where we only want to increase one variable (xj ), we know that only one entry of xN will be non-zero, so the product ANxN will evaluate to xj times the column of AN corresponding to xj. By the definition of AN, this will just be the jth column of the larger matrix A, giving
A−1ANxN =A−1Ajxj, BB
(where Aj is the column vector corresponding to the jth column of A).
University of Victoria – CSC 445/545 – Summer 2021 61
Simplex via Linear Algebra (17)
Working backwards from the conclusion of Slide 34 (or by using the dictionary form on Slide 39), we have
xB =A−1b−A−1ANxN BB
(where the term A−1ANxN normally vanishes since xN = 0). B
In of
in
definition of of A−1ANxN =A−1Ajxj,
the
case
where
we
only w
ant
to
crease
one
variable
(xj ),
we
know
that
only
one
entry
xN
will b
e
non-
zero,
so t
he p
roduct
AN xN
will
eval
ua
te
to
xj ti
mes
the c
olumn
of
AN
cor
res
ponding
to x
j.
By
the
AN,
this
will
just
be
the
jth co
lumn
the
larger
A, giving
(where Aj is the column vector corresponding to the jth column of A).
matrix
University of Victoria – CSC 445/545 – Summer 2021
62
BB
Simplex via Linear Algebra (18)
Working backwards from the conclusion of Slide 34 (or by using the dictionary form on Slide 39), we have
Question: What should we do if the (alleged) explanation below looks like word salad? xB =A−1b−A−1ANxN
(where the term A−1ANxN normally vanishes since xN = 0). B
BB
In of
in
definition of of A−1ANxN =A−1Ajxj,
the
case
where
we
only w
ant
to
crease
one
variable
(xj ),
we
know
that
only
one
entry
xN
will b
e
non-
zero,
so t
he p
roduct
AN xN
will
eval
ua
te
to
xj ti
mes
the c
olumn
of
AN
cor
res
ponding
to x
j.
By
the
AN,
this
will
just
be
the
jth co
lumn
the
larger
A, giving
(where Aj is the column vector corresponding to the jth column of A).
matrix
University of Victoria – CSC 445/545 – Summer 2021
63
BB
Simplex via Linear Algebra (19)
Answer: Consider the following example. Suppose we have N = {3, 5, 8, 9} and
1 2 3 4
AN=5 6 7 8 9 10 11 12
x3 xN=x5.
x 8 x9
By definition, each column of AN is the column of A corresponding to a non-basic variable (so the first column of AN is column 3 of A, the second column of AN is column 5 of A, etc.).
Suppose we increase the value of the non-basic variable x8 to a positive value t. The expression ANxN would then be
1 2 3 40 3 t
5 6 7 8 0=t 7 9 10 11 12 0 11
which is just the value of t multiplied by the column of AN corresponding to x8, which will just be column 8 of the original matrix A.
University of Victoria – CSC 445/545 – Summer 2021 64
Simplex via Linear Algebra (20)
Define a vector ∆x with ∆xN = 0 and ∆xB = A−1Aj. B
Setting xj to a positive value t will change the values of the basic variables from xB to xB −A−1Ajxj =xB −t∆xB
B
and since we need to ensure that no variables go negative, we need xB −t∆xB ≥0.
The largest increase t is therefore
(Note that the indexing for the min function uses the regular x vectors, not the versions
restricted to B)
University of Victoria – CSC 445/545 – Summer 2021 65
t = min ∆xi >0
xi i∈B ∆xi
Simplex via Linear Algebra (21)
ζ = 0 + 8×1 x= −2x
+ 2×3
xB ∆xB 8 −4
+ 4×2
x=−x −x =−t
8 4 1
4 1
x 4
x5
4 −3
+ 4×2
+ 3×2
5 1
x6=−x1 x7 2 −1
x7 =
3 x 6 1 0 + x3
2
+ x2
In cases where ∆xi ≤ 0 for all i (so there are no terms to compare inside the min function), the value of t should be interpreted as +∞, implying that the value of xj can be arbitrarily large and hence that the LP is unbounded.
University of Victoria – CSC 445/545 – Summer 2021 66
Simplex via Linear Algebra (22)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables. 3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The leaving variable will be some variable xi for which xi =t.
∆xi
If multiple variables qualify, ties are broken by the pivot selection rule as usual. For example,
Bland’s rule will always choose the lowest numbered candidate.
University of Victoria – CSC 445/545 – Summer 2021 67
Simplex via Linear Algebra (23)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
Due to the way that t was selected, the value of xj when it enters the basis will be t, and the value of xi will be zero. Since t is positive, this guarantees that, as long as the basis was feasible at the beginning of the step, the new basis will also be feasible.
University of Victoria – CSC 445/545 – Summer 2021 68
Simplex via Linear Algebra (24)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
Once the entering variable xj and leaving variable xi have been selected, the pivot step requires updating any stored data to reflect the new basis.
This requires setting B ← B ∪{j}−{i} and N ← N ∪{i}−{j}, as well as updating any stored data for x, z and ζ.
University of Victoria – CSC 445/545 – Summer 2021 69
Simplex via Linear Algebra (25)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
A naive pivoting step could update B and N (as on the previous slide) and then fully compute x ←A−1b
BB xN ← 0
zB ← 0
zN ←(A−1AN)TcB −cN
B
ζ∗ ←c TA−1b BB
University of Victoria – CSC 445/545 – Summer 2021
70
Simplex via Linear Algebra (26)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables. 3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
It is possible to save some computation by updating some of the data instead of recomputing it. For example, before updating the sets B and N, the value of x can be adjusted by setting
xB ← xB − t∆xB (which will set the leaving variable xi to zero) xj ←t
University of Victoria – CSC 445/545 – Summer 2021 71
Simplex via Linear Algebra (27)
1. Compute the objective value ζ∗ = c T A−1b and the objective coefficient vector BB
zN = (A−1AN )T cB − cN . If zN ≥ 0, the basis B corresponds to an optimal solution B
(so the algorithm can terminate).
2. Choose an entering variable j ∈ N from among the non-basic variables.
3. Choose a leaving variable i ∈ B from among the basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
Pseudocode for the linear algebraic version of the Simplex Method is given on the next slide.
The Vanderbei book also contains pseudocode for the primal and dual Simplex Methods using linear algebra (see Figure 6.1 on Page 102). The version in the book is designed to illustrate the duality more clearly, so it is a bit more technically complicated than the version on the next slide. For example, it computes a vector ∆z as part of the process of recomputing z, since doing so makes it more obvious that the vector z is the dual version
of the vector x.
University of Victoria – CSC 445/545 – Summer 2021 72
Simplex via Linear Algebra (28)
procedure PrimalSimplex(A, b, c, B, N)
//Compute initial value of x
x ←A−1b BB
x←0 N
ifx ̸≥0then B
Error: Initial basis is not feasible. end if
while true do
//Part 1: Compute z and check for optimality
z←0 B
z ←(A−1AN)Tc −c NBBN
ifz ≥0then N
Optimal: Compute and return ζ∗ = c T A−1b BB
end if
//Part 2: Choose entering variable
j ← Some index in N such that zj < 0 (depending on pivot rule)
//Part 3: Choose leaving variable
∆x ← A−1Aj BB
∆x ←0 N
t ← min ∆xi >0
(Check for unboundedness; see Slide 66 for details)
xi i∈B ∆xi
i ← Some index in B such that xi /∆xi = t (depending on pivot rule)
//Part 4: Update for next iteration
x ←x −t∆x BBB
xj ←t
B ← B ∪ {j} − {i} N ← N ∪ {i} − {j}
end while
end procedure
University of Victoria – CSC 445/545 – Summer 2021 73
Why is it called a basis? (1)
Virtually all of the derivation in the previous section depended on the basis matrix AB being invertible. In order to justify that the linear algebraic simplex method is sound, we will need to demonstrate that, at each step of the algorithm, AB is invertible.
University of Victoria – CSC 445/545 – Summer 2021 74
Why is it called a basis? (2)
Question: Can we show that any collection of m columns from the m × (n + m) matrix A is guaranteed to be invertible?
University of Victoria – CSC 445/545 – Summer 2021 75
Why is it called a basis? (3)
max. 3×1+6×2+2×3 s.t. 4×1 − x2 +2×3 −2×1 + x2 −2×3 x1 + x3
x1,x2,x3
≤1 ≤2 ≤ 3 ≥ 0
Answer: No. Even in our running example LP we can construct a basis for which the matrix AB is singular.
University of Victoria – CSC 445/545 – Summer 2021
76
Why is it called a basis? (4)
x2 6
−1 1
x4 x5
1
1
x1 x3 x6
cT = 3 2
421
−1 1 0 AB=1 0 1
000 4 2 0
AN=−2 −2 0 111
A = − 2 − 2 1 1
Basic:{2, 4, 5}
b = 2 1 3
Non-basic:{1, 3, 6}
If x2, x4 and x5 are chosen as the basis, the matrix AB has a row of all zeros (and is therefore definitely not invertible).
University of Victoria – CSC 445/545 – Summer 2021 77
Why is it called a basis? (5)
x2 6
−1 1
x4 x5
1
1
x1 x3 x6
cT = 3 2
421
−1 1 0 AB=1 0 1
000 4 2 0
AN=−2 −2 0 111
A = − 2 − 2 1 1
Basic:{2, 4, 5}
b = 2 1 3
Non-basic:{1, 3, 6}
Experiment: Could we make any more sense of the basis {x2,x4,x5} using dictionaries?
University of Victoria – CSC 445/545 – Summer 2021 78
Why is it called a basis? (6)
ζ = 0 + 3×1
x4 = 1 − 4×1
x5 = 2 + 2×1
x6 = 3 − x1
+ 6×2
+ 2×3 − 2×3 + 2×3 − x3
Here is the initial dictionary for the LP (with slack variables named using the same convention as the rest of this lecture). To reach the basis {x2,x4,x5}, it is necessary to pivot with x2 entering and x6 leaving.
University of Victoria – CSC 445/545 – Summer 2021 79
+
−
x2 x2
Why is it called a basis? (7)
ζ = 0 + 3×1
x4 = 1 − 4×1
x5 = 2 + 2×1
x6 = 3 − x1
+ 6×2
+ 2×3 − 2×3 + 2×3 − x3
+
−
x2 x2
Pivoting with x2 entering and x6 leaving is impossible, though, since it would require division by zero. Therefore, even with the dictionary based method, we can’t expect to actually realize every possible combination of variables as a basis.
University of Victoria – CSC 445/545 – Summer 2021 80
Why is it called a basis? (8)
x2 6
−1 1
x4 x5
1
1
x1 x3 x6
cT = 3 2
421
−1 1 0 AB=1 0 1
000 4 2 0
AN=−2 −2 0 111
A = − 2 − 2 1 1
Basic:{2, 4, 5}
b = 2 1 3
Non-basic:{1, 3, 6}
Therefore, a problem like the one above does not necessarily affect the soundness of the Simplex Method, as long as we can show that the matrix AB is non-singular for every basis that is actually visited.
University of Victoria – CSC 445/545 – Summer 2021 81
Why is it called a basis? (9)
Question: Can we show that, when the Simplex Method is started from a feasible basis (for which AB is invertible), the new basis matrix A′B produced by any valid pivot step will also be invertible?
Answer: Yes. The proof is somewhat perfunctory (see Lemma 5.6.1 in Matouˇsek and G ̈artner) and is less of an insight into linear programming as an exercise in housekeeping.
University of Victoria – CSC 445/545 – Summer 2021 82
Why is it called a basis? (10)
ζ = 0 + 3×1
x4 = 1 − 4×1
x5 = 2 + 2×1
x6 = 3 − x1
+ 6×2
+ 2×3 − 2×3 + 2×3 − x3
Using the dictionary form, it might be more clear why any pivoting operation preserves invertibility. Any valid pivot operation (that is, a pivot where the ratio between entering and leaving variable is well-defined) is performed using elementary row operations, which preserve invertibility of the underlying system.
University of Victoria – CSC 445/545 – Summer 2021 83
+
−
x2 x2
Why is it called a basis? (11)
ζ = 0 + 3×1
x4 = 1 − 4×1
x5 = 2 + 2×1
x6 = 3 − x1
+ 6×2
+ 2×3 − 2×3 + 2×3 − x3
More intuitively, since any pivot operation is reversible (that is, after pivoting with xj entering and xi leaving, the previous dictionary can always be restored by pivoting with xi entering and xj leaving).
University of Victoria – CSC 445/545 – Summer 2021 84
+
−
x2 x2
Why is it called a basis? (12)
Question: Each pivot operation preserves invertibility, but what about the initial basis?
Answer: For initially-feasible LPs, the initial basis will consist entirely of slack variables, and due to the definition of equational form, this will result in AB being the m × m identity matrix (which is invertible).
For LPs which are not initially feasible, a two-phase method (covered later) can be used to find a feasible point (using the same constraint matrix A) starting from an initially feasible problem.
University of Victoria – CSC 445/545 – Summer 2021 85
Why is it called a basis? (13)
During the Simplex Algorithm, the columns which comprise the matrix AB will always form a basis for the column space of the larger matrix A, which is why the term ‘basis’ is used in this context.
University of Victoria – CSC 445/545 – Summer 2021 86
Dual Simplex via Linear Algebra (1)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The derivation of the Dual Simplex Method is similar, with the obvious transposition of the vectors x and z.
University of Victoria – CSC 445/545 – Summer 2021 87
Dual Simplex via Linear Algebra (2)
−ξ∗
x B
−ξ =−c TA−1b
Dual
(A−1b)Tz BBBB
zN =(A−1AN)TcB −cN − −(A−1AN)TzB BB
As noted on Slide 42, the linear algebraic derivation of the dual dictionary seems more complicated than the derivation of the primal dictionary, since the derivation was made using the primal equational form.
University of Victoria – CSC 445/545 – Summer 2021 88
−
Dual Simplex via Linear Algebra (3)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The leaving variable index i ∈ B is selected from among those indices with xi < 0 (where the choice depends on the pivot rule). Since this is the dual problem, the leaving variable is zi (notxi).
University of Victoria - CSC 445/545 - Summer 2021 89
Dual Simplex via Linear Algebra (4)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The major difference occurs in Step 3. As in the primal Simplex Method, we want to increase the variable zi to some positive value.
University of Victoria - CSC 445/545 - Summer 2021 90
Dual Simplex via Linear Algebra (5)
The dual dictionary expression derived on Slide 41 (also shown on Slide 88) gives us z =(A−1A )Tc −c −−(A−1A )Tz
NBNBNBNB (where the second bracketed term normally vanishes since zB = 0).
The term involving zB can be rewritten as
−(A−1AN)TzB =−ATN(ATB)−1zB
B
In the case where we only want to increase one variable (zi ), we know that only one entry of zB will be non-zero, but it is not possible to apply the same trick as in the primal algorithm (see Slide 64) due to the inverse calculation for (ATB )−1.
Instead, construct a vector u of the same dimension as zB , where each index uk is defined
as follows.
1 if index k of zB corresponds to variable zi
uk = 0 otherwise
University of Victoria - CSC 445/545 - Summer 2021 91
Dual Simplex via Linear Algebra (6)
Define a vector ∆z with ∆zB = 0 and ∆zN = −ATN (ATB )−1u.
Now, the effect of increasing variable zi to a positive value s will result in a change of −s ∆zN
to the values in zN . As in the primal case, we must enforce the invariant zN −s∆zN ≥0
The largest increase s is therefore
(Note that the indexing for the min function uses the regular z vectors, not the versions
restricted to N)
University of Victoria - CSC 445/545 - Summer 2021 92
s = min ∆zj >0
zj j∈N ∆zj
Dual Simplex via Linear Algebra (7)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables. 4. Perform the pivot (at minimum, this requires modifying B and N).
In the event that the argument to the min function in the calculation
s = min ∆zj >0
zj j∈N ∆zj
is empty (that is, if there are no indices such that ∆zj > 0), the dual problem is unbounded (implying that the primal problem is infeasible).
University of Victoria – CSC 445/545 – Summer 2021 93
Dual Simplex via Linear Algebra (8)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables. 4. Perform the pivot (at minimum, this requires modifying B and N).
The entering variable will be some variable zj for which zj =s.
∆zj
If multiple variables qualify, ties are broken by the pivot selection rule as usual.
University of Victoria – CSC 445/545 – Summer 2021 94
Dual Simplex via Linear Algebra (9)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
The pivot step is essentially the same as in the primal version, although it is possible to avoid recomputing z by making the following incremental update before modifying the basis.
zN ← zN − s∆zN (which will set the leaving variable xi to zero) zi ←s
University of Victoria – CSC 445/545 – Summer 2021 95
Dual Simplex via Linear Algebra (10)
1. Compute the objective value −ξ∗ = c T A−1b and the dual objective coefficient vector BB
x = A−1b. If x ≥ 0, the basis B corresponds to an optimal solution (so the BBB
algorithm can terminate).
2. Choose a leaving variable i ∈ B from among the basic variables.
3. Choose an entering variable j ∈ N from among the non-basic variables.
4. Perform the pivot (at minimum, this requires modifying B and N).
Pseudocode for the dual simplex method is given on the next slide.
University of Victoria – CSC 445/545 – Summer 2021 96
Dual Simplex via Linear Algebra (11)
procedure DualSimplex(A, b, c, B, N) z←0
B
z ←(A−1AN)Tc −c
NBBN ifz ̸≥0then
N
Error: Initial basis is not dual feasible. end if
while true do
//Part 1: Compute x and check for optimality
x ←A−1b BB
x←0 N
ifx ≥0then B
Optimal: Compute and return ζ∗ = c T A−1b BB
end if
//Part 2: Choose leaving variable
i ← Some index in B such that xi < 0 (depending on pivot rule)
//Part 3: Choose entering variable
Compute the vector u as described on Slide 91
∆z ←0 B
∆zN ← −ATN (ATB )−1 u zj
s ← min (Check for unboundedness; see Slide 92 for details) j∈N ∆zj
∆zj >0
j ← Some index in N such that zj /∆xj = s (depending on pivot rule)
//Part 4: Update for next iteration
z ←z −s∆z NNN
zi ←s
B ← B ∪ {j} − {i} N ← N ∪ {i} − {j}
end while
end procedure
University of Victoria – CSC 445/545 – Summer 2021 97
Solving LPs (1)
One of the benefits of the linear algebraic Simplex Algorithms is that they can be easily started from any feasible basis. To start the dictionary version of the Simplex Algorithm from an arbitrary basis, it is usually necessary to perform a sequence of pivots to set up the dictionary.
This aspect is especially useful when trying to solve LPs that may not be initially feasible. It is possible to find initially feasible solutions using an auxiliary problem (in the same way as for the dictionary method), but using a combination of the linear algebraic primal and dual algorithms, it is also possible to solve arbitrary LPs with a concise two-phase method.
University of Victoria – CSC 445/545 – Summer 2021 98
Solving LPs (2)
Given an LP on n optimization variables and m constraints in equational form
max. cTx
s.t. Ax = b
x≥0
(where A is a m × (n + m) matrix), the following procedure can be used to solve the LP.
If the LP is primal-feasible (that is, if b ≥ 0), call PrimalSimplex(A, b, c, B, N) with N = {1, 2, . . . , n} and B = {n + 1, n + 2, . . . , n + m} to solve the LP.
If the LP is dual-feasible (that is, if c ≤ 0), call DualSimplex(A, b, c, B, N) with N = {1, 2, . . . , n} and B = {n + 1, n + 2, . . . , n + m} to solve the LP.
If the LP is neither primal-feasible or dual-feasible:
1. Call DualSimplex(A,b,0,N,B) with N = {1,2,…,n} and B = {n + 1,n + 2,…,n + m}
(note that the vector 0, which is always dual-feasible, is substituted for the objective function).
2. Let B′ and N′ be the basic and non-basic variables (respectively) for the optimal solution to the
auxiliary LP from Step 1. The basis B′ will be both primal-feasible and dual-feasible for the original LP. Call PrimalSimplex(A, b, c, N′, B′) to solve the original LP.
University of Victoria – CSC 445/545 – Summer 2021 99
The Revised Simplex Method (1)
In both the primal and dual algorithms, the most computationally demanding steps are those which involve inverse matrices.
University of Victoria – CSC 445/545 – Summer 2021 100
The Revised Simplex Method (2)
A calculation involving an inverse matrix and a vector, like
u ← M−1v,
can be carried out more efficiently by solving the linear system Mu = v, which avoids
having to explicitly compute the inverse of M and multiply it by v.
Asymptotically1, solving the system Mu = v requires n3 operations, whereas computing
3
the inverse M−1 requires n3 numerical operations (and the extra step of multiplying by v
requires n2 numerical operations).
1We can’t use big-O notation here because the constant factors are significant.
University of Victoria – CSC 445/545 – Summer 2021 101
The Revised Simplex Method (3)
There are also numerical disadvantages to computing and using inverse matrices. Explicitly computing an inverse matrix is more likely to produce numerical instability than solving a system of equations.
Even in cases where an inverse matrix has already been computed, it can be numerically safer to solve a linear system instead of multiplying a vector by the inverse.
University of Victoria – CSC 445/545 – Summer 2021 102
The Revised Simplex Method (4)
In the primal algorithm, the following steps use the inverse matrix A−1: B
x ← A−1b (to compute the initial value of x) BB
zN ←(A−1AN)TcB −cN B
∆xB ← A−1Aj B
These can be modified to avoid the use of an inverse: To compute xB , solve the linear system AB xB = b.
Tocomputez ,firstsolveATv=c toobtainv=(A−1)Tc ,thenset NBBBB
z N ← A TN v − c N .
To compute ∆xB , solve the linear system AB ∆xB = Aj
University of Victoria – CSC 445/545 – Summer 2021 103
The Revised Simplex Method (5)
In the dual algorithm, the following steps use the inverse matrix A−1: B
zN ←(A−1AN)TcB −cN (tocomputetheinitialvalueofz) B
x ←A−1b BB
∆zN ←−ATN(ATB)−1u
Adaptations of the first two calculations are shown on the previous slide.
Tocompute∆zN,firstsolveATBv=utoobtainv=(ATB)−1u,thenset∆zN ←−ATNv.
University of Victoria – CSC 445/545 – Summer 2021 104
The Revised Simplex Method (6)
When the algorithm is implemented to avoid the use of inverses (using the adaptations on the previous two slides), it is called the Revised Simplex Algorithm.
In addition to saving operations by skipping inverse calculations, and avoiding numerical instability caused by computing inverse matrices, the linear algebraic nature of the Revised Simplex Method makes it easy to incorporate other innovations from numerical linear algebra. The dictionary-based method does not have this advantage.
For example, by using LU decompositions to solve linear systems, it is possible to save operations by reusing the decomposition within each iteration (since every set of linear systems involves AB in some way) and across iterations (by making small updates to the factorization instead of recomputing it at each step).
University of Victoria – CSC 445/545 – Summer 2021 105
The Revised Simplex Method (7)
If numerical linear algebra sounds exciting, you may want to try one of the following:
Be a CSC 545 student and choose a related topic for your presentation this semester. Take CSC 449 (Numerical Linear Algebra) next time it is offered1.
Take CSC 490 (Directed Study) with a numerical linear algebra focus.
1Last offered in Spring 2011
University of Victoria – CSC 445/545 – Summer 2021 106