CSC 445/545 – Summer 2021
The Network Simplex Method: Primal Pivoting
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
July 10, 2021
The Story So Far (1)
In the previous lecture, we saw how to model the complete state of the Simplex Method on a minimum-cost network flow problem using graphs.
University of Victoria – CSC 445/545 – Summer 2021 2
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
The Story So Far (2)
The basis (thick red edges) is a set of |V | − 1 edges comprising a spanning tree (of the underlying undirected graph).
University of Victoria – CSC 445/545 – Summer 2021 3
Supply/Cost
g
f
Flow
hi
d
e
c
ab
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
The Story So Far (3)
One vertex (always vertex a in these examples) is selected to be the root of the spanning tree (and is given special treatment in some parts of the algorithm).
University of Victoria – CSC 445/545 – Summer 2021 4
Supply/Cost
g
f
Flow
hi
d
e
c
ab
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
The Story So Far (4)
Each basic edge (u, v ) has an associated primal flow value xuv . (There is a variable xuv for every edge, but it will be zero for non-basic edges).
University of Victoria – CSC 445/545 – Summer 2021 5
Supply/Cost
Flow
g
f
h6i 10 5
3d -3
e
-12
a -6 b
c
0
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
The Story So Far (5)
Each vertex v ∈ V has an associated dual variable yv. The value ya associated with the root is defined to be zero. For all other variables, yv is the cost of moving one unit of flow from the root to vertex v using only basic edges.
University of Victoria – CSC 445/545 – Summer 2021 6
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
The Story So Far (6)
We interpret the cost of moving a unit of flow in the wrong direction along an edge (u,v) to be −cost((u,v)).
University of Victoria – CSC 445/545 – Summer 2021 7
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
The Story So Far (7)
Each non-basic edge (u, v ) has an associated dual slack variable zuv . The value of zuv indicates the potential cost increase associated with adding (u,v) to the basis.
University of Victoria – CSC 445/545 – Summer 2021
8
Supply/Cost
Flow
g
f
28h i
-7
d e9
10 c ab
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
The Story So Far (8)
A flow is primal feasible if all primal flow variables xuv are non-negative, or, equivalently, if the direction of each edge is respected (and flow is not moved across any edge in the wrong direction).
University of Victoria – CSC 445/545 – Summer 2021 9
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
The Story So Far (9)
A flow is dual feasible if all dual slack variables zuv are non-negative, or, equivalently, if there is no non-basic edge (u,v) that would reduce the cost of transportation if added to the basis.
University of Victoria – CSC 445/545 – Summer 2021 10
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
The Story So Far (10)
A flow is optimal if it is both primal and dual feasible. Note that the dual optimization variables yv are not required to be non-negative for the flow to be optimal.
University of Victoria – CSC 445/545 – Summer 2021 11
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
The Story So Far (11)
The flow above is neither primal nor dual feasible.
University of Victoria – CSC 445/545 – Summer 2021 12
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
The Story So Far (12)
To make infeasibilities more obvious, we will typeset infeasible primal flow or dual slack values in blue (see above).
University of Victoria – CSC 445/545 – Summer 2021 13
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
0
3d
1
-3
-2
a -6 b 0 -1
What is a Primal Pivot? (1)
The flow above is feasible, but not optimal (notice that there are non-basic edges which are not dual feasible).
University of Victoria – CSC 445/545 – Summer 2021 14
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
What is a Primal Pivot? (2)
Our goal is to find a way to model the (primal) pivoting operation using the graph.
University of Victoria – CSC 445/545 – Summer 2021 15
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
What is a Primal Pivot? (3)
Question: What can we deduce about the required logic?
University of Victoria – CSC 445/545 – Summer 2021 16
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
What is a Primal Pivot? (4)
By applying what we already know about the Simplex Method (and the graph-theoretic interpretation), we know the following.
The basis is a collection of edges, so any pivoting operation will involve an ‘entering edge’ and a ‘leaving edge’.
The entering variable in a primal pivot is chosen to be a dual-infeasible variable. In graph-theoretic terms this implies that our entering edge will be an arc with a negative dual slack value.
The basis must be a spanning tree, but adding a new edge will create a cycle. Therefore, the leaving edge must be part of the same cycle (so that the resulting new basis is a tree again).
The new basis must be feasible, so the leaving arc must be chosen to preserve feasibility.
University of Victoria – CSC 445/545 – Summer 2021 17
What is a Primal Pivot? (5)
We could choose either arc (e,d) or (d,i) as the entering arc in the example above (and, as you might have guessed, the particular choice would devolve on a pivot selection rule).
University of Victoria – CSC 445/545 – Summer 2021 18
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
What is a Primal Pivot? (6)
Suppose we choose arc (e,d) to enter the basis.
University of Victoria – CSC 445/545 – Summer 2021 19
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
3d
-9
e3
10 9 c
3 a6b
0 -1
-2
What is a Primal Pivot? (7)
Adding (e,d) to the basis creates a cycle on vertices b,c,d and e. The leaving arc must therefore be one of (c, b), (d, c) or (e, b).
University of Victoria – CSC 445/545 – Summer 2021 20
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
3d
-9
e3
10 9 c
3 a6b
0 -1
-2
Resolving Cycles (1)
v6
v3
v1
v2
v5
v4
Suppose the edge (v6, v1) (in blue) is the entering edge, creating the cycle v1, v2, v3, v4, v5, v6.
University of Victoria – CSC 445/545 – Summer 2021 21
Resolving Cycles (2)
v1 f1 v2
? f2
v6
f5
v3 f3
v5 f4 v4
Each other edge will have some existing non-negative flow value.
University of Victoria – CSC 445/545 – Summer 2021
22
Resolving Cycles (3)
v1 f1 v2
? f2
v6
f5
v3 f3
v5 f4 v4
Before considering the effect of adding flow on the entering edge, we should differentiate between the edges that point in the ‘same direction’ as the entering edge with respect to the cycle (light blue) and those that point in the opposite direction (orange).
University of Victoria – CSC 445/545 – Summer 2021 23
Resolving Cycles (4)
v1 f1 v2
t f2
v6
f5
v3 f3
v5 f4 v4
Consider the effect of adding flow along the entering edge (v6,v1): We can model this by setting the flow value along that edge to some non-negative value t.
University of Victoria – CSC 445/545 – Summer 2021 24
Resolving Cycles (5)
v1 f1 v2
t f2
v6
f5
v3 f3
v5 f4 v4
As per the usual expectations for primal pivots, we must ensure that any increase t to the entering edge maintain feasibility (which implies maintaining flow balance as well).
University of Victoria – CSC 445/545 – Summer 2021 25
Resolving Cycles (6)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
Therefore, if t units of flow are added along (v6,v1), the other edges in the cycle must be adjusted to maintain balance.
University of Victoria – CSC 445/545 – Summer 2021 26
Resolving Cycles (7)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
For example, consider v1: If t units of flow are now arriving along (v6, v1), they must be sent out along (v1,v2) to maintain the pre-existing balance of supply at v1.
University of Victoria – CSC 445/545 – Summer 2021 27
Resolving Cycles (8)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
On the other hand, to maintain balance at v2 (which now has t units arriving from v1), we have no choice but to send flow backwards along (v3,v2) to maintain balance.
University of Victoria – CSC 445/545 – Summer 2021 28
Resolving Cycles (9)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
Note that “sending flow backwards” along edges is not inherently problematic, since we can subtract the “backwards” flow from the flow along the edge to produce the same effect (as long as the underlying non-negativity constraints continue to be satisfied).
University of Victoria – CSC 445/545 – Summer 2021 29
Resolving Cycles (10)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
In particular, since we require that every edge has a non-negative flow value, we must ensure that f2 − t ≥ 0 and f4 − t ≥ 0.
University of Victoria – CSC 445/545 – Summer 2021 30
Resolving Cycles (11)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
Therefore, the maximum amount of flow t that we can add to the entering edge (v6,v1) is the smaller of f2 and f4.
University of Victoria – CSC 445/545 – Summer 2021 31
Resolving Cycles (12)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
Notice that none of the flow amounts along the (blue) edges in the same direction as the entering edge place any constraints on t.
University of Victoria – CSC 445/545 – Summer 2021 32
Resolving Cycles (13)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 − t
v3
f3 + t
f4 − t
v4
We now have enough information to deduce the procedure for a primal pivot in the Network Simplex Method.
University of Victoria – CSC 445/545 – Summer 2021 33
Primal Pivoting (1)
Primal Pivoting: Choose a dual infeasible non-basic arc e (using some pivot selection rule) as the entering arc. Then,
Find the cycle created by adding e to the basis.
Locate all edges within the cycle whose directions are ‘opposite’ to e.
Choose the leaving arc l to be the opposite-directed edge with the smallest flow value.
Set the flow value for arc e to match that of arc l.
Adjust all other edges in the cycle accordingly. This will result in arc l having zero flow, so it can be removed from the basis.
University of Victoria – CSC 445/545 – Summer 2021 34
Primal Pivoting (2)
v1 5 v2 ?7
v6
v3
6 10 v5 8 v4
To contextualize the steps, we can start with a concrete version of the earlier example. This example might be part of a larger graph (since there’s no requirement that the cycle created by an entering edge involve all vertices in the graph).
University of Victoria – CSC 445/545 – Summer 2021 35
Primal Pivoting (3)
v1 5 v2 ?7
v6
v3
6 10 v5 8 v4
Suppose that (v6,v1) is chosen to enter the basis. Assuming the existing basis was primal feasible, the flow assigned to each arc must be balanced and non-negative.
University of Victoria – CSC 445/545 – Summer 2021 36
Primal Pivoting (4)
v1 5 v2 ?7
v6
v3
6 10 v5 8 v4
(The numerical value of each flow is essentially arbitrary in this context, since it would have been dictated by the balance constraints).
University of Victoria – CSC 445/545 – Summer 2021 37
Primal Pivoting (5)
v6
v3
v1 5 v2 ?8
10 7 v5 6 v4
After adding (v6,v1), the basis contains a cycle, so an edge must be selected to leave.
University of Victoria – CSC 445/545 – Summer 2021 38
Primal Pivoting (6)
v1 5 v2 ?8
v6
v3
10 7 v5 6 v4
The leaving arc must be one of the arcs whose orientation in the cycle is opposite to the entering arc (v6,v1). (On the diagram, opposite-oriented arcs are shown in orange)
University of Victoria – CSC 445/545 – Summer 2021 39
Primal Pivoting (7)
v1 5 v2 ?8
v6
v3
10 7 v5 6 v4
The leaving arc must be one of the arcs whose orientation in the cycle is opposite to the entering arc (v6,v1). (On the diagram, opposite-oriented arcs are shown in orange)
University of Victoria – CSC 445/545 – Summer 2021 40
Primal Pivoting (8)
v1 5+t v2
t 8−t
v6
v3
10+t 7+t v5 6−t v4
If the flow along (v6, v1) is increased to some value t ≥ 0, the flow on the other arcs in the cycle must be adjusted as shown to maintain balance.
University of Victoria – CSC 445/545 – Summer 2021 41
Primal Pivoting (9)
v1 5+t v2
t 8−t
v6
v3
10+t 7+t v5 6−t v4
Therefore, the largest possible value of t is 6 (equal to the smallest flow value of an opposite- oriented edge). This implies that (v5,v4) must be the leaving arc.
University of Victoria – CSC 445/545 – Summer 2021 42
Primal Pivoting (10)
v1 5+t v2
t 8−t
v6
v3
10+t 7+t v5 6−t v4
To perform the pivot, we first set t = 6 and adjust the flow of each arc accordingly.
University of Victoria – CSC 445/545 – Summer 2021 43
Primal Pivoting (11)
v1 11 v2 62
v6
16
v3 13
v5 0 v4
After the adjustment, the leaving edge will have a flow value of 0 and can be removed from the basis.
University of Victoria – CSC 445/545 – Summer 2021 44
Primal Pivoting (12)
v1 11 v2 62
v6
16
v5
v3 13
v4
To complete the pivot, the dual variable and dual slack values must also be updated (which might require working with vertices/edges outside the cycle above).
University of Victoria – CSC 445/545 – Summer 2021 45
Primal Pivoting (13)
v1 11 v2 62
v6
16
v5
v3 13
v4
While it is obviously possible to simply recompute the dual and dual slack variables from scratch using the tree, not every value will have changed (and we can identify exactly which updates are needed).
University of Victoria – CSC 445/545 – Summer 2021 46
Primal Pivoting (14)
Consider the effect of adding (d,i) to the basis in the example above.
University of Victoria – CSC 445/545 – Summer 2021 47
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
3d
-9
e3
10 9 c
-1
-6
3 a6b
0 -1
-2
Primal Pivoting (15)
The resulting cycle is d,i,f,e,b,c, and the leaving arc could be either (c,b) or (d,c). Suppose (c,b) is chosen as the leaving arc.
University of Victoria – CSC 445/545 – Summer 2021 48
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
g
Flow
hi
5
?
f
3d
e3
9c 3
ab
Primal Pivoting (16)
Removing (c,b) from the spanning tree (before adding (d,i)) will separate the tree into exactly two components.
University of Victoria – CSC 445/545 – Summer 2021 49
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
3d
e3 9c
a6b
h6i 10 5
Primal Pivoting (17)
The dual value of vertices in the component containing the root vertex (shaded purple) will not change, since the dual values are computed from the root downward.
University of Victoria – CSC 445/545 – Summer 2021 50
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
3d
e3 9c
a6b
h6i 10 5
Primal Pivoting (18)
Therefore, only those dual values yv for vertices v in the other component (shaded orange) will need to be recomputed after the pivot.
University of Victoria – CSC 445/545 – Summer 2021 51
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
3d
e3 9c
a6b
h6i 10 5
Primal Pivoting (19)
Similarly, since the dual slack variables for non-basic edges are computed using the dual values yv, only those edges incident to the orange vertices (c and d) will need to have their slack values recomputed after the pivot.
University of Victoria – CSC 445/545 – Summer 2021 52
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
3d
e3 9c
a6b
h6i 10 5
Primal Pivoting (20)
To complete the pivot with (d,i) entering and (c,b) leaving, we will first update the primal flow values to set the flow along (d,i) to be 3.
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
g
Flow
hi
5
3
f
3d
e3
9c 3
ab
Primal Pivoting (21)
After rebalancing the flow values within the cycle, the dual and dual slack values can be recomputed.
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
g
f
6d
e0
12 c 0
a6b
h6i 10 2
3
Primal Pivoting (22)
The state of the system after all updates are complete is shown above. Notice that arc (d, c) is degenerate.
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
-188 4
g
f
-11
28h 6 i 10 2
3
0
e0
10 12 c
6
6d
-9
-7
4
a6b 0 -1
Primal Pivoting (23)
The resulting flow is not dual feasible. The next entering arc will be (e,d) and the next leaving arc will be (f,i)
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
-188 4
g
f
-11
28h 6 i 10 2
3
? e0
10 12 c
6
6d
-9
0
4
a6b 0 -1
Primal Pivoting (24)
Removing (f , i) from the spanning tree (before adding (e, d)) will separate the tree into the components above, so dual updates are only needed for vertices c,d,h and i.
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
g
10
Flow
h6i
3
f
6d
e0
12 c
a6b
Primal Pivoting (25)
To complete the pivot with (e, d) entering and (f , i) leaving, we will first update the primal flow values to set the flow along (e,d) to be 2.
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
g
f
Flow
hi
2
3
6d 2
e
c
ab
Primal Pivoting (26)
After rebalancing the flow values within the cycle, the dual and dual slack values can be recomputed.
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
g
f
h6i 10 0
5
8d 2
e0
12 c
a6b
Primal Pivoting (27)
The state of the system after the pivot is shown above.
University of Victoria – CSC 445/545 – Summer 2021 60
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-181 -3
g
f
-11
21h 6 i 10 7
5
2 e0
10 12 c
-1
8d
-9
-7
-3
a6b 0 -1
Primal Pivoting (28)
The flow is still not dual feasible. The next entering arc will be (c,b) and the next leaving arc will be (e, b)
University of Victoria – CSC 445/545 – Summer 2021 61
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
Flow
-181 -3
g
f
-11
21h 6 i 10 7
5
2 e0
10 12 c
8d
-9
-7
? a6b
0 -1
-3
Primal Pivoting (29)
Removing (e,b) from the spanning tree will separate the tree into the components above, so dual updates will be needed for every vertex but a and b.
University of Victoria – CSC 445/545 – Summer 2021 62
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
18c
2d
6
3
1 a1b
-6 -6
0
g
10
f
Flow
h6i
5
8d 2
e0
c
a6b
Primal Pivoting (30)
To complete the pivot with (c,b) entering and (e,b) leaving, we will first update the primal flow values to set the flow along (c,b) to be 12.
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
g
f
Flow
hi
d
2 e0
12 c 12
ab
Primal Pivoting (31)
After rebalancing the flow values within the cycle, the dual and dual slack values can be recomputed.
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
g
10
f
Flow
h6i
5
8d 14
e 12
0c 12
a6b
Primal Pivoting (32)
After the pivot is complete, the flow is both primal and dual feasible (and therefore is optimal). The total cost is 224.
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
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
91c
8d
-8
-6
12 a6b
0 -1
-2
The Primal Network Simplex Method (1)
Task: Starting from the primal feasible flow above, find an optimal flow.
University of Victoria – CSC 445/545 – Summer 2021 66
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 11 16
j -17 i 8 k 2 11 7
6
7 g -6 h 10
13
-14 7 -2 10 5
-11f 20 e -6 d14
12 11 17
b 14 a 1 c -1 0 -1
The Primal Network Simplex Method (2)
Iteration 1. Entering arc is (j,i).
University of Victoria – CSC 445/545 – Summer 2021 67
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 11 16
j -17 i 8 k 2 11 7
6
7 g -6 h 10
13
-14 7 -2 10 5
-11f 20 e -6 d14
12 11 17
b 14 a 1 c -1 0 -1
The Primal Network Simplex Method (3)
With (j, i) entering, the leaving arc is (g, i). The flow assigned to (j, i) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 68
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 11 16
j?i k 2
6
7gh 13
-11 f 12
7
5
e
11
d 14
b14a c -1 0 -1
The Primal Network Simplex Method (4)
End of Iteration 1. Total cost is 232.
University of Victoria – CSC 445/545 – Summer 2021 69
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
j2i8k 17 11 7
6
5 g 11 h 10
-4
-14 5 15 10 5
-11f 20 e 11 d-3 10 9 0
b 12 a 1 c -1 0 -1
The Primal Network Simplex Method (5)
Iteration 2. Entering arc is (f , g ).
University of Victoria – CSC 445/545 – Summer 2021 70
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
j2i8k 17 11 7
6
5 g 11 h 10
-4
-14 5 15 10 5
-11f 20 e 11 d-3 10 9 0
b 12 a 1 c -1 0 -1
The Primal Network Simplex Method (6)
With (f,g) entering, the leaving arc is (e,g). The flow assigned to (f,g) will be 5 units.
University of Victoria – CSC 445/545 – Summer 2021 71
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
jik
6
g
?5
h
-4 5
e
-11 f
10 9
d -3
b12a c -1 0 -1
The Primal Network Simplex Method (7)
End of Iteration 2. Total cost is 162.
University of Victoria – CSC 445/545 – Summer 2021 72
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
j2i8k 3 11 7
-8
5 g -3 h 10
-4
5 14 15 10 5
-11f 20 e 11 d-3
540
b7a1c -1 0 -1
The Primal Network Simplex Method (8)
Iteration 3. Entering arc is (g,h).
University of Victoria – CSC 445/545 – Summer 2021 73
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
j2i8k 3 11 7
-8
5 g -3 h 10
-4
5 14 15 10 5
-11f 20 e 11 d-3
540
b7a1c -1 0 -1
The Primal Network Simplex Method (9)
With (g,h) entering, the leaving arc is (j,i). The flow assigned to (g,h) will be 2 units.
University of Victoria – CSC 445/545 – Summer 2021 74
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -6 -1
j2i k 11
-8
5g?h -4
-11 f
5
e
d -3
5
bac
-1 0 -1
The Primal Network Simplex Method (10)
End of Iteration 3. Total cost is 156.
University of Victoria – CSC 445/545 – Summer 2021 75
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -9 -4
j3i8k 697
-8
7 g 2 h 10
-7
7 14 18 10 5
-11f 20 e 14 d-6
5 4 -3
b7a1c -1 0 -1
The Primal Network Simplex Method (11)
Iteration 4. Entering arc is (d,c).
University of Victoria – CSC 445/545 – Summer 2021 76
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -9 -4
j3i8k 697
-8
7 g 2 h 10
-7
7 14 18 10 5
-11f 20 e 14 d-6
5 4 -3
b7a1c -1 0 -1
The Primal Network Simplex Method (12)
With (d, c) entering, the leaving arc is (f , b). The flow assigned to (d, c) will be 5 units.
University of Victoria – CSC 445/545 – Summer 2021 77
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-12 -9 -4
jik
-8
g
2h
-7
-11 f
7 10
5
e d -6
5?
b7a1c -1 0 -1
The Primal Network Simplex Method (13)
Optimal. Total cost is 141.
University of Victoria – CSC 445/545 – Summer 2021 78
Supply/Cost
7 9 -10
j6i3k 524
-5
1g1h2
-1
3161
-4 5f4e3d0
10 5 2
b1a1c 2 -4 1
Flow
-9 -6 -1
j3i8k 697
-5
7 g 7 h 10
-4
12 11 15 15 5
-8f 17 e 11 d-3
345
b2a6c -1 0 -1
Unboundedness (1)
Question: Under what conditions would a minimum-cost flow problem be unbounded?
University of Victoria – CSC 445/545 – Summer 2021 79
Unboundedness (2)
v1 f1 v2
t f2
v6
f5
v3 f3
v5 f4 v4
In the ordinary Simplex Method, unboundedness is normally detected when selecting the leaving variable, which would normally place an upper bound on the increase of the entering variable. Specifically, an LP is unbounded if, for a particular entering variable, there are no possible leaving variables.
University of Victoria – CSC 445/545 – Summer 2021 80
Unboundedness (3)
v1 f1 v2
t f2
v6
f5
v3 f3
v5 f4 v4
In the Primal Network Simplex Method, after choosing an entering arc e, the leaving arc is selected to be the opposite-oriented edge with the smallest flow value in the cycle created by adding e to the basis.
University of Victoria – CSC 445/545 – Summer 2021 81
Unboundedness (4)
v1 t
v6
f5 + t
f1 + t v2
f2 + t
v3 f3 + t
v5
Question: What would happen if no opposite-oriented edges exist?
University of Victoria – CSC 445/545 – Summer 2021
82
f4 + t v4
Unboundedness (5)
v1 t
v6
f5 + t
v5
f1 + t
v2
f2 + t
v3
f3 + t
f4 + t
v4
If every edge in the cycle has the same orientation as the entering edge e, none of the flow values are constrained by the flow on edge e. Therefore, it will be possible to increase the flow along edge e without bound (and still maintain flow balance).
University of Victoria – CSC 445/545 – Summer 2021 83
Unboundedness (6)
v1 t
v6
f5 + t
f1 + t
v2
f2 + t
v3
f3 + t
v5
If, after selecting an entering arc, there are no opposite-oriented arcs in the cycle, then the
flow problem is unbounded.
f4 + t
v4
University of Victoria – CSC 445/545 – Summer 2021 84
Unboundedness (7)
v1 t
v6
f5 + t
f1 + t
v2
f2 + t
v3
f3 + t
v5
Question: Why does arbitrarily increasing the flow in this case result in the objective function
becoming unbounded?
f4 + t
v4
University of Victoria – CSC 445/545 – Summer 2021 85
Unboundedness (8)
v1 t
v6
f5 + t
f1 + t
v2
f2 + t
v3
f3 + t
v5
Before we can draw any conclusions about why this situation results in unboundedness, we
have to explore why e would be chosen as an entering arc at all.
f4 + t
v4
University of Victoria – CSC 445/545 – Summer 2021 86
Unboundedness (9)
If we chose a particular arc e = (u,v) to enter the basis (as part of a primal pivot), then we must have zuv < 0.
Recall, from the previous lecture, that 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.
University of Victoria - CSC 445/545 - Summer 2021 87
Unboundedness (10)
If zuv is negative, then the total global cost of the flow decreases by −zuv for each unit of flow that we transport across (u,v). Therefore, if there are no limits on how much flow we can send along (u,v), it is actually possible to make a profit by sending flow through the cycle indefinitely (without actually supplying any vertices). Since the objective of the primal problem is to minimize cost, cases where flow can be sent at a profit allow the objective value (total cost) to be made arbitrarily small (and negative).
The only way this can occur is if the total cost of transporting flow around the entire cycle (that is, the sum of the costs of each arc in the cycle) is negative. Therefore, unboundedness will only occur in networks which contain directed cycles with negative total cost.
One implication of this is that, if the cost of every arc is non-negative, the flow problem will be unbounded.
University of Victoria - CSC 445/545 - Summer 2021 88
Unboundedness Example (1)
The network above is the same as the earlier example, except that the weight of (a,e) has been set to be −10. This creates a negative cost cycle a, e, d, c, b.
University of Victoria - CSC 445/545 - Summer 2021 89
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 5
-6
-6
e3
09c
3d
-9
-1
3 a6b
0 -1
-2
Unboundedness Example (2)
Running the Primal Network Simplex Method will eventually reveal that the minimum-cost flow problem on this network is unbounded.
University of Victoria - CSC 445/545 - Summer 2021 90
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 5
-6
-6
e3
09c
3d
-9
-1
3 a6b
0 -1
-2
Unboundedness Example (3)
Iteration 1. Entering arc is (d,i).
University of Victoria - CSC 445/545 - Summer 2021 91
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 5
-6
-6
e3
09c
3d
-9
-1
3 a6b
0 -1
-2
Unboundedness Example (4)
With (d, i) entering, the leaving arc is (c, b). The flow assigned to (d, i) will be 3 units.
University of Victoria - CSC 445/545 - Summer 2021 92
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
hi
5
?
-6
3d
-9
e3
9c
3
-2
ab
0 -1
Unboundedness Example (5)
End of Iteration 1. Total cost is 250.
University of Victoria - CSC 445/545 - Summer 2021 93
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 2
3
0
e0
0 12 c
6
6d
-9
-7
4
a6b 0 -1
Unboundedness Example (6)
Iteration 2. Entering arc is (e,d).
University of Victoria - CSC 445/545 - Summer 2021 94
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
28h 6 i 10 2
3
0
e0
0 12 c
6
6d
-9
-7
4
a6b 0 -1
Unboundedness Example (7)
With (e, d) entering, the leaving arc is (f , i). The flow assigned to (e, d) will be 2 units.
University of Victoria - CSC 445/545 - Summer 2021 95
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-188 4
g
f
-11
hi
2
?
3
0
6d
-9
e
ab
0 -1
c
4
Unboundedness Example (8)
End of Iteration 2. Total cost is 236.
University of Victoria - CSC 445/545 - Summer 2021 96
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-181 -3
g
f
-11
21h 6 i 10 7
5
2 e0
0 12 c
-1
8d
-9
-7
-3
a6b 0 -1
Unboundedness Example (9)
Iteration 3. Entering arc is (c, b).
University of Victoria - CSC 445/545 - Summer 2021 97
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-181 -3
g
f
-11
21h 6 i 10 7
5
2 e0
0 12 c
-1
8d
-9
-7
-3
a6b 0 -1
Unboundedness Example (10)
With (c, b) entering, the leaving arc is (e, b). The flow assigned to (c, b) will be 12 units.
University of Victoria - CSC 445/545 - Summer 2021 98
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-181 -3
g
f
-11
hi
d
2 e0
12 c
?
-9
-7
-3
ab
0 -1
Unboundedness Example (11)
End of Iteration 3. Total cost is 224.
University of Victoria - CSC 445/545 - Summer 2021 99
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
-1 1 c
8d
-8
-6
12 a6b
0 -1
-2
Unboundedness Example (12)
Iteration 4. Entering arc is (a, e).
University of Victoria - CSC 445/545 - Summer 2021 100
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
-1 1 c
8d
-8
-6
12 a6b
0 -1
-2
Unboundedness Example (13)
Unbounded. The flow on the entering arc (a,e) can be increased without bound.
University of Victoria - CSC 445/545 - Summer 2021 101
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
hi
d
14
e 12
-8
-6
?c
12 a6b
0 -1
-2
Unboundedness Example (14)
Question: Does the presence of a negative-cost edge guarantee that the flow problem will be unbounded?
University of Victoria - CSC 445/545 - Summer 2021 102
Supply/Cost
10-6 1
g
f
-2
2h4i 7 15
4
2 e4
-9 8 c
2d
6
3
1 a1b
-6 -6
0
Flow
-172 -2
g
f
-10
21h 6 i 10 7
5
14
e 12
-1 1 c
8d
-8
-6
12 a6b
0 -1
-2