CS计算机代考程序代写 algorithm CSC 445/545 – Summer 2021

CSC 445/545 – Summer 2021
The Network Simplex Method: Dual Pivoting
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
July 11, 2021

Deriving a Dual Method (1)
The flow above is dual feasible, but not optimal (notice that there are basic edges which are not primal feasible).
University of Victoria – CSC 445/545 – Summer 2021 2
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6 -5
-14 d 0 4 0 14
0a3f9

Deriving a Dual Method (2)
Our goal in this lecture is to find a way to model the dual pivoting operation using the graph, and use the resulting Dual Network Simplex Method as the basis for a two-phase solver for arbitrary minimum cost flow instances.
University of Victoria – CSC 445/545 – Summer 2021 3
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6 -5
-14 d 0 4 0 14
0a3f9

Basis Updates and Dual Variables (1)
Before deriving a dual pivoting process, we will first revisit the updates needed to dual variables when the basis is modified.
University of Victoria – CSC 445/545 – Summer 2021 4
Supply/Cost
Flow
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (2)
Recall that the value of each dual variable yv represents the cost of transporting a single unit of flow from the root to vertex v using only basic edges.
University of Victoria – CSC 445/545 – Summer 2021 5
Supply/Cost
Flow
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (3)
Consider the basis above, and recall that after a pivot, only those vertices which are separated from the root by the removal of the leaving arc need to have their dual variables updated.
University of Victoria – CSC 445/545 – Summer 2021 6
Supply/Cost
Flow
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (4)
Suppose that the arc (b, d) leaves the basis in favour of the arc (c, d). Notice that zcd = −5, and recall that each dual slack value zuv corresponds to the cost differential between the current basis and a basis containing (u,v) instead.
University of Victoria – CSC 445/545 – Summer 2021 7
Supply/Cost
Flow
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (5)
After removing the leaving arc (b,d) from the basis, the spanning tree is split into the two components shown above.
University of Victoria – CSC 445/545 – Summer 2021 8
Supply/Cost
Flow
a
04
bc
d
83
ef
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (6)
To avoid notational confusion (in this and future examples), let C0 denote the component containing the root (purple) and C1 denote the other component.
University of Victoria – CSC 445/545 – Summer 2021 9
Supply/Cost
Flow
a
04
bc
d
83
ef
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (7)
We will treat C0 and C1 as sets of vertices (so we can make statements like a ∈ C0).
University of Victoria – CSC 445/545 – Summer 2021 10
Supply/Cost
Flow
a
04
bc
d
83
ef
0 b
4
a
23
71
d
3
24
c -2
-8 e
f 3

Basis Updates and Dual Variables (8)
Since the removal of the arc (b,d) from the basis results in C1 containing d,e and f, the dual values yd , ye and yf will need to be updated.
University of Victoria – CSC 445/545 – Summer 2021 11
Flow (Old Basis)
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
Flow (New Basis)
0
a
04
2b c3
52
d
?
83
?e f?

Basis Updates and Dual Variables (9)
Once the update is complete, the change to each affected dual variable is precisely the value that zcd had before the basis change.
University of Victoria – CSC 445/545 – Summer 2021 12
Flow (Old Basis)
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
Flow (New Basis)
0
a
04
2b c3
52
d
4
83
6e f0

Basis Updates and Dual Variables (10)
In general, if an arc (s,t) enters the basis, the change in the value of each affected dual variable (for vertices in C1) will be −zst if s ∈ C1 and zst if t ∈ C1.
University of Victoria – CSC 445/545 – Summer 2021 13
Flow (Old Basis)
0
a
22
2b c3
2 -5
d
9
83
11 e
f 5
Flow (New Basis)
0
a
04
2b c3
52
d
4
83
6e f0

Basis Updates and Dual Variables (11)
Now consider this variant of the previous graph, which has extra non-basic edges.
University of Victoria – CSC 445/545 – Summer 2021 14
Supply/Cost
Flow
0
a
22
2b c3 2 -5
16 d 7 9
83
11 e -4 f 5
4
a
23
0 b
c -2
71 7d9
3
24
-8e 2 f3

Basis Updates and Dual Variables (12)
We already know that, after a basis change, only those edges (u,v) where at least one endpoint lies in C1 require updates to their dual slack values zuv .
University of Victoria – CSC 445/545 – Summer 2021 15
Flow (Old Basis)
0
a
22
2b c3 2 -5
16 d 7 9
83
11 e -4 f 5
Flow (New Basis)
0
a
04
2b c3 ?2
?d? 4
83
6e?f0

Basis Updates and Dual Variables (13)
We also know that the dual slack variable for arc (u,v) is, in general, defined by the equality
constraint
−yu +yv +zuv =cost((u,v)).
University of Victoria – CSC 445/545 – Summer 2021
16
Flow (Old Basis)
0
a
22
2b c3 2 -5
16 d 7 9
83
11 e -4 f 5
Flow (New Basis)
0
a
04
2b c3 ?2
?d? 4
83
6e?f0

Basis Updates and Dual Variables (14)
We have seen that, when an arc (s,t) enters the basis, the dual values yv for each vertex in C1 will be adjusted by the value of zst.
As for the other dual slack values zuv , we can show that
􏰏 If both endpoints are in the same component (that is, if u, v ∈ C0 or u, v ∈ C1, zuv will
be unchanged.
􏰏 If vertex u is in the same component as vertex s (that is, if (u,v) and (s,t) bridge C0
and C1 in the same direction), the new value zu′v will equal z′ =z −z.
uv uv st
􏰏 If vertex u is in the same component as vertex t (that is, if (u,v) and (s,t) bridge C0 and C1 in opposite directions), the new value zu′v will equal
z′ =z +z. uv uv st
University of Victoria – CSC 445/545 – Summer 2021
17

Basis Updates and Dual Variables (15)
The updated dual slack values are shown on the right above.
University of Victoria – CSC 445/545 – Summer 2021 18
Flow (Old Basis)
0
a
22
2b c3 2 -5
16 d 7 9
83
11 e -4 f 5
Flow (New Basis)
0
a
04
2b c3 52
11 d 12 4
83
6e -4 f0

What is a Dual Pivot? (1)
In a dual pivot, the leaving variable (which will be primal infeasible) is selected first and an entering variable is then chosen to restore the basis and maintain dual feasibility.
University of Victoria – CSC 445/545 – Summer 2021 19
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6 -5
-14 d 0 4 0 14
0a3f9

What is a Dual Pivot? (2)
As with the entering variable in a primal pivot, the exact choice of leaving variable is subject to the pivot selection rule.
University of Victoria – CSC 445/545 – Summer 2021 20
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6 -5
-14 d 0 4 0 14
0a3f9

What is a Dual Pivot? (3)
Unless otherwise stated, we will use the network equivalent of the largest coefficient rule: The leaving arc will be chosen to be a primal infeasible arc with the smallest (negative) primal flow value.
University of Victoria – CSC 445/545 – Summer 2021 21
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6 -5
-14 d 0 4 0 14
0a3f9

What is a Dual Pivot? (4)
However, any primal infeasible arc is a valid candidate. For example, we could choose the arc (d,g) as the leaving arc.
University of Victoria – CSC 445/545 – Summer 2021 22
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
5c9h6 -2 13
-3 e 2
7 6 11
2b g7 6?
-14 d 0 4 0 14
0a3f9

What is a Dual Pivot? (5)
Recall from the previous lecture that deleting any arc from the spanning tree will separate the basis into exactly two subtrees.
University of Victoria – CSC 445/545 – Summer 2021 23
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
ch
-2
-3 e 2
b
g
6
-14 d 0
af

What is a Dual Pivot? (6)
Question: Which non-basic arc should be chosen to enter?
University of Victoria – CSC 445/545 – Summer 2021 24
Supply/Cost
1c 10 h2 1 13 3e1
3 2 10
5b g3 27 2d2 415
-4 a 12 f 0
Flow
c9h -2 13
-3 e 2 7 11
b
g
6?
-14 d 0
4 14 a3f

What is a Dual Pivot? (7)
Normally, we could reason about the selection of entering/leaving arcs by considering the implications of each choice on the objective function (with the understanding that the Simplex Method will always move toward a better objective value). However, the dual objective function (which is a linear combination of the dual variables yv ) is not very intuitive for this purpose.
Instead, we can reason about the implications of a particular pivot, and deduce the necessary behavior based on the restrictions imposed by the Dual Simplex Method.
We will explore the intuitive meaning of the dual objective function later in the lecture.
University of Victoria – CSC 445/545 – Summer 2021 25

What is a Dual Pivot? (8)
Before the pivot:
􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have xuv = 0 and zuv ≥ 0. 􏰏 The entering arc (s , t ) must have zst = 0 (and, ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. The basic requirements of any dual pivot are given above. University of Victoria - CSC 445/545 - Summer 2021 26 What is a Dual Pivot? (9) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have xuv = 0 and zuv ≥ 0. 􏰏 The entering arc (s , t ) must have zst = 0 (and, ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. The leaving arc will carry flow between C0 and C1. In order to remove it from the basis, we will need to choose an entering arc that can carry the same flow (so that the flow across the leaving arc can be reduced to zero). Additionally, since removing the leaving arc will disconnect the tree, the entering arc must restore the connection between C0 and C1. Therefore, the entering arc must also bridge between C0 and C1. University of Victoria - CSC 445/545 - Summer 2021 27 What is a Dual Pivot? (10) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have xuv = 0 and zuv ≥ 0. 􏰏 The entering arc (s, t) must have ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. The entering arc will be dual feasible (as will all other non-basic arc, since dual pivoting only makes sense on a dual feasible basis). zst = 0 (and, University of Victoria - CSC 445/545 - Summer 2021 28 What is a Dual Pivot? (11) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have xuv = 0 and zuv ≥ 0. 􏰏 The entering arc (s, t) must have ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. Additionally, we also expect that the entering arc will be primal feasible after the pivot, since the (normal) Simplex Method normally guarantees this. (Specifically, the entering arc on a dual pivot will be primal feasible afterwards, and the leaving arc on a primal pivot will be dual feasible afterwards) zst = 0 (and, University of Victoria - CSC 445/545 - Summer 2021 29 What is a Dual Pivot? (12) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have xuv = 0 and zuv ≥ 0. 􏰏 The entering arc (s, t) must have ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. Since the entering arc must carry the same flow as the leaving arc (between C0 and C1), the only way to ensure that the resulting flow value is primal feasible is to choose the entering arc to bridge between the components in the opposite direction to the leaving arc (since the leaving arc is primal infeasible). zst = 0 (and, University of Victoria - CSC 445/545 - Summer 2021 30 What is a Dual Pivot? (13) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have and 􏰏 The entering arc (s, t) must have ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. Finally, to ensure that the basis is dual feasible when the pivot is complete, we must ensure that every dual slack variable is non-negative. We saw earlier that the only dual slack values affected by the pivot will correspond to edges which bridge between the two components C0 and C1. xuv =0 zst = 0 University of Victoria - CSC 445/545 - Summer 2021 31 (and, zuv ≥0. What is a Dual Pivot? (14) Before the pivot: 􏰏 The leaving arc (u,v) will be primal infeasible: xuv < 0. 􏰏 The entering arc (s, t) will be dual feasible: zst ≥ 0. After the pivot: 􏰏 The leaving arc (u,v) must have and 􏰏 The entering arc (s, t) must have ideally, xst ≥ 0). 􏰏 The basis must be dual feasible. Suppose that an edge (p,q) bridging C0 and C1 is dual infeasible after the pivot. The interpretation of zpq < 0 is that the edge (p,q) is a lower cost route between C0 and C1. Therefore, to prevent any bridging edge from becoming dual infeasible, we must choose the entering arc to be the lowest cost candidate (so that no cheaper routes exist). xuv =0 zst = 0 University of Victoria - CSC 445/545 - Summer 2021 32 (and, zuv ≥0. What is a Dual Pivot? (15) We can also see that the entering arc must bridge the components in the opposite direction as the leaving arc by examining the equations for adjusting the dual slack variables. University of Victoria - CSC 445/545 - Summer 2021 33 What is a Dual Pivot? (16) The leaving arc (u,v) will have zuv = 0 before the pivot, so, to prevent the leaving arc from becoming infeasible, it is necessary to choose the entering arc (s, t) to bridge in the opposite direction(sothatzu′v=zuv+zst). University of Victoria - CSC 445/545 - Summer 2021 34 What is a Dual Pivot? (17) Since we also want to maintain dual feasibility among those arcs (p,q) that point in the same direction as the entering arc (s, t), we will choose (s, t) to have the smallest dual slack value, so that zp′ q = zpq − zst is never negative. University of Victoria - CSC 445/545 - Summer 2021 35 What is a Dual Pivot? (18) The arcs that bridge between C0 and C1 are shown above. Light blue arcs bridge between the components in the same direction as the leaving arc (d,g). Orange arcs bridge between the components in the opposite direction. University of Victoria - CSC 445/545 - Summer 2021 36 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow c9h 13 e b 11 ? g d 14 a3f What is a Dual Pivot? (19) Based on the deductions in the previous slides, we know that the entering arc must have the opposite direction as the leaving arc and, among all such arcs, have the minimum dual slack value. University of Victoria - CSC 445/545 - Summer 2021 37 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow c9h 13 e b 11 ? g d 14 a3f What is a Dual Pivot? (20) Therefore, the entering arc will be (g,e). University of Victoria - CSC 445/545 - Summer 2021 38 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow c9h 13 e b 11 ? g d 14 a3f The Dual Network Simplex Method (1) Dual Pivoting: Choose a primal infeasible basic arc l (using some pivot selection rule) as the leaving arc. Then, 􏰏 Identify the two components C0 and C1 created by removing l from the spanning tree (where it is assumed that the root vertex is in C0). 􏰏 Locate all edges that bridge C0 and C1 in the ‘opposite’ direction as l. 􏰏 Choose the entering arc e to be the opposite-directed edge with the smallest dual slack value. 􏰏 Set the flow value for arc e to be the negation of the flow on arc l. 􏰏 Update the dual variable values of all vertices in C1 and the dual slack values of all edges bridging the components. University of Victoria - CSC 445/545 - Summer 2021 39 The Dual Network Simplex Method (2) Task: Starting from the dual-feasible basis above, find an optimal flow using the Dual Network Simplex Method. University of Victoria - CSC 445/545 - Summer 2021 40 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 5c9h6 -2 13 -3 e 2 7 6 11 2b g7 6 -5 -14 d 0 4 0 14 0a3f9 The Dual Network Simplex Method (3) Iteration 1. Leaving arc is (a, b). University of Victoria - CSC 445/545 - Summer 2021 41 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 5c9h6 -2 13 -3 e 2 7 6 11 2b g7 6 -5 -14 d 0 4 0 14 0a3f9 The Dual Network Simplex Method (4) With (a,b) leaving, the entering arc is (d,a). The flow assigned to (d,a) will be 14 units. University of Victoria - CSC 445/545 - Summer 2021 42 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 5c h6 e 6 2b g7 ?d 0 0a3f9 4 The Dual Network Simplex Method (5) End of Iteration 1. Total cost is -4. University of Victoria - CSC 445/545 - Summer 2021 43 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 1c9h2 -2 13 -3 e 2 7 2 11 -2 b g 3 -8 -5 4d0 14 -4 14 0a7f5 The Dual Network Simplex Method (6) Iteration 2. Leaving arc is (d,b). University of Victoria - CSC 445/545 - Summer 2021 44 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 1c9h2 -2 13 -3 e 2 7 2 11 -2 b g 3 -8 -5 4d0 14 -4 14 0a7f5 The Dual Network Simplex Method (7) With (d, b) leaving, the entering arc is (c, h). The flow assigned to (c, h) will be 8 units. University of Victoria - CSC 445/545 - Summer 2021 45 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow 1c9h2 13 e 2 11 -2 b g 3 ? 4d -4 0a f5 The Dual Network Simplex Method (8) End of Iteration 2. Total cost is 68. University of Victoria - CSC 445/545 - Summer 2021 46 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -8c 8 h2 -2 22 5 e 10 7 -7 20 -11 b g 3 9 -13 13 d 0 14 -4 14 0a7f5 The Dual Network Simplex Method (9) Iteration 3. Leaving arc is (d,g). University of Victoria - CSC 445/545 - Summer 2021 47 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -8c 8 h2 -2 22 5 e 10 7 -7 20 -11 b g 3 9 -13 13 d 0 14 -4 14 0a7f5 The Dual Network Simplex Method (10) With (d,g) leaving, the entering arc is (f,d). The flow assigned to (f,d) will be 13 units. University of Victoria - CSC 445/545 - Summer 2021 48 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -8 c h 2 e -7 -11 b g 3 9? 13 d -4 0a7f5 14 The Dual Network Simplex Method (11) End of Iteration 3. Total cost is 250. University of Victoria - CSC 445/545 - Summer 2021 49 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -22 c 8 h -12 -2 22 5 e 10 7 -21 20 -25 b g -11 23 14 27 d 13 14 -4 13 0 a 21 f -9 The Dual Network Simplex Method (12) Iteration 4. Leaving arc is (c, e). University of Victoria - CSC 445/545 - Summer 2021 50 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -22 c 8 h -12 -2 22 5 e 10 7 -21 20 -25 b g -11 23 14 27 d 13 14 -4 13 0 a 21 f -9 The Dual Network Simplex Method (13) With (c, e) leaving, the entering arc is (e, b). The flow assigned to (e, b) will be 2 units. University of Victoria - CSC 445/545 - Summer 2021 51 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 -22 c Flow ? 22 e 7 -21 20 h -12 -25 b g -11 d -4 0 a f -9 The Dual Network Simplex Method (14) Optimal. Total cost is 264. University of Victoria - CSC 445/545 - Summer 2021 52 Supply/Cost 1c 10 h2 1 13 3e1 3 2 10 5b g3 27 2d2 415 -4 a 12 f 0 Flow -22 c 8 h -12 7 29 7 e 10 2 -28 27 -25 b g -11 23 14 27 d 13 14 -4 13 0 a 21 f -9 Another Example (1) Task: Starting from the dual-feasible basis above, find an optimal flow using the Dual Network Simplex Method. University of Victoria - CSC 445/545 - Summer 2021 53 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f -1 i -10 h -4 21 7 -5 3 e6 -2 d 1 -2 -6 1 c 6 7 a9b 08 Another Example (2) Iteration 1. Leaving arc is (h,g). University of Victoria - CSC 445/545 - Summer 2021 54 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f -1 i -10 h -4 21 7 -5 3 e6 -2 d 1 -2 -6 1 c 6 7 a9b 08 Another Example (3) With (h, g ) leaving, the entering arc is (g , f ). The flow assigned to (g , f ) will be 10 units. University of Victoria - CSC 445/545 - Summer 2021 55 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f -1 ?hi 21 1 e d 3 c 7 ab 08 Another Example (4) End of Iteration 1. Total cost is 170. University of Victoria - CSC 445/545 - Summer 2021 56 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 Another Example (5) Iteration 2. Leaving arc is (a, e). University of Victoria - CSC 445/545 - Summer 2021 57 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 Another Example (6) With (a, e) leaving, the entering arc is (b, a). The flow assigned to (b, a) will be 6 units. University of Victoria - CSC 445/545 - Summer 2021 58 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 hi 1 e d 3 ?c 7 a9b 08 Another Example (7) Optimal. Total cost is 224. University of Victoria - CSC 445/545 - Summer 2021 59 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 Economic Interpretation (1) Question: Ok, but what does the dual really mean? University of Victoria - CSC 445/545 - Summer 2021 60 Economic Interpretation (2) -5 c 59 a2 05 We can construct economic interpretations of the primal and dual LP that will allow us to better understand their relationship and the properties of extreme cases (like unbounded- ness). b University of Victoria - CSC 445/545 - Summer 2021 61 Economic Interpretation (3) -5 c 59 a2 05 The primal minimum cost flow problem is a logistics problem: Find the lowest-cost way to distribute flow across the network, equalizing supply and demand. b University of Victoria - CSC 445/545 - Summer 2021 62 Economic Interpretation (4) -5 c 59 a2 05 The dual problem can be viewed as finding fair prices for the resource, taking into account supplies and shipping costs. b University of Victoria - CSC 445/545 - Summer 2021 63 Economic Interpretation (5) -5 c 59 a2 05 We already know that a dual variable yv corresponds to the cost of shipping a single unit of flow to vertex v from the root of the spanning tree. More generally, we could show that the cost of shipping one unit from vertex u to vertex v will equal yv − yu . b University of Victoria - CSC 445/545 - Summer 2021 64 Economic Interpretation (6) -5 c 59 a2 05 Question: If you had to sell one unit of flow in city c, what would be a fair price? b University of Victoria - CSC 445/545 - Summer 2021 65 Economic Interpretation (7) -5 c 59 a2 05 (The question assumes that you must dispose of the resource, and you must therefore set a price such that a buyer can be found). b University of Victoria - CSC 445/545 - Summer 2021 66 Economic Interpretation (8) -5 c 59 a2 05 Obviously, you could set any price you wanted, but you would be undercut by a competitor if you overpriced the resource. It would also make no sense to underprice the resource (i.e. sell at a loss). b University of Victoria - CSC 445/545 - Summer 2021 67 Economic Interpretation (9) -5 c 59 a2 05 Since city c has a shortage of the resource, it is reasonable to assume that a market for sale exists. However, since the resource can be shipped in from other cities (directly from city b for $9 or from city b via city a for $7), the fair price would be at most $7. b University of Victoria - CSC 445/545 - Summer 2021 68 Economic Interpretation (10) -5 c 59 a2 05 In general, the fair price in a city with demand will equal the minimum cost associated with shipping the resource in from elsewhere. b University of Victoria - CSC 445/545 - Summer 2021 69 Economic Interpretation (11) -5 c 59 a2 05 Question: If you had to sell one unit of flow in city b, what would be a fair price? b University of Victoria - CSC 445/545 - Summer 2021 70 Economic Interpretation (12) -5 c 59 a2 05 City b has an oversupply, so there must not be any interested local consumers. On the other hand, one unit of flow does still have some value (since it could be sold in a neighbouring city). b University of Victoria - CSC 445/545 - Summer 2021 71 Economic Interpretation (13) -5 c 59 a2 05 Therefore, if you have to dispose of one unit of flow in city b, you could pay someone $7 to take that unit of flow (which would make it economically viable to ship it to city c and sell it). b University of Victoria - CSC 445/545 - Summer 2021 72 Economic Interpretation (14) -5 c 59 a2 05 The “fair price” could therefore be negative, in cases where the resource is undesirable in a particular context. b University of Victoria - CSC 445/545 - Summer 2021 73 Economic Interpretation (15) -5 c 59 a2 05 Although it may seem odd that we require that the resource be disposed of, even if doing so costs money, this is a reasonable requirement in many applications, such as electricity generation. It is relatively common for the wholesale price of electricity to be negative during times of high supply (e.g. bright days in areas with solar generation). b University of Victoria - CSC 445/545 - Summer 2021 74 Economic Interpretation (16) max. −5yb + 5yc s.t. + yc +zac =5 − yb +zba=2 − yb + yc + zbc = 9 zuv ≥ 0forall (u,v)∈E −ya ya The terms in the dual objective function are the total demand at each vertex multiplied by the fair price of the resource at that vertex. Notice that for vertex b, which has a supply of 5, the coefficient is −5. University of Victoria - CSC 445/545 - Summer 2021 75 Economic Interpretation (17) max. −5yb + 5yc s.t. + yc +zac =5 − yb +zba=2 − yb + yc + zbc = 9 zuv ≥ 0forall (u,v)∈E −ya ya We can interpret the dual objective function as maximizing the overall revenue from selling all units of flow at each vertex (according to the supply/demand at each vertex). University of Victoria - CSC 445/545 - Summer 2021 76 Economic Interpretation (18) max. −5yb + 5yc s.t. + yc +zac =5 − yb +zba=2 − yb + yc + zbc = 9 zuv ≥ 0forall (u,v)∈E −ya ya In a valid input network, global supplies and demands will sum to zero (so we can reasonably expect that all supplies and demands are finite). Therefore, for the dual to be unbounded, one or more y variables must be unbounded (either positive or negative, depending on the vertex). University of Victoria - CSC 445/545 - Summer 2021 77 Economic Interpretation (19) max. −5yb + 5yc s.t. + yc +zac =5 − yb +zba=2 − yb + yc + zbc = 9 zuv ≥ 0forall (u,v)∈E −ya ya In particular, the dual will be unbounded if yv can be made arbitrarily large at a vertex with demand, or arbitrarily small (negative) at a vertex with extra supply. University of Victoria - CSC 445/545 - Summer 2021 78 Economic Interpretation (20) Question: Under what circumstances could yv become arbitrarily large at a vertex with net demand? University of Victoria - CSC 445/545 - Summer 2021 79 Economic Interpretation (21) If a vertex v has net demand (that is, if supply(v) < 0), then there will be buyers for the resource at that vertex, so it is reasonable that the fair price yv would be positive. Additionally, since we know that there is a global balance of supply and demand, there will always be flow somewhere in the graph that can satisfy the demand at vertex v. Therefore, if yv can be made arbitrarily large, the cost of shipping flow to vertex v to satisfy demand must be infinite (since the fair price will never exceed the cost of shipping flow to the vertex). This can only occur if it is impossible to send enough flow to vertex v to meet demand. University of Victoria - CSC 445/545 - Summer 2021 80 Economic Interpretation (22) -5 c 59 a2 05 For example, consider vertex c above. It is impossible to send any flow to vertex c, so the demand will never be met. Therefore, the fair price of flow at vertex c is infinite (and the dual will be unbounded). b University of Victoria - CSC 445/545 - Summer 2021 81 Economic Interpretation (23) -5 c 59 a2 05 Notice that the “infinite price” interpretation coincides exactly with the condition for primal infeasibility: There is no feasible flow that satisfies demand at vertex c. b University of Victoria - CSC 445/545 - Summer 2021 82 Economic Interpretation (24) -5 c 59 a2 05 Similarly, the fair price of flow at vertex b will be negative infinity (since it is impossible to send the flow anywhere that it will have any value). b University of Victoria - CSC 445/545 - Summer 2021 83 Economic Interpretation (25) -5 c 59 a2 32 The dual problem is also unbounded for the network above, even though it is possible to satisfy some of the demand at vertex c, since it is still impossible to completely satisfy demand (and therefore, the price will go to infinity once all units have been sent from vertex b). b University of Victoria - CSC 445/545 - Summer 2021 84 Economic Interpretation (26) -5 c -5 2 a1 32 Finally, in the network above, a unit of flow can be shipped around the cycle indefinitely for infinite profit (without selling it). Therefore, if the goal is to make the largest profit, it is not rational to define a selling price at all (since selling at any finite price would be less profitable than holding forever). b University of Victoria - CSC 445/545 - Summer 2021 85 Economic Interpretation (27) -5 c -5 2 a1 32 As a result, this case is dual infeasible (since no set of fair prices can exist at all). We know already that this case corresponds to an unbounded primal objective value, so by weak duality it follows that the dual problem is infeasible. b University of Victoria - CSC 445/545 - Summer 2021 86 Unboundedness in the Dual (1) In general, unboundedness in the dual will occur whenever it becomes impossible to fully satisfy demand at some vertex (which will drive the cost of flow at that vertex to infinity). Notice that this description exactly matches the interpretation of primal infeasibility (which is one more symptom of the underlying duality). University of Victoria - CSC 445/545 - Summer 2021 87 Unboundedness in the Dual (2) During the Dual Network Simplex Method, if, after choosing a leaving arc, there are no choices for an entering arc (that is, if all edges between C0 and C1 bridge those components in the same direction as the leaving arc), then the problem is unbounded. Semantically, this is because the leaving arc (u,v) is chosen to be primal infeasible (that is, to carry flow in the wrong direction between components), and the absence of a candidate entering arc implies that there is no way to carry flow in the correct direction. University of Victoria - CSC 445/545 - Summer 2021 88 Unboundedness in the Dual (3) The graph above is identical to one of the usual examples, except that the arc (f,e) has been replaced with (e, f ). University of Victoria - CSC 445/545 - Summer 2021 89 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f 3 i -10 h -4 17 11 -5 3 e6 2d 1 -2 -6 1 c 6 7 a9b 08 Unboundedness in the Dual (4) Task: Starting from the dual feasible basis above, attempt to find an optimal flow. University of Victoria - CSC 445/545 - Summer 2021 90 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f 3 i -10 h -4 17 11 -5 3 e6 2d 1 -2 -6 1 c 6 7 a9b 08 Unboundedness in the Dual (5) Iteration 1. Leaving arc is (h,g). University of Victoria - CSC 445/545 - Summer 2021 91 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f 3 i -10 h -4 17 11 -5 3 e6 2d 1 -2 -6 1 c 6 7 a9b 08 Unboundedness in the Dual (6) With (h, g ) leaving, the entering arc is (g , f ). The flow assigned to (g , f ) will be 10 units. University of Victoria - CSC 445/545 - Summer 2021 92 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow 1311 7 g f 3 ?hi 17 1 e d 3 c 7 ab 08 Unboundedness in the Dual (7) End of Iteration 1. Total cost is 138. University of Victoria - CSC 445/545 - Summer 2021 93 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -411 7 g f 3 17h 6 i 10 11 5 8 e6 -6 1 c 6 -8 d 1 3 7 a9b 08 Unboundedness in the Dual (8) Iteration 2. Leaving arc is (e, f ). University of Victoria - CSC 445/545 - Summer 2021 94 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -411 7 g f 3 17h 6 i 10 11 5 8 e6 -6 1 c 6 -8 d 1 3 7 a9b 08 Unboundedness in the Dual (9) With (e, f ) leaving, the entering arc is (f , i). The flow assigned to (f , i) will be 8 units. University of Victoria - CSC 445/545 - Summer 2021 95 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -411 7 g f 3 17h i 11 ?d 1 e ab 08 3 c 7 Unboundedness in the Dual (10) End of Iteration 2. Total cost is 226. University of Victoria - CSC 445/545 - Summer 2021 96 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -1511 7 g f -8 28h 6 i 10 8 -3 0 e6 -6 1 c 6 11 d 1 3 7 a9b 08 Unboundedness in the Dual (11) Iteration 3. Leaving arc is (a, e). University of Victoria - CSC 445/545 - Summer 2021 97 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -1511 7 g f -8 28h 6 i 10 8 -3 0 e6 -6 1 c 6 11 d 1 3 7 a9b 08 Unboundedness in the Dual (12) With (a, e) leaving, the entering arc is (b, a). The flow assigned to (b, a) will be 6 units. University of Victoria - CSC 445/545 - Summer 2021 98 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -1511 7 g f -8 hi 1 e d 3 ?c 7 a9b 08 Unboundedness in the Dual (13) End of Iteration 3. Total cost is 280. University of Victoria - CSC 445/545 - Summer 2021 99 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -242 -2 g f -17 28h 6 i 10 8 -3 6 e 12 91c 11 d -8 -6 12 a6b 0 -1 -2 Unboundedness in the Dual (14) Iteration 4. Leaving arc is (d,i). University of Victoria - CSC 445/545 - Summer 2021 100 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -242 -2 g f -17 28h 6 i 10 8 -3 6 e 12 91c 11 d -8 -6 12 a6b 0 -1 -2 Unboundedness in the Dual (15) Unbounded. No candidates for entering arc exist, so the price of sending flow from vertex i to vertex d is infinite. University of Victoria - CSC 445/545 - Summer 2021 101 Supply/Cost 10-6 1 g f -2 2h4i 7 15 4 2 e4 18c 2d 6 3 1 a1b -6 -6 0 Flow -242 -2 g f -17 hi ? -6 11 d -8 e ab 0 -1 c -2 Two Phase Methods (1) -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Task: Given a graph with supply and cost values, solve the minimum cost network flow problem. University of Victoria - CSC 445/545 - Summer 2021 102 Two Phase Methods (2) -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 To solve an arbitrary instance of the minimum cost network flow problem, we will need to find either a primal or dual feasible basis (or show that none exists), then use the Primal or Dual Network Simplex Method to find an optimal flow. University of Victoria - CSC 445/545 - Summer 2021 103 Two Phase Methods (3) -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 First Issue: Given only the input network, we need to find any basis (even an infeasible one) before proceeding. University of Victoria - CSC 445/545 - Summer 2021 104 Two Phase Methods (4) Using a graph traversal algorithm like depth-first search or breadth-first search (and treating the graph as undirected) will yield an arbitrary spanning tree. University of Victoria - CSC 445/545 - Summer 2021 105 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Two Phase Methods (5) Of course, an arbitrary spanning tree may be neither primal nor dual feasible, but we can use it as the starting point to find a primal or dual feasible basis. University of Victoria - CSC 445/545 - Summer 2021 106 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Two Phase Methods (6) This situation is analogous to the initialization phase of the normal Simplex Method (which requires an auxiliary problem or a two-phase primal-dual method to find a feasible basis). University of Victoria - CSC 445/545 - Summer 2021 107 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Two Phase Methods (7) We could derive a network form of the auxiliary problem for initialization, but since we already have all of the machinery for duality on hand, it is more convenient to use a two phase method. University of Victoria - CSC 445/545 - Summer 2021 108 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Two Phase Methods (8) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 Recall that a ‘two phase’ solution method for ordinary LPs first solves a modified version of the LP (which is guaranteed to be primal or dual feasible) to find a feasible solution, then uses that feasible solution to solve the original LP. University of Victoria - CSC 445/545 - Summer 2021 109 Modified LP (Dual Feasible) max. 0x1 + 0x2 s.t. −x1 − 2x2 −x1 +2x2 2x1 −3x2 x1 + x2 x1,x2 ≤ −5 ≤10 ≤10 ≤ 13 ≥ 0 Two Phase Methods (9) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 For example, for the LP above on the left (whose initial dictionary will be neither primal nor dual feasible), we can construct the modified LP on the right, which will always be initially dual feasible. Any optimal solution for the modified LP will be both primal and dual feasible (for the modified LP), and therefore will be primal feasible for the original LP. University of Victoria - CSC 445/545 - Summer 2021 110 Modified LP (Dual Feasible) max. 0x1 + 0x2 s.t. −x1 − 2x2 −x1 +2x2 2x1 −3x2 x1 + x2 x1,x2 ≤ −5 ≤10 ≤10 ≤ 13 ≥ 0 Two Phase Methods (10) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 We can therefore solve the original LP by applying the Dual Simplex Method to the modified LP to find a primally feasible solution to the original LP, then using the Primal Simplex Method on the original LP (starting from the optimal solution of the modified LP) to find the solution. University of Victoria - CSC 445/545 - Summer 2021 111 Modified LP (Dual Feasible) max. 0x1 + 0x2 s.t. −x1 − 2x2 −x1 +2x2 2x1 −3x2 x1 + x2 x1,x2 ≤ −5 ≤10 ≤10 ≤ 13 ≥ 0 Two Phase Methods (11) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 (If the modified LP is found to be dual-unbounded, then no primally feasible solution exists for the original LP) University of Victoria - CSC 445/545 - Summer 2021 112 Modified LP (Dual Feasible) max. 0x1 + 0x2 s.t. −x1 − 2x2 −x1 +2x2 2x1 −3x2 x1 + x2 x1,x2 ≤ −5 ≤10 ≤10 ≤ 13 ≥ 0 Two Phase Methods (12) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 We could also construct a primal-feasible modified LP (by setting the right hand side of each constraint to be zero), then solve that with the Primal Simplex Method to find a solution which is dual feasible for the original LP, then solve the original LP starting from that solution using the Dual Simplex Method. University of Victoria - CSC 445/545 - Summer 2021 113 Modified LP (Primal Feasible) max. 3x1 + 4x2 s.t. −x1 −2x2 −x1 +2x2 2x1 −3x2 x1 + x2 ≤0 ≤0 ≤0 ≤ 0 x1,x2 ≥ 0 Two Phase Methods (13) Original LP max. 3x1 + 4x2 s.t. −x1 − 2x2 ≤ −5 −x1 +2x2 ≤10 2x1 −3x2 ≤10 x1 + x2 ≤ 13 x1,x2 ≥ 0 (In general, a two phase method is one in which the primal and dual methods are applied in succession, although there is no general advantage to either ordering of methods) University of Victoria - CSC 445/545 - Summer 2021 114 Modified LP (Primal Feasible) max. 3x1 + 4x2 s.t. −x1 −2x2 −x1 +2x2 2x1 −3x2 x1 + x2 ≤0 ≤0 ≤0 ≤ 0 x1,x2 ≥ 0 Two Phase Methods (14) We can apply the same logic to derive a two phase method for network problems. University of Victoria - CSC 445/545 - Summer 2021 115 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Two Phase Methods (15) A basis is primal feasible if no arcs have negative flow, or, equivalently, if the flow across each edge respects the direction of the edge. Flow on a basic edge is allowed to be zero. Therefore, in a network where supply(v) = 0 for all vertices v ∈ V , any balanced flow will have every xuv = 0, which is always feasible. Therefore, any valid basis will always be feasible in such a graph. University of Victoria - CSC 445/545 - Summer 2021 116 Two Phase Methods (16) A basis is dual feasible if no arcs have a negative dual slack value, or, equivalently, if there is no non-basic arc that would result in a lower cost basis. Dual optimization variables and dual slack values are determined by edge costs (or more specifically, by differentials in edge costs). In a network where cost(e) = 0 for all edges e, wewillhaveyv =0forallv∈V and,consequentlyzuv =0foreveryedge(u,v)∈E. Therefore, in such a network, every valid basis will be dual feasible. University of Victoria - CSC 445/545 - Summer 2021 117 Two Phase Methods (17) Two Phase Method (Dual First): Given a graph G with supply and cost values, 1. Construct a graph G′ consisting of a copy of G with all edge costs set to zero. 2. Compute an arbitrary spanning tree of G′. This basis will always be dual feasible (since all costs are zero, so all dual slack values will be zero). 3. Apply the Dual Network Simplex Method to compute an optimal flow for G′. If unboundedness is detected, the original problem instance G is infeasible. 4. If unboundedness is not detected, the optimal basis B′ will be both primal and dual feasible for G′. Since the vertex supply values in G′ match those of G, B′ will also be primal feasible for G (although probably not dual feasible for G). 5. Apply the Primal Network Simplex Method on G, starting from the primal feasible basis B′, to find the optimal flow. University of Victoria - CSC 445/545 - Summer 2021 118 Two Phase Methods (18) Two Phase Method (Primal First): Given a graph G with supply and cost values, 1. Construct a graph G′ consisting of a copy of G with all vertex supply values set to zero. 2. Compute an arbitrary spanning tree of G′. This basis will always be primal feasible (since all supplies are zero, so all primal flow values will be zero). 3. Apply the Primal Network Simplex Method to compute an optimal flow for G′. If unboundedness is detected, the original problem instance G is unbounded or infeasible. 4. If unboundedness is not detected, the optimal basis B′ will be both primal and dual feasible for G′. Since the edge cost values in G′ match those of G, B′ will also be dual feasible for G (although probably not primal feasible for G). 5. Apply the Dual Network Simplex Method on G, starting from the dual feasible basis B′, to find the optimal flow. University of Victoria - CSC 445/545 - Summer 2021 119 Dual-First Two Phase Method (1) Task: Starting from the infeasible basis above, use a two phase method (dual first, primal second) to solve the network flow problem. University of Victoria - CSC 445/545 - Summer 2021 120 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Dual-First Two Phase Method (2) Phase One: All edge costs are temporarily set to zero (shown in orange on the left, to indicate that they are phony). This makes any basis dual feasible, so we can use the Dual Network Simplex Method to find an optimal flow for the modified graph. University of Victoria - CSC 445/545 - Summer 2021 121 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e4f0 0 1400 0 a -4 b 1 c -4 d 0000 Dual-First Two Phase Method (3) Iteration 1. Leaving arc is (b, a). University of Victoria - CSC 445/545 - Summer 2021 122 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e4f0 0 1400 0 a -4 b 1 c -4 d 0000 Dual-First Two Phase Method (4) With (b, a) leaving, the entering arc is (e, c). The flow assigned to (e, c) will be 4 units. University of Victoria - CSC 445/545 - Summer 2021 123 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 ghij 0ef00 000 a?bcd 0000 Dual-First Two Phase Method (5) End of Iteration 1. Total cost is 0. University of Victoria - CSC 445/545 - Summer 2021 124 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e4f0 0 1004 0 a 0 b 5 c -4 d 0000 Dual-First Two Phase Method (6) Iteration 2. Leaving arc is (c,d). University of Victoria - CSC 445/545 - Summer 2021 125 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e4f0 0 1004 0 a 0 b 5 c -4 d 0000 Dual-First Two Phase Method (7) With (c, d) leaving, the entering arc is (d, f ). The flow assigned to (d, f ) will be 4 units. University of Victoria - CSC 445/545 - Summer 2021 126 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 ghij 0ef00 0 abc?d 0000 Dual-First Two Phase Method (8) Optimal. Total cost is 0. University of Victoria - CSC 445/545 - Summer 2021 127 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e8f0 0 1008 4 a0b5c0d 0000 Dual-First Two Phase Method (9) The optimal basis for the modified graph will be both primal and dual feasible. Since the vertex supply values for the modified graph match those of the original graph, this basis will be primal feasible for the original graph. University of Victoria - CSC 445/545 - Summer 2021 128 Supply/Cost -2 -4 -1 1 g0h0i0j 000 0 10e 0 f3 0 000 0 a0b0c0d -3 -5 -3 4 Flow 0000 g5h1i0j 001 7 0e8f0 0 1008 4 a0b5c0d 0000 Dual-First Two Phase Method (10) Phase Two: Starting from the feasible basis produced by Phase One, we can now run the Primal Network Simplex Method. University of Victoria - CSC 445/545 - Summer 2021 129 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 8 f-17 5 10238 4 a 11 b 5 c 31 d 0 1 -1 -22 Dual-First Two Phase Method (11) Iteration 1. Entering arc is (f , i ). University of Victoria - CSC 445/545 - Summer 2021 130 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 8 f-17 5 10238 4 a 11 b 5 c 31 d 0 1 -1 -22 Dual-First Two Phase Method (12) With (f , i) entering, the leaving arc is (h, i). The flow assigned to (f , i) will be 1 units. University of Victoria - CSC 445/545 - Summer 2021 131 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g5h1i j ? 7 -12e 8 f-17 10 abcd 0 1 -1 -22 Dual-First Two Phase Method (13) Optimal. Total cost is 302. University of Victoria - CSC 445/545 - Summer 2021 132 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 7 f-17 5 9238 4 a 11 b 5 c 31 d 0 1 -1 -22 Primal-First Two Phase Method (1) Task: Starting from the infeasible basis above, use a two phase method (primal first, dual second) to solve the network flow problem. University of Victoria - CSC 445/545 - Summer 2021 133 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 9 -18 g 5 h 1 i 29 j 25 -24 1 7 -12e 4 f-17 25 14 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Primal-First Two Phase Method (2) Phase One: All vertex supply values are temporarily set to zero (shown in orange on the left, to indicate that they are phony). This makes any basis primal feasible, so we can use the Primal Network Simplex Method to find an optimal flow for the modified graph. University of Victoria - CSC 445/545 - Summer 2021 134 Supply/Cost 0000 g2h2i2j 121 5 0e5f0 9 12 10 11 5 a 10 b 2 c 10 d 0000 Flow 5 7 9 -18 g 0 h 0 i 29 j 25 -24 0 0 -12e 0 f-17 25 0 12 11 20 a0b0c0d 0 -10 -12 -2 Primal-First Two Phase Method (3) Iteration 1. Entering arc is (f , i ). University of Victoria - CSC 445/545 - Summer 2021 135 Supply/Cost 0000 g2h2i2j 121 5 0e5f0 9 12 10 11 5 a 10 b 2 c 10 d 0000 Flow 5 7 9 -18 g 0 h 0 i 29 j 25 -24 0 0 -12e 0 f-17 25 0 12 11 20 a0b0c0d 0 -10 -12 -2 Primal-First Two Phase Method (4) With (f,i) entering, the leaving arc is (a,g). The flow assigned to (f,i) will be 0 units. University of Victoria - CSC 445/545 - Summer 2021 136 Supply/Cost 0000 g2h2i2j 121 5 0e5f0 9 12 10 11 5 a 10 b 2 c 10 d 0000 Flow 5 7 9 -18 g0h0i j ? 0 -12e 0 f-17 0 abcd 0 -10 -12 -2 Primal-First Two Phase Method (5) Optimal. Total cost is 0. University of Victoria - CSC 445/545 - Summer 2021 137 Supply/Cost 0000 g2h2i2j 121 5 0e5f0 9 12 10 11 5 a 10 b 2 c 10 d 0000 Flow -19 -17 -15 -18 g0h0i5j 100 24 -12 e 0 f -17 25 0 12 11 20 a0b0c0d 0 -10 -12 -2 Primal-First Two Phase Method (6) The optimal basis for the modified graph will be both primal and dual feasible. Since the edge costs for the modified graph match those of the original graph, this basis will be dual feasible for the original graph. University of Victoria - CSC 445/545 - Summer 2021 138 Supply/Cost 0000 g2h2i2j 121 5 0e5f0 9 12 10 11 5 a 10 b 2 c 10 d 0000 Flow -19 -17 -15 -18 g0h0i5j 100 24 -12 e 0 f -17 25 0 12 11 20 a0b0c0d 0 -10 -12 -2 Primal-First Two Phase Method (7) Phase Two: Starting from the feasible basis produced by Phase One, we can now run the Dual Network Simplex Method. University of Victoria - CSC 445/545 - Summer 2021 139 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow -19 -17 -15 -18 g -2 h -6 i 5 j 171 24 -12 e -3 f -17 25 7 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Primal-First Two Phase Method (8) Iteration 1. Leaving arc is (h,i). University of Victoria - CSC 445/545 - Summer 2021 140 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow -19 -17 -15 -18 g -2 h -6 i 5 j 171 24 -12 e -3 f -17 25 7 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Primal-First Two Phase Method (9) With (h,i) leaving, the entering arc is (a,g). The flow assigned to (a,g) will be 6 units. University of Victoria - CSC 445/545 - Summer 2021 141 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 -19 -17 -15 -18 Flow gh?ij 1 24 -12 e f -17 abcd 0 -10 -12 -2 Primal-First Two Phase Method (10) End of Iteration 1. Total cost is 134. University of Victoria - CSC 445/545 - Summer 2021 142 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 3 f-17 25 13 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Primal-First Two Phase Method (11) Iteration 2. Leaving arc is (b, a). University of Victoria - CSC 445/545 - Summer 2021 143 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 3 f-17 25 13 12 11 20 a -4 b 1 c -4 d 0 -10 -12 -2 Primal-First Two Phase Method (12) With (b, a) leaving, the entering arc is (e, c). The flow assigned to (e, c) will be 4 units. University of Victoria - CSC 445/545 - Summer 2021 144 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 ghij -12 e f -17 25 1211 20 a?bcd 0 -10 -12 -2 Primal-First Two Phase Method (13) End of Iteration 2. Total cost is 178. University of Victoria - CSC 445/545 - Summer 2021 145 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 3 f-17 36 9234 31 a 11 b 5 c -4 d 0 1 -1 9 Primal-First Two Phase Method (14) Iteration 3. Leaving arc is (c,d). University of Victoria - CSC 445/545 - Summer 2021 146 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 3 f-17 36 9234 31 a 11 b 5 c -4 d 0 1 -1 9 Primal-First Two Phase Method (15) With (c, d) leaving, the entering arc is (d, f ). The flow assigned to (d, f ) will be 4 units. University of Victoria - CSC 445/545 - Summer 2021 147 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 ghij -12 e f -17 36 31 abc?d 0 1 -1 9 Primal-First Two Phase Method (16) Optimal. Total cost is 302. University of Victoria - CSC 445/545 - Summer 2021 148 Supply/Cost -2 -4 -1 1 g2h2i2j 121 5 10e 5 f3 9 12 10 11 5 a 10 b 2 c 10 d -3 -5 -3 4 Flow 5 7 -15 -18 g 4 h 24 i 5 j 25 1 1 6 -12e 7 f-17 5 9238 4 a 11 b 5 c 31 d 0 1 -1 -22