NETWORK THEORY

IE 428

Lecture 9: Min-Cost Flow Problem

Sina Rastani
 2

Pseudo-flows
A pseudo-flow is a "flow" vector such that satısfying only the capacity
and nonnegativity constraints.
Let denote the excess (deficit) at node where

If , we refer to as the excess of node i; if , we call the node’s deficit.

Notice that , and hence where E and D are the set of excess and deficit
nodes respectively.

This implies that if the network contains an excess node, it must also
contain a deficit node.
 3

Pseudo-flows

5 0 -2
2 10 -2 2 4
2 4 3
5 0 0
5 5 1 0
0
1 4 20
2 4
5 4 3 5
3 5
0 -3
2 -7

Supplies/demands and capacities A pseudo-flow and excesses

Pseudo-flows and the Residual Network

5 -2 5 -2
0 10
2 4 2 4
3 2
0 0 0
3 5
1 0 0 1 4 20
3

2 4 2
3 5 3 5
4
0 -3 0 -3

A pseudo-flow and excesses The residual network

The infeasibility of the pseudo-flow is . e.g., 5.

4
 5

Reduced Costs in G(x)

Let πi denote the node potential for node i.


cij  cij   i   j

For unit of flow out of node i, subtract πi from the cost.

For unit of flow into node j, add πj to the cost.

$3 $3 – π1 + π2
1 2 1 2

-$5 $1 $1 – π2 + π3
-$5 – π3 + π1

3 3
 6

Optimality Conditions
Theorem. Suppose that x* is flow and π* is a vector of node
potential. Then x* and π* are optimal if
1. the flow x* is feasible and
2. cπ*ij ≥ 0 for all (i, j) ∈ G(x*).
The second property is often called dual feasibility.
 7

Optimality Conditions
The cycle canceling algorithm starts with a feasible flow and
maintains a feasible flow at each iteration. It terminates with
dual feasibility.

The successive shortest path algorithm starts with (and

maintains) an infeasible flow x and node potentials π that are
dual feasible. It stops when it obtains a flow that is feasible.
Its main subroutine involves sending flow along a path from a
node with excess to a node with deficit.
 8

Successive Shortest Path Algorithm

• This algorithm maintains a pseudoflow in the network.
• A pseudoflow is a flow where the inflow into a node can be different that
the outflow of the node.
 9

Successive Shortest Path Algorithm

• The algorithm maintains the optimality of the pseudoflow at all
times.

• The algorithm starts with a zero pseudoflow x.

• The algorithm selects a node k with excess, selects a node l with
deficit, identifies a shortest path in G(x) from node k to node l,
and augments flow along this path.

• The algorithm terminates when there is no imbalanced node.

• The algorithm uses the reduced cost optimality conditions to
maintain optimality
 10

Successive Shortest Path Algorithm

• Theorem: Suppose a pseudoflow (or a flow) x satisfies the
reduced cost optimality conditions with respect to some node
potentials π. Let the vector d represent the shortest path distances
from some node k to all other nodes in the residual network G(x)
with as the length of an arc (i, j). Then the following properties
are valid:
•
1. The pseudoflow x also satisfies the reduced cost optimality
conditions with respect to the node potentials π′ = π –d.
• 2. The reduced costs are zero for all arcs (i, j) in a shortest
path from node k to every other node.
 11

Successive Shortest Path Algorithm

• Theorem: Suppose that a pseudoflow (or a flow) x satisfies the
reduced cost optimality conditions and we obtain x′ from x by
sending flow along a shortest path from node s to some other
node k; then x′ also satisfies the reduced cost optimality
conditions.
 12

Augmenting paths

5 10 -2 5 3 -2
2 4 2 4
2 0
0 0
3 5 0 0
1 4 20 1 4 8
3 0

2 0
3 5 3 5
0 4 -3 0 4 -3

Capacities and excesses in G(x) Excesses and reduced costs in G(x)

A path P from i to j in G(x) is augmenting if e(i) > 0, e(j) < 0, and ∀ (v, w) ∈ P,
cπvw = 0.
Augmenting along a path
The capacity of an augmenting
5 -2 path P from node i to node j is
2 4
min { e(i), -e(j), min(v,w)∈P rvw}.
In this case, the capacity is
3 5
1 min {5, 2, 3} = 2
3

3 5
To augment along a path P is to
send δ units of flow from i to j in
P, where δ = capacity(P).
The augmenting path with
residual capacities.

13
 14

Before and after the augmentation

5 10 -2 3 10 0
2 4 2 4
2
4
0 5 0
3 1 3
1 4 20 1 4 20
3 2
1

2 4
3 5 3 5
4 0 4 -3
0 -3

Capacities and excesses in G(x) Capacities and excesses in G(x)

before augmenting on P after augmenting on P
 15

The effect of augmentations

5 -2 3 3 0
3
2 4 2 4
0 0
0 0
0 0 0 0
1 4 8 1 4 8
2
0 0
0
0 0
3 5 3 5
4 4
0 -3 0 -3

Excesses and reduced costs Excesses and reduced costs after the
before the augmentation augmentation
Augmentations reduce the infeasibility by at least 1.
Augmentations maintain dual feasibility. Any arc added to G(x) is the reversal of an
arc with a reduced cost of 0.
 16

The Successive Shortest Path Algorithm

 17

A numerical example
 18

A numerical example
 19

Adjusting node potentials

Select node i with e(i) > 0.
Let d(j) = shortest path from node i to node j in G(x).
Replace πj by πj - d(j) for all j ∈ N.
-1 0
-2
1 1
2 2 3
2 3
0 0
1 0
2 0
0 6
5
1 0 4 4 0 1 0 4 -4

0 0 1 3
6 5 6 5
1 2 1 -1 2 -1
G(x) with reduced costs on arcs and
shortest path distances. e(1) > 0. Node potentials πj - d(j) and
reduced costs
 20

On Node Potentials
After adjusting node potentials, there is a path with 0-reduced cost arcs
in G(x) from node i to each other node (assuming that there is a path
from node 1).
-1 0
-2 0 7
-2
2 3 2 3
0 0 5
0 10 5 12
6 2
1 0 4 -4 1 10 4 -3

1 3 5 5
6 5 6 5
-1 2 -1 0 5 -5
Node potentials πj - d(j)and Excesses and capacities.
reduced costs
 21

Augment along a path from node i

Select a node j with e(j) < 0 that is reachable from node i. (Note that
Dijkstra algorithm can choose it if the heuristic in the previous slide is
used) Let P be the path from node i to node j.
Send min {e(i), -e(j), min {rvw : (v, w) ∈ P} } units in P.
0 -2
7 0 -2
2 3 4
5 2 3
10 5 12 2
2 7 2 3
1 10 4 -3
1
3 3 4 0
5 5
6 5 Send min {10, 3, 5} units of
0 5 -5 flow from 1 to 4. Update
residual capacities and
Excesses and capacities.
excesses.
 22

The Original Costs and Node Potentials

0 4 0
2 4

7
5
2
0 1 1

6
2
3 5

0 0
 23

The Original Capacities and Supplies/Demands

5 -2
10
2 4

30
25
23 20
1 20

20
25
3 5

-7 -19
 24

Select a supply node and find the shortest paths

shortest
7 4 8 path
distance
2 4

7
0 5 The shortest
2 path tree is
1 1
marked in
bold and blue.
6
2
3 5

6 8
 25

Update the Node Potentials and the Reduced Costs

-7 43 -8
2 4

7
0 5 0
6 2
0 1 1

0
6
2
3 5
0
-6 -8
 26

Send Flow From a Supply Node to a Demand Node Along Shortest Paths (along
arcs with reduced costs of 0)

5 -2 Arc numbers are

10 residual
2 4 capacities.

30 Red arcs have a

reduced cost of 0
25
23
20
1 20

send 7 units
from node 1
20
25 to node 3
3 5

-7 -19
 27

Update the Residual Network

5 -2 If an arc is added
10
to G(x), then it has
2 4
a reduced cost of
30 0, and it is red.
25
23
20
16 1 20
7 Arcs in the residual
network will
13 always have a non-
Arc (3,1) has 25 negative reduced
3 5
a reduced cost cost
of 0
-7 -19
0
 28

A comment
At this point, one would choose a source node, and then find the
shortest path from the source node to all other nodes, and then
update the residual network.

However, there are still paths of 0 reduced cost in the residual

network, and it makes sense to use them. This heuristic is quite
useful in practice.
 29

Send Flow From a Supply Node to a Demand Node Along Shortest

Paths
5 -2
10
Recall that red
2 4
arcs have a
30 reduced cost of 0
25
20
16 1 20
7
Send 2 units of
13 flow from node 1
25 to node 4
3 5

0 -19
 30

Update the Residual Network

5 -2 0
10
2 4

30 2 units of flow were

25 sent from node 1 to
18 node 4 on 1-3-4
16 1 20
2
14 9

11
25
3 5

0 -19
 31

Send Flow From a Supply Node to a Demand Node Along

Shortest Paths
5 0
10
2 4

30 Send flow from

25 node 1 to node 5
14 18
1 20
2 How much
9
flow should
11 be sent?
25
3 5

0 -19
 32

Update the Residual Network

5 0
10
2 4

30 11 units of flow
25 were sent from node
14 18 1 to node 5
1 20
3 2
20

14
3 5

11 -8
0 -19
 33

Select a supply node and find the shortest paths

-7 3 -8
2 4
The shortest path
tree is marked in
0 0 bold and blue.
6
0 1 1
0
0
The values on the
0 nodes are the
3 5 current node
0 potentials
-6 -8
 34

Update the node potentials and the reduced costs

0 -11
-7 3 -8
2 4
To obtain new node
potentials, subtract
0 0
3 the shortest path
0 1 1 distances from the
0
old potentials.
3
0
3 5
0
-6 -9 -8 -11
 35

Send Flow From a Supply Node to a Demand Node Along Shortest

Paths
5 0
10
2 4

30
25 Send flow from node 1
to node 5
18
3 1 20
2
20
How much
flow will be
14 sent?
3 5

11 -8
0
 36

Update the Residual Network

5 0
8
2 4
2
28
25 2 units of flow
3 2 20
1 20 were sent from
1
node 1 to node 5
20

12
3 5

13 -8
0 -6
 37

Select a supply node and find the shortest paths

-7 0 -11
2 4
0
0 The shortest
0 0 path tree is
3 marked in bold
0 1 1
and blue.
3
0
3 5
0
-9 -11
 38

Update the Node Potentials and the Reduced Costs

-7 0 -11
2 4
0
0 To obtain the new
1 node potential,
0 subtract the shortest
2
0 1 0 path distance from
the old potential.
4
0
3 5
0
-9 -11
-12
-10
 39

Send Flow From a Supply Node to a Demand Node Along Shortest Paths

5 0
8
2 4
2
28 Send flow from
25 node 2 to node 5
2 20
1 1 20
20 How much
flow can be
sent?
12
3 5

13
0 -6
 40

Update the Residual Network

5 0 0
3
2 4
7
28 5 units of flow were
25 sent from node 2 to
2 20 node 6.
1 1 5 15
20

12
3 5
-1
13
0 -6
 41

Send Flow From a Supply Node to a Demand Node

0 0
3
2 4
7
28 Send flow
25 from node 1
2 20 to node 5
1 1 5 15
20

12
3 5
-1
13
0
 42

Update the Residual Network

0 0
2
2 4
8 1 unit of flow was
27
25 sent from node 1 to
0 3 20 node 5.
1 1 6 14
20 The resulting flow
is feasible, and also
optimal.
12
3 5
-1
13
0 0
 43

The Final Optimal Flow

5 -2
10,8
2 4

30,3
25
23 20
1 20,6

20,20 25,13
3 5

-7 -19
 44

The Final Optimal Node Potentials and the Reduced Costs

-7 0 -11
2 4

Flow is at
0 1 lower
2
0 1 0 bound.
-4

3 5
Flow is at 0
upper -10 -12
bound
 45

The Capacity Scaling Algorithm

• This algorithm is an enhancement of the successive shortest
path algorithm.

• It ensures that in each augmentation, sufficiently large flow (at

least ∆) is sent from an excess node to a deficit node.

• The algorithm selects a node k with excess at least ∆, selects a

node l with deficit at least ∆, identifies a shortest path in G(x)
from node k to node l with residual capacity at least ∆, and
augments flow along this path.

• The algorithm terminates when there is no imbalanced node.

 46

The Capacity Scaling Algorithm

 47

The Capacity Scaling Algorithm