CSC 445/545 – Summer 2021 – Network Simplex Examples II
CSC 445/545 – Summer 2021
Network Simplex Examples II
Bill Bird
Department of Computer Science
University of Victoria
July 11, 2021
University of Victoria – CSC 445/545 – Summer 2021 1
Examples
This lecture contains examples of exercises of the form ‘solve this minimum cost network
flow problem’. The term ‘solve’ means to determine if the problem is infeasible, unbounded
or has an optimal flow, and to find the optimal flow if one exists. Therefore, determining
that a problem instance is infeasible or unbounded is considered ‘solving’ that problem.
All of the examples in this lecture involve starting from a dual-feasible basis and using dual
pivoting to find an optimal flow.
The examples here all use the network equivalent of the largest coefficient rule to select the
leaving arc at each step. Specifically, the leaving arc is chosen to be the primal-infeasible
arc with the smallest negative primal flow value.
University of Victoria – CSC 445/545 – Summer 2021 2
Example 1 (1)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
-3
e
-1
f-1
g
-8
h
-6
i
-2
4
-1
3
9
3
6
4 1
10
9
5
0
5
Task: Starting from the dual feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 3
Example 1 (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
-3
e
-1
f-1
g
-8
h
-6
i
-2
4
3
9
3
6
4 1
10
9
5
0
5
-1
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 4
Example 1 (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
2
d
-3
e
-1
f-1
g
-8
h
-6
i
-2
9
?
With (b, c) leaving, the entering arc is (c, d). The flow assigned to (c , d) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 5
Example 1 (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
1
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
-8
h
-6
i
-2
5
1
4
10
3
6
4 1
9
10
5
0
5
Optimal. Total cost is 71.
University of Victoria – CSC 445/545 – Summer 2021 6
Example 2 (1)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
2
d
-3
e
-1
f-1
g
3
h
5
i
9
4
-1
3
9
3
10 4
5
10
9
5
11
16
Task: Starting from the dual feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 7
Example 2 (2)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
2
d
-3
e
-1
f-1
g
3
h
5
i
9
4
3
9
3
10 4
5
10
9
5
11
16
-1
Iteration 1. Leaving arc is (b, c).
University of Victoria – CSC 445/545 – Summer 2021 8
Example 2 (3)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
2
d
-3
e
-1
f-1
g
3
h
5
i
9
9
?
With (b, c) leaving, the entering arc is (c , d). The flow assigned to (c , d) will be 1 units.
University of Victoria – CSC 445/545 – Summer 2021 9
Example 2 (4)
Supply/Cost Flow
a
-6
b
-5
c
1
d
3
e
6
f-2
g
10
h
-6
i
1
1
1
8
4
2
1
5
1
2
7
4
4
-10
a
0
b
1
c
-7
d
-3
e
-1
f-1
g
3
h
5
i
9
5
1
4
10
3
10 4
5
9
10
5
11
16
Optimal. Total cost is 16.
University of Victoria – CSC 445/545 – Summer 2021 10
Example 3 (1)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
2
-5 -3
110
5
0 -4
1
12
4
5
7
24
1
5
Task: Starting from the dual feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 11
Example 3 (2)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
2
-3
110
5
0 -4
1
12
4
5
7
24
1
5
-5
Iteration 1. Leaving arc is (b, a).
University of Victoria – CSC 445/545 – Summer 2021 12
Example 3 (3)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-10
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
12
4?
With (b, a) leaving, the entering arc is (c , b). The flow assigned to (c , b) will be 5 units.
University of Victoria – CSC 445/545 – Summer 2021 13
Example 3 (4)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-6
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
7
5 -8
-410
0
5 1
1
4
16
5
7
24
1
5
End of Iteration 1. Total cost is 78.
University of Victoria – CSC 445/545 – Summer 2021 14
Example 3 (5)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-6
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
7
5
-410
0
5 1
1
4
16
5
7
24
1
5
-8
Iteration 2. Leaving arc is (c , d).
University of Victoria – CSC 445/545 – Summer 2021 15
Example 3 (6)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
-6
c
-8
d
2
e-12 f 7
g
5
h
7
i
9
j
6
4
16 7
?
With (c , d) leaving, the entering arc is (e, c). The flow assigned to (e, c) will be 8 units.
University of Victoria – CSC 445/545 – Summer 2021 16
Example 3 (7)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
2
e-12 f 7
g
5
h
7
i
9
j
6
-1
5
42 8
8
-3 -7
1
11
23
7
524
1
5
End of Iteration 2. Total cost is 134.
University of Victoria – CSC 445/545 – Summer 2021 17
Example 3 (8)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
2
e-12 f 7
g
5
h
7
i
9
j
6
-1
5
42 8
8
-3
1
11
23
7
524
1
5-7
Iteration 3. Leaving arc is (h, i).
University of Victoria – CSC 445/545 – Summer 2021 18
Example 3 (9)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
2
e-12 f 7
g
5
h
7
i
9
j
6
7
1
24
?
With (h, i) leaving, the entering arc is (f , e). The flow assigned to (f , e) will be 7 units.
University of Victoria – CSC 445/545 – Summer 2021 19
Example 3 (10)
Supply/Cost Flow
a
-3
b
-5
c
-3
d
4
e10 f 3
g
-2
h
-4
i
-1
j
1
5
10
10
2 10
9
512 11
2
5
2
1
2 2
1
a
0
b
1
c
-1
d
-22
e-12 f -17
g
5
h
7
i
-15
j
-18
6
5
49 8
1
7
4
1
11
23
31
5
25
24 5
Optimal. Total cost is 302.
University of Victoria – CSC 445/545 – Summer 2021 20
Example 4 (1)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-45
e
-30
f
-55
g
-40
6 6
-8
2
9 5
73
40
10
30
1
5
9
9
(This is the motivating example from Chapter 14 of Vanderbei)
University of Victoria – CSC 445/545 – Summer 2021 21
Example 4 (2)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-45
e
-30
f
-55
g
-40
6 6
-8
2
9 5
73
40
10
30
1
5
9
9
Task: Starting from the dual feasible basis above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 22
Example 4 (3)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-45
e
-30
f
-55
g
-40
6 6
2
9 5
73
40
10
30
1
5
9
9-8
Iteration 1. Leaving arc is (d , b).
University of Victoria – CSC 445/545 – Summer 2021 23
Example 4 (4)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-45
e
-30
f
-55
g
-40
73
40
30
9?
With (d , b) leaving, the entering arc is (g , e). The flow assigned to (g , e) will be 8 units.
University of Victoria – CSC 445/545 – Summer 2021 24
Example 4 (5)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-36
e
-21
f
-55
g
-40
6 6
-6
9 -3
8
64
31
10
21
91
5
9
End of Iteration 1. Total cost is 725.
University of Victoria – CSC 445/545 – Summer 2021 25
Example 4 (6)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-36
e
-21
f
-55
g
-40
6 6
9 -3
8
64
31
10
21
91
5
9
-6
Iteration 2. Leaving arc is (d , e).
University of Victoria – CSC 445/545 – Summer 2021 26
Example 4 (7)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
-36
e
-21
f
-55
g
-40
9
64 ?
With (d , e) leaving, the entering arc is (a, d). The flow assigned to (a, d) will be 6 units.
University of Victoria – CSC 445/545 – Summer 2021 27
Example 4 (8)
Supply/Cost Flow
a
0
b
0
c-6
d
-6
e
-2
f
9
g
5
48
28
10
7
65
7
38
15
56
48108
24
33
19
a
0
b
-7
c48
d
28
e
-21
f
-55
g
-40
6
6
12
9 3
2
31
10
21
73
64
1
5
9
Optimal. Total cost is 1109.
University of Victoria – CSC 445/545 – Summer 2021 28