CSC 445/545 – Summer 2021
The Network Simplex Method: Graph Theoretic Interpretations
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
July 15, 2021
What is a basis? (1)
-6
d
15 a1b8e
5 -21 23
Consider the network shown above.
University of Victoria – CSC 445/545 – Summer 2021
2
c
0
What is a basis? (2)
min. s.t.
xab +xbd +xcb +8xeb +2xec +5xed −xab
xab −xbd +xcb + xeb
−xcb + xec
= −5 = 2 = 0
The LP formulation of the min-cost flow problem is shown above.
xbd
+ xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
University of Victoria – CSC 445/545 – Summer 2021 3
What is a basis? (3)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
−1 -5
1−111 2 A= −11b=0
1 1 6
−1 −1 −1 -3
Problem: The constraint matrix A does not have full rank. By construction, each column corresponds to one arc and has two non-zero entries: 1 and -1. Therefore, the matrix A cannot directly be used as the equational form matrix of the LP.
University of Victoria – CSC 445/545 – Summer 2021 4
What is a basis? (4)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
−1 -5
1−111 2 A= −11b=0
1 1 6
−1 −1 −1 -3
As mentioned earlier, the linear dependence can be resolved by either adding slack variables
(which will increase the rank of the resulting matrix) or deleting redundant constraints.
University of Victoria – CSC 445/545 – Summer 2021 5
What is a basis? (5)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
−1 -5
1−111 2 A= −11b=0
1 1 6
−1 −1 −1 -3
Notice that the constraints (which encode the flow balance between vertices) are actually overspecified: If we enforce the flow balance for |V | − 1 vertices, the remaining vertex will automatically be balanced as well.
University of Victoria – CSC 445/545 – Summer 2021 6
What is a basis? (6)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
−1 -5
1−111 2 A= −11b=0
1 1 6
−1 −1 −1 -3
Idea: Select a vertex and delete its balance constraint. For consistency, in this course we
will always choose the first vertex as the root (although any choice is suitable).
University of Victoria – CSC 445/545 – Summer 2021 7
What is a basis? (7)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
1−111 2 ′ −11′0
A= 1 1b=6
−1 −1 −1 -3
Let A′ and b′ denote the result of deleting the first row from A and the first element of b.
University of Victoria – CSC 445/545 – Summer 2021 8
What is a basis? (8)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
1−111 2 ′ −11′0
A= 1 1b=6
−1 −1 −1 -3
We can prove that, for any connected graph, the matrix A′ , which has |V | − 1 rows, will have full rank (i.e. rank |V | − 1)
University of Victoria – CSC 445/545 – Summer 2021 9
What is a basis? (9)
min. xab +xbd +xcb +8xeb +2xec +5xed xab −xbd +xcb + xeb
xbd
= 2
s.t.
−xab = −5
−xcb + xec
= 0 + xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
We will refer to the vertex whose constraint was deleted as the root vertex. In these slides, we will continue to write down the deleted constraint, but highlight the row in purple (see above) to indicate that the constraint should be ignored.
University of Victoria – CSC 445/545 – Summer 2021 10
What is a basis? (10)
min. xab +xbd +xcb +8xeb +2xec +5xed xab −xbd +xcb + xeb
xbd
= 2
s.t.
−xab = −5
−xcb + xec
In the LP formulation, each arc (u,v) is represented by one optimization variable xuv.
= 0 + xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
University of Victoria – CSC 445/545 – Summer 2021 11
What is a basis? (11)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
1−111 2 ′ −11′0
A= 1 1b=6
−1 −1 −1 -3
The matrix A′ of non-root balance constraints will have |V |−1 rows, so any basis will consist of |V | − 1 optimization variables, each corresponding to a single arc.
University of Victoria – CSC 445/545 – Summer 2021 12
What is a basis? (12)
xab xbd xcb xeb xec xed cT = 1 1 1 8 2 5
1−111 2 ′ −11′0
A= 1 1b=6
−1 −1 −1 -3
Question: What properties are required for a collection of |V | − 1 arcs to form a basis?
University of Victoria – CSC 445/545 – Summer 2021 13
What is a basis? (13)
Eachprimaloptimizationvariablexuv correspondstoanedge(u,v)∈E,sowecan interpret the basis as being a collection of arcs (and accordingly, the vector xB will contain the flow values of each arc in the basis).
For a particular collection B to be a basis, we require the basis matrix AB to be invertible. One way to understand invertibility in this case is to observe that, if AB is invertible, then
there will be a solution xB to the equation
ABxB =b
for any choice of supply values b. The solution xB must be a balanced flow, although for the purposes of invertibility, it is not relevant whether xB ≥ 0 (that is, the flow values may be infeasible).
University of Victoria – CSC 445/545 – Summer 2021 14
What is a basis? (14)
00
bf
adeg
0000
c
h
00
For example, consider the network above (with only the supply values shown). To qualify as a basis, a particular collection of edges must be able to produce a balanced flow for any supply values (assuming that the supply values sum to zero).
University of Victoria – CSC 445/545 – Summer 2021 15
What is a basis? (15)
00
bf
adeg
0000
c
h
00
Consider the collection of |V | − 1 = 7 edges above. Is this a basis?
University of Victoria – CSC 445/545 – Summer 2021 16
What is a basis? (16)
00
bf
55 ad5eg
05050
c
h
0 -5
Setting the supply values of d and h as above, we can see that there is a balanced flow using only the selected edges.
University of Victoria – CSC 445/545 – Summer 2021 17
What is a basis? (17)
00
bf
-5 -5
a d-5e g
0 -50-50
c
h
05
Negating the supply values of d and h still produces a balanced (but infeasible) flow.
University of Victoria – CSC 445/545 – Summer 2021 18
What is a basis? (18)
00
bf
adeg
5 -50 0
c
h
00
However, if we modify the supply values to add an imbalance between a and d, there is no balanced flow using only the selected edges. Specifically, no flow can be sent from a to d without using the non-basic variables xbd or xcd .
University of Victoria – CSC 445/545 – Summer 2021 19
What is a basis? (19)
00
bf
adeg
5 -50 0
c
h
00
Therefore, there will be no solution to ABxB = b for this particular supply vector b, and this set of edges will not be a basis.
University of Victoria – CSC 445/545 – Summer 2021 20
What is a basis? (20)
00
bf
adeg
0000
c
h
00
On the other hand, the set of edges above is a basis, since flow can be sent between any two vertices (although not necessarily feasibly).
University of Victoria – CSC 445/545 – Summer 2021 21
What is a basis? (21)
00
bf
adeg
0000
c
h
00
Observation: For a collection of edges B to be a basis, the subgraph (V,B) must be connected.
University of Victoria – CSC 445/545 – Summer 2021 22
What is a basis? (22)
Fact: A connected graph on |V | vertices with |V | − 1 edges must be a tree. Therefore, the set of basic edges B must comprise a spanning tree of the network.
University of Victoria – CSC 445/545 – Summer 2021 23
What is a basis? (23)
Fact: If B is a spanning tree, then AB will be invertible. Therefore, any spanning tree B is a valid (although not necessarily feasible) basis.
University of Victoria – CSC 445/545 – Summer 2021 24
Computing Balanced Flows (1)
Task: Given the basis shown above (on the right), compute the corresponding balanced flow (which may not necessarily be feasible).
University of Victoria – CSC 445/545 – Summer 2021 25
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
? a?b?e ?
c
Computing Balanced Flows (2)
The balanced flow corresponding to a particular basis is the solution xB to the equation AB xB = b, so we could compute the flow with a general linear algebraic method.
University of Victoria – CSC 445/545 – Summer 2021 26
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
? a?b?e ?
c
Computing Balanced Flows (3)
However, since the basis is a spanning tree, it is possible to completely infer the flow on each edge by working inwards from the leaves of the tree.
University of Victoria – CSC 445/545 – Summer 2021 27
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
? a?b?e ?
c
Computing Balanced Flows (4)
Although there are multiple (equivalent) ways to frame the resulting algorithm, since we have already chosen a vertex to serve as the root of the spanning tree, we will work from the leaves of the spanning tree upward (toward the root vertex a).
University of Victoria – CSC 445/545 – Summer 2021 28
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
? a?b?e ?
c
Computing Balanced Flows (5)
For example, the node d has a supply of −6, and since flow can only reach d via the edge bd, we know that the flow value xbd must equal 6.
University of Victoria – CSC 445/545 – Summer 2021 29
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6
a?b?e ?
c
Computing Balanced Flows (6)
Similarly, since vertex c has a supply value of zero, the flow along xcb must be zero.
University of Victoria – CSC 445/545 – Summer 2021 30
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6
a?b?e 0
c
Computing Balanced Flows (7)
The supply value of vertex e is 3, so to balance the flow, 3 units must be sent across the basic edge e, b, giving xeb = 3.
University of Victoria – CSC 445/545 – Summer 2021 31
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a?b3e 0
c
Computing Balanced Flows (8)
Vertex b has supply value −2, along with 3 units of incoming flow (from vertex e) and 6 units of outgoing flow (to d), for a net supply of −5. Therefore, we must set xab = 5 to ensure balance.
University of Victoria – CSC 445/545 – Summer 2021 32
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a5b3e 0
c
Computing Balanced Flows (9)
Notice that the resulting flow values are balanced. In general, this technique will produce a balanced flow for any spanning tree as long as the network has an overall supply balance (that is, if all supply values sum to zero).
University of Victoria – CSC 445/545 – Summer 2021 33
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a5b3e 0
c
Computing Balanced Flows (10)
Task: Construct a balanced flow for this basis.
University of Victoria – CSC 445/545 – Summer 2021 34
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
? a?b?e
?
c
Computing Balanced Flows (11)
The leaves in this case (interpreting the basis as a rooted tree with root a) are vertices c and d. We therefore can set xec = 0 and xed = 6.
The vertex e then has a net supply of −3.
University of Victoria – CSC 445/545 – Summer 2021 35
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6
a?b?e 0
c
Computing Balanced Flows (12)
The only way to balance vertex e is to send 3 units of flow from b to e. The arc (e, b) points in the wrong direction, so we set xeb = −3 (that is, we send 3 units in the wrong direction along (e, b)).
University of Victoria – CSC 445/545 – Summer 2021 36
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a?b -3 e
0
c
Computing Balanced Flows (13)
The net supply at vertex b is then −5, so we set xab = 5. The resulting flow is balanced (but not feasible).
University of Victoria – CSC 445/545 – Summer 2021 37
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a5b -3 e
0
c
Computing Balanced Flows (14)
Although it may seem counterintuitive to compute infeasible flows, remember that this step is only intended to compute the values of each basic variable xuv (i.e. to solve AB xB = b). The same values of xB would be obtained with a linear algebraic method (although possibly with much more work).
University of Victoria – CSC 445/545 – Summer 2021 38
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
d
6 a5b -3 e
0
c
Computing Balanced Flows (15)
Task: Compute the balanced flow for this network and basis.
University of Victoria – CSC 445/545 – Summer 2021 39
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
g
f
h?i ??
?d ?
e
?c ?
a?b
Computing Balanced Flows (16)
Starting at the nodes furthest from the root and working backwards up the spanning tree produces the results above.
University of Victoria – CSC 445/545 – Summer 2021 40
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
g
f
h6i ??
?d ?
e
?c ?
a?b
Computing Balanced Flows (17)
Starting at the nodes furthest from the root and working backwards up the spanning tree produces the results above.
University of Victoria – CSC 445/545 – Summer 2021 41
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
g
f
h6i 10 5
?d ?
e
?c ?
a?b
Computing Balanced Flows (18)
Starting at the nodes furthest from the root and working backwards up the spanning tree produces the results above.
University of Victoria – CSC 445/545 – Summer 2021 42
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
g
f
h6i 10 5
3d -3
e
?c 0
a?b
Computing Balanced Flows (19)
Starting at the nodes furthest from the root and working backwards up the spanning tree produces the results above.
University of Victoria – CSC 445/545 – Summer 2021 43
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
g
f
h6i 10 5
3d -3
e
-12
a -6 b
c
0
Primal and Dual Variables (1)
-6
d
15 a1b8e
5 -21 23 c
0
Question: Each primal variable xuv represents the flow on arc (u,v). Can we derive an interpretation of the dual optimization and slack variables in terms of flows?
University of Victoria – CSC 445/545 – Summer 2021 44
Primal and Dual Variables (2)
min. xab +xbd +xcb +8xeb +2xec +5xed xab −xbd +xcb + xeb
xbd
= 2
s.t.
−xab = −5
−xcb + xec
= 0 + xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
Each primal constraint represents the flow balance of a single vertex. Therefore, each vertex v will be represented by a dual optimization variable yv .
University of Victoria – CSC 445/545 – Summer 2021 45
Primal and Dual Variables (3)
min. xab +xbd +xcb +8xeb +2xec +5xed xab −xbd +xcb + xeb
xbd
= 2
s.t.
−xab = −5
−xcb + xec
= 0 + xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
We also know that each primal optimization variable xuv (which corresponds to edge uv) will have a corresponding dual slack variable zuv , and that by complementary slackness, one of the pair must always equal zero.
University of Victoria – CSC 445/545 – Summer 2021 46
Primal and Dual Variables (4)
min. xab +xbd +xcb +8xeb +2xec +5xed xab −xbd +xcb + xeb
xbd
= 2
s.t.
−xab = −5
−xcb + xec
= 0 + xed = 6 − xeb− xec− xed=−3
xuv ≥ 0forall (u,v)∈E
Fact: For a particular edge (u, v ), at most one of xuv and zuv may be non-zero. In particular, if (u,v) is basic, then zuv will be zero, and if (u,v) is non-basic, then xuv will be zero.
University of Victoria – CSC 445/545 – Summer 2021 47
Primal and Dual Variables (5)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+ 6yd − 3ye + yd
− ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E
−ya
Constructing the dual (using the dual form from the previous lecture) yields the LP above. Note that the dual optimization variables yv are unconstrained (and can have negative values), although the dual slack variables zuv are non-negative.
University of Victoria – CSC 445/545 – Summer 2021 48
Primal and Dual Variables (6)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+6yd−3ye + yd
−ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E
−ya
Note for later: By duality, any flow that is both primal and dual feasible is optimal. For the purposes of this LP, a flow is primal feasible if each primal flow variable xuv is non-negative and dual feasible if each dual slack variable zuv is non-negative. The dual optimization variables yv can be negative, positive or zero in a feasible flow.
University of Victoria – CSC 445/545 – Summer 2021 49
Primal and Dual Variables (7)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+ 6yd − 3ye + yd
− ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E
−ya
One of the dual variables (ya in this case) will correspond to the root vertex. Since the root vertex was deleted from the primal constraint system, we have to treat its dual counterpart differently than the other dual variables.
University of Victoria – CSC 445/545 – Summer 2021 50
Primal and Dual Variables (8)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+ 6yd − 3ye + yd
− ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E
−ya
Recall that the root vertex was originally chosen as a way to ensure that the basis matrix would be invertible (that is, the root vertex was chosen as a way to address the overspecifi- cation of the constraint system). Since the root vertex does not participate in the constraint system, the phantom dual variable ya can be treated as zero.
University of Victoria – CSC 445/545 – Summer 2021 51
Primal and Dual Variables (9)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+ 6yd − 3ye + yd
− ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
−ya
zuv ≥ 0forall (u,v)∈E Question: Given a basis B ⊆ E(G) and a choice of root vertex, is it possible to compute
the value of each yv ?
University of Victoria – CSC 445/545 – Summer 2021 52
Primal and Dual Variables (10)
-6
d
15 a1b8e
5 -21 23 c
0
Yes. Consider the basis B = {(a,b),(b,d),(c,b),(e,b)}. We know that the dual slack variable zuv is zero when the arc (u,v) is in the basis, so we can solve the dual constraint system to find the value of each yv .
University of Victoria – CSC 445/545 – Summer 2021 53
Primal and Dual Variables (11)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+6yd−3ye + yd
−ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E Since we have defined the dual variable ya for the root vertex to be zero, and since we know
that(a,b)∈B,wehavezab =0,giving
−ya +yb +zab =−1 ⇒ yb =1.
University of Victoria – CSC 445/545 – Summer 2021
54
−ya
Primal and Dual Variables (12)
max. −5ya + 2yb s.t. + yb − yb yb yb
− yc yc
+ 6yd − 3ye + yd
− ye
− ye yd − ye
+zab=1 +zbd=1 +zcb=1 +zeb=8 + zec = 2 + zed = 5
zuv ≥ 0forall (u,v)∈E
−ya
We can extend this logic to iteratively find the value of every yv, since each vertex v is guaranteed to be incident to at least one basic arc (and therefore will have at least one dual constraint where the corresponding slack variable is zero).
University of Victoria – CSC 445/545 – Summer 2021 55
Computing Dual Variables (1)
While it is possible to simply solve the dual constraint equations (with linear algebra) to find the dual variables, there is also a tree-based method (which has the added benefit of exposing a particular interpretation of the dual variables).
University of Victoria – CSC 445/545 – Summer 2021 56
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
?
d
abe
???
c
?
Computing Dual Variables (2)
Task: Given the basis shown above, compute the value of each dual variable yv .
University of Victoria – CSC 445/545 – Summer 2021 57
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
?
d
abe
???
c
?
Computing Dual Variables (3)
(In this and future examples, we will write dual values next to each vertex in the right pane of the diagram)
University of Victoria – CSC 445/545 – Summer 2021 58
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
?
d
abe
???
c
?
Computing Dual Variables (4)
By definition, the root vertex a has ya = 0.
University of Victoria – CSC 445/545 – Summer 2021 59
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
?
d
abe
0??
c
?
Computing Dual Variables (5)
Each dual constraint corresponds to a single edge (u,v) ∈ E and has the form −yu +yv +zuv =cost(u,v).
If the edge (u,v) is basic (implying that zuv = 0) and the value of either of yu or yv is known, the equation can easily be solved for of the other variable.
We can therefore work out the value of each dual variable by moving down the spanning tree from the root.
University of Victoria – CSC 445/545 – Summer 2021 60
Computing Dual Variables (6)
Observation: Each dual variable yv will equal the cost of moving one unit of flow from the root to vertex v using only basic edges (where it is assumed that moving flow in the wrong direction along an arc negates the cost).
University of Victoria – CSC 445/545 – Summer 2021 61
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
?
d
abe
01?
c
?
Computing Dual Variables (7)
Observation: Each dual variable yv will equal the cost of moving one unit of flow from the root to vertex v using only basic edges (where it is assumed that moving flow in the wrong direction along an arc negates the cost).
University of Victoria – CSC 445/545 – Summer 2021 62
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
2
d
abe
01 -7
c
0
Computing Dual Variables (8)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 63
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
???
g
f
?
hi
?
e
d
?
c
?
ab
??
Computing Dual Variables (9)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 64
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
???
g
f
?
hi
?
e
d
?
c
?
ab
0?
Computing Dual Variables (10)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 65
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
???
g
f
?
hi
1
e
d
?
c
?
ab
0 -1
Computing Dual Variables (11)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 66
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
???
g
f
-1
hi
1
e
d
3
c
-2
ab
0 -1
Computing Dual Variables (12)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 67
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-8? 14
g
f
-1
hi
1
e
d
3
c
-2
ab
0 -1
Computing Dual Variables (13)
Task: Compute the dual variable values for the network and basis shown above.
University of Victoria – CSC 445/545 – Summer 2021 68
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-818 14
g
f
-1
hi
1
e
d
3
c
-2
ab
0 -1
Computing Dual Slack Variables (1)
So far, we have found a graph theoretic interpretation for the following aspects of the LP formulation.
Basis: The basis corresponds to a subset B ⊆ E of |V | − 1 edges, which must comprise a spanning tree of the graph.
Primal Flows (xuv ): The value of each primal variable xuv is the number of units of flow across that arc. Non-basic edges always have a flow value of zero.
Dual Optimization Variables (yv ): The value of each dual variable yv is the total cost of moving one unit of flow from the root vertex to vertex v, using only basic edges.
University of Victoria – CSC 445/545 – Summer 2021 69
Computing Dual Slack Variables (2)
The only remaining unknowns are the dual slack variables zuv . We already observed that zuv = 0 if arc (u,v) is basic.
Otherwise, once the value of each dual optimization variable yv is known, we can compute the value of zuv for non-basic arcs (u,v) using the dual constraint equations
−yu +yv +zuv =cost(u,v).
University of Victoria – CSC 445/545 – Summer 2021
70
Computing Dual Slack Variables (3)
The dual slack values for the two non-basic edges zec and zed are shown on the diagram above (in the right pane).
University of Victoria – CSC 445/545 – Summer 2021 71
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
2
d
-4
abe
0 1 -5-7
c
0
Computing Dual Slack Variables (4)
The value of a dual slack variable zuv can be interpreted as describing the increase in cost associated with using edge (u,v) instead of the existing basic edges.
University of Victoria – CSC 445/545 – Summer 2021 72
Supply/Cost
-6
d
15 a1b8e
5 -21 23
c
0
Flow
2
d
-4
abe
0 1 -5-7
c
0
Computing Dual Slack Variables (5)
More concretely, zuv will equal the cost differential puv −pb
where
puv = cost of transporting one unit of flow from the root to u using basic edges, and then to v using edge (u,v).
pb = cost of transporting one unit of flow from the root to v using basic edges.
If zuv is negative, then it is cheaper to transport flow using edge (u,v) than with the current basis (and therefore it is advantageous to add (u,v) to the basis).
University of Victoria – CSC 445/545 – Summer 2021 73
Computing Dual Slack Variables (6)
The interpretation might be easier to visualize on the example above (to avoid having to deal with reverse-direction flow at first).
University of Victoria – CSC 445/545 – Summer 2021 74
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
bc
2 11
-6
3
d
Computing Dual Slack Variables (7)
Based on the values of the dual variables yc and yd , we can see that the costs of moving one unit of flow from the root to vertices c and d are 11 and 3, respectively.
University of Victoria – CSC 445/545 – Summer 2021 75
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
bc
2 11
-6
3
d
Computing Dual Slack Variables (8)
However, if we could use edge (d,c), the cost to move a unit of flow from the root to vertex c (viavertexd)wouldbeyd +cost((d,c))=5.
University of Victoria – CSC 445/545 – Summer 2021 76
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
bc
2 11
-6
3
d
Computing Dual Slack Variables (9)
The value zdc = −6 indicates the potential increase (or in this case, decrease, since the value is negative) in the cost of moving flow to the destination of the edge (d,c) (that is, vertex c) if the edge (d,c) was added to the basis.
University of Victoria – CSC 445/545 – Summer 2021 77
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
bc
2 11
-6
3
d
Computing Dual Slack Variables (10)
Notice that a negative value for zdc implies that the basis is not the most cost-effective, and such cases are also not dual feasible.
University of Victoria – CSC 445/545 – Summer 2021 78
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
bc
2 11
-6
3
d
Computing Dual Slack Variables (11)
After adding (d , c ) to the basis in place of (a, c ), notice that the resulting yc value is 11 + (−6) = 5, reflecting the improvement indicated by the value of zdc on the previous slides.
University of Victoria – CSC 445/545 – Summer 2021 79
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
6
bc
25
3
d
Computing Dual Slack Variables (12)
Also notice that the non-basic edge (a,c) has zab = 6, since adding (a,b) to the basis in place of (d,c) would increase the cost of moving flow to c by 6.
University of Victoria – CSC 445/545 – Summer 2021 80
Supply/Cost
a
7
2 11
bc
15
12
3
d
Flow
a
0
6
bc
25
3
d
Computing Dual Slack Variables (13)
The diagram above shows the dual slack values for the other example graph from earlier.
University of Victoria – CSC 445/545 – Summer 2021 81
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-818 14
g
f
-1
28h i
1
-7
d
3
e9
10 c -2
ab
0 -1
Complete Interpretation (1)
We now have a way to represent the entire state of the Simplex Method on a Minimum-Cost Flow problem using the graph itself, in the right pane of the diagram above.
University of Victoria – CSC 445/545 – Summer 2021 82
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-818 14
g
f
-1
28h 6 i 10 5
-7
3
e9
-12 10 c
3d
1
-3
0 a -6 b
0 -1
-2
Complete Interpretation (2)
The basis is a spanning tree (thick red edges) where each edge has an associated primal flow value. The non-basic edges each have an associated dual slack value. Each vertex has an associated dual optimization variable.
University of Victoria – CSC 445/545 – Summer 2021 83
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-818 14
g
f
-1
28h 6 i 10 5
-7
3
e9
-12 10 c
3d
1
-3
0 a -6 b
0 -1
-2
Complete Interpretation (3)
If all primal flow values are non-negative, the basis is primal feasible.
University of Victoria – CSC 445/545 – Summer 2021 84
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 5
-6
-6
e3
10 9 c
3d
-9
-1
3 a6b
0 -1
-2
Complete Interpretation (4)
If all dual slack variables are non-negative, the basis is dual feasible.
University of Victoria – CSC 445/545 – Summer 2021 85
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-811 7
g
f
-1
21h 6 i 10 7
5
8 e6
-6 1 c
6
8d
1
3
7
a9b 08
Complete Interpretation (5)
By strong duality, any basis which is both primal and dual feasible will be optimal for the minimum cost flow problem.
University of Victoria – CSC 445/545 – Summer 2021 86
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
91c
8d
-8
-6
12 a6b
0 -1
-2
Complete Interpretation (6)
Therefore, our next objective will be to develop a graph-theoretic interpretation of the piv- oting step, to allow the entire Simplex Method to be run on the graph directly.
University of Victoria – CSC 445/545 – Summer 2021 87
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
91c
8d
-8
-6
12 a6b
0 -1
-2