6CCS3OME/7CCSMOME – Optimisation Methods
Lecture 5
Minimum cost flow problem Multicommodity flow problems
Tomasz Radzik and Kathleen Steinho ̈fel
Department of Informatics, King’s College London 2020/21, Second term
Minimum cost flow problem
(6,3)
3 (4,3) (3,2)
1
3
1 (1,2) 4(4,1)
(1,5)
4
(8,1)
(2,2)
(4,3)
1 (2,3) (3,2)
2 (3,8)
Cost of this flow:
1*2 + 4*7 + 3*3 + … = 114
+8
−6
(5,7)
4 (4,5)
2
+5
−4
−3
G = (V, E, u, c, d).
A Flow Network:
• V – set of nodes, E – set of directed edges (links).
• Foreachedge(v,w)∈E,
3 (4,1)
u(v, w) ≥ 0 is the capacity of edge (v, w) (the 1st number on the edge). • For each node v ∈ V , (as in the flow-feasibility problem),
|d(v)| is the (initial) supply (if d(v) > 0)
or demand (if d(v) < 0) at v. v∈V d(v) = 0. • Foreachedge(v,w)∈E,
c(v,w) ≥ 0 is the cost of one unit of flow on edge (v,w)
(the 2nd number on the edge). 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
2 / 27
1
3 Is there a cheaper solution? (3,3)
Minimum cost flow problem (cont.)
• Objective: Find a flow which satisfies all supply and demand and has the minimum possible cost,
or determine that it’s not possible to satisfy supllies/demands.
• Formally, a flow (in network G) is a function f : E → R, assigning flows to
edges,
f(v,w) isthenon-negative(amountof)flowonedge(v,w),
which satisfies the capacity constraints and the flow conservation constraints.
• Thecostofaflowf is: (v,w)∈E
c(v, w)f (v, w).
• Capacity constraints: For each edge (v, w) ∈ E, f (u, v) ≤ u(v, w).
• A technical assumption (for convenience): if (v,w) ∈ E, then (w,v) ̸∈ E.
(3, 5) (3, 5) vwvw
(3, 5) (3, 0)
(2, 6) (2, 6) 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
(2, 6)
vw
3 / 27
Flow conservation constraints
• Netflowoutgoingfromnodev: f(v,x)− f(z,v).
b
(a + b + c) − (d + e) .
a
v
d e
c
• Flow conservation constraints:
(v,x)∈E
net flow out of v:
(z,v)∈E
• the net flow outgoing from each transitional node (d(v) = 0) is 0;
• the net flow outgoing from each “supply” node v is at most d(v);
• the net flow incoming to each “demand” node v is at most
|d(v)| = −d(v) (the demand at v),
or equivalently, the net flow outgoing from v is at least d(v)
Formally, the net flow outgoing from v: = 0, if d(v) = 0, f(v,x)− f(z,v)= ≤ d(v), ifd(v)>0,
(v,x)∈E (z,v)∈E
• A flow satisfies all supplies and demands,
≥ d(v), if d(v) < 0.
if the net flow outgoing from each vertex v is equal to d(v). 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
4 / 27
Flow conservation constraints: example
(6,3)
a
−3 t2
2 (4,1)
b
1 (2,3) s2 +5
2 (3,8) 1 (1,2)
t3 −4
type of node
node
net flow out
supply
transitional supply node
d(v) a,b,g,v 0 = 0
demand nodes
net flow in demand
net flow out d(v)
1
(3,2) 2 (4,3)
3 (4,3) 3(4,1)
(1,5)
net flow out from v:
3
(8,1)
t1
(2,2)
12
(3,3) = 0, if d(v) = 0,
+8 g s1 (3,2)
−6
≤ d(v), ifd(v)>0, ≥ d(v), ifd(v)<0.
(5,7)
3 (4,5)
2
s1 s2
7≤8 4 ≤ 5
t1 t2 t3
−d(v) 5≤6⇔−5≥−6
v
3≤3⇔−3≥−3
3≤4⇔−3≥−4 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 5 / 27
Application: Production and distribution problems
• A car manufacturer produces several car models in several plants and ships them to several retail centres.
• Each retail centre requests a specific number of cars of each model.
• Determine the production plan for each plant and the shipping schedule so that the total cost of production and transportation is minimized. (Application 9.1 in Ahuja, Magnanti and Orlin’s textbook).
• We can model this problem as a minimum cost flow problem:
• four types of nodes: plant nodes, plant/model nodes, retailer/model
nodes and retailer nodes;
• three types of edges: production edges, transportation edges and demand edges.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
6 / 27
Application: Production and distribution problems (cont.)
+120
+180
p1 (100, 5)
p2
p2/m2
r2/m1
p2/m2 (50, 3)
r1/m2
p1/m1
r1/m1
p2/m1
r1/m3
p2/m3
r2/m2
(80, 0.5)
(70, 0.6)
r1
• A production edge (pi, pi/mj): capacity – maximum possible production of cars mj at plant pi; cost – production cost of one car mj at plant pi.
• A transportation edge (pi/mj, rk/mj): transportation of cars mj from plant pi to retailer rk; capacity and transportation cost per one car.
• A demand edge (rk/mj, rk): capacity - demand for cars mj at retailer rk.
• Supplies at nodes pi (production capacities) and demands at nodes rk. 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
7 / 27
(90, 0)
r2
−200
−100
Application: Production and distribution problems (cont.)
+180
p1
70
30 40
+120 50
30
30
p2
p2/m2
r2/m1
p1/m1
r1/m1
p2/m2
p2/m1
r1/m3
80
20 100 40
80
p2/m3 80
r2/m2
• A (integral) flow corresponds to a feasible production/transportation schedule.
• A minimum cost (integral) flow gives an optimal (minimum cost) production/transportation schedule.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
8 / 27
60
r1/m2
r1
90
80
r2
20
−200
−100
Sending flows along cheapest paths
• Take a node v which has positive remaining supply;
find a cheapest path from v to a node w with positive remaining demand; send as much flow as possible from v to w along this path.
• Example:
1-st path: (a, c, p)
2-nd path: (a, i) 3-rd path: (b, c, i)
+5
(5,3)
−9
a2 37
i
(4,1) (8,4)
c
(9,5) (3,0)
+7 7 b
3
• Thecostofthisflow: 2∗3+3∗1+7∗5+7∗4+3∗0=72. Notoptimal.
• Sometimes we have to “re-route” the flow to get the optimal cost. 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
9 / 27
(4,3)
p
−3
Residual network
• Let f be a flow in network G = (V,E,u,c,d).
• The residual capacity of an edge (w, v) ∈ E:
uf (w, v) = u(w, v) − f (w, v).
w
2 (3, 5)
(1, 5)
x (y, z)
flow capacity cost
capacity = 3; 2 units of flow
residual capacity = 1
v
w
v
• If (w, v) ∈ E and f (w, v) > 0, then the residual capacity of a reverse edge (v,w) is uf(v,w) = f(w,v), and its cost is c(v,w) = −c(w,v).
2 (3, 5)
(1 5)
w (2, −5) v
wv
The positive residual capacity of the reverse edge (v, w) represents possibility of reducing (some) flow on the actual edge (w, v).
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
10 / 27
Residual network (cont.)
2 (3, 5)
(1 5)
w (2, −5) v
wv
• The negative costs of the reverse edges ensure that sending flow g(x, y) through a residual edge (x, y) changes the cost of the flow by c(x, y)g(x, y).
Sending flow g(v, w) through a reverse residual edge (v, w) represents reducing the flow on the actual edge (w, v) by g(v, w) and this reduces the cost of the flow by c(w, v)g(v, w), so the cost of flow changes by:
−c(w, v)g(v, w) = c(v, w)g(v, w).
• For each node v ∈ V , the residual supply/demand at v is
df(v)=d(v)− f(v,x)+ f(z,v). (v,x)∈E (z,v)∈E
• The residual network of network G with respect to flow f is
Gf =(V,Ef,uf,c,df), whereEf isthesetofresidualedges(edgeswith positive residual capacities).
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
11 / 27
Example: residual networks and cheapest paths in residual networks
current flow in input network:
residual network: [3,3]
+5 a
[4,1] 3
i −9 a i [3,−1]
[8,4] 0 +7 b
[3,0] 3
p −3
[8,4] [3,0]
[5,3] 2
[2,−3]
−7
[4,3] 0
+7 b p [4,3]
flow in residual network: [3,3] 3
new flow in input network:
+7 b
[4,3] 3
a
[2,−3] [3,−1] 3
i [9,5]
−7
+5 a
[4,1] 0
[1,1] [8,4]
c
[8,4] 0 +7 b
[9,5] 0 [1,1] cc
[9,5]
path:
[4,3] 3
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
12 / 27
[3,0] 3 p
p −3
[5,3] 5
i −9
c
[9,5] 0 [3,0] 0
cost: (b, c, i) 9 (b,p,c,i) 8 (b,c,a,i) 6 (b,p,c,a,i) 5
Example (cont.)
current flow in input network:
flow in residual network: [3,3] 3
new flow in input network:
+5 a
i −9 [9,5] 0
a
i −9
[4,1] 3
[9,5] ccc
[9,5] 0 [3,0] 0
[8,4] 0 +7 b
[3,0] 3
p −3 +7 b
[3,0] 3 p
[8,4] 0 +7 b
p −3
[5,3] 2
[2,−3] [3,−1] 3
i −7 +5 a
[4,1] 0
[5,3] 5
[4,3] 0
[4,3] 3
[4,3] 3
flow fold
value(fold) = 2+3 = 5
flow fp value(fp) = 3
flow fnew = fold ↑ fp
cost(fold) =
3 · 2 + 1 · 3 + 0 · 3 = 9
cost(fp) = (3+0+(−1)+3)·3 = 15
value(fnew) = value(fold) + value(fp) =5+3=8
Additional cost £18 for sending the additional 3 units through edges (a, i) and (b, p), but £3 back because after all we’re not using edge (a, c).
cost(fnew) = cost(fold) + cost(fp) = 9 + 15 = 24
(= 5 · 3 + 3 · 3)
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
13 / 27
[1,1] [8,4]
Successive shortest path algorithm
SUCCESSIVESP(G)
(6,3)
(4,3) (3,2)
(4,1) (8,1)
(3,3)
f ← zero flow;
+8 (5,7)
−6
S={v∈V :d (v)>0} f
(4,5)
(4,1)
while S is not empty do
compute the residual network Gf ;
select a node v ∈ S; { an arbitrary node v ∈ S would do } compute a shortest-path tree T in Gf from v
to all nodes reachable from v;
if there is a node w in T with residual demand (df (w) < 0) then
P ←thepathinT fromvtow; {anyw∈T withdf(w)<0woulddo} q← min{df(v), −df(w), min{uf(x,y):(x,y)∈P}};
fP ← theflowofvalueqinGf alongpathP ;
f ← f ↑fP; {updateflowf bysendingqunitsofflowalongpathP } if df(v)=0 then S←S−{v};
else S←S−{v}.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 14 / 27
(2,3)
(3,8)
(3,2) (2,2)
(4,3)
(1,2)
+5
−4 (1,5)
−3
Successive Shortest Paths algorithm: correctness and running time
• At the end of each iteration, the current flow f has the minimum cost among all flows which satisfy the same demands and supplies as flow f. This can be shown by induction on the number of iterations (not easy!).
• Cost of residual edges can be negative, but no negative cycles.
• Appropriate “h(v)” numbers can be (efficiently) maintained so that in each iteration the “re-weighted” costs are non-negative.
The re-weighting scheme is as in Johnson’s all-pairs shortest-paths algorithm: cˆ(v,w)=c(v,w)+h(v)−h(w).
Thus in each iteration, the computation of a shortest path tree can be done by Dijkstra’s shortest path algorithm, in O(min{m log n, n2}) time.
• If all input edge capacities and node supplies/demands are integral, then the number of iterations is at most {d(v) : v ∈ V, d(v) > 0} (the total supply in the network).
• The number of iterations can be exponential in the number of nodes.
• There are algorithms for the minimum cost flow problem which run in
polynomial time. The best known asymptotic running time of an algorithm
for the minimum cost flow problem is O(m2 log2 n).
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 15 / 27
Multicommodity flow problems
• Input instance:
• a (directed) network G = (V, E, u), where u(x, y) is the capacity of an
edge (x, y) ∈ E;
• k commodities. Commodity q (1 ≤ q ≤ k) is specified by (sq,tq,dq),
where
• sq ∈ V and tq ∈ V are the origin (source) and the destination (target)
of commodity q,
• dq (> 0) is the (amount of) demand of this commodity.
• Design simultaneous flow of all commodities which satisfies the demands of all commodities, and optimises some specified global objective.
• Application: allocation of communication paths to requests in telecommunication networks.
• For some multicommodity flow problems, flows do not need to satisfy the edge capacity constraints.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
16 / 27
Example
• Specification of a network: 736
s1
t2 44c
d
2327
6
3q
5 t3
5 t1 s2 a b s3
• Specification of commodities:
commodity source destination amount
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
17 / 27
p
1db3 2ac6 3bq4
Example (cont.)
• Simultaneous flow of all commodities:
s1 d
t2
3
26
s2
a
b
s3=t1
2 24c
• Specification of commodities:
commodity source destination amount
p
q
4
t3
1db3 2ac6 3bq4
• Remark: this flow does not satisfy the edge capacities given on the
previous slide.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
18 / 27
Flow of commodities
• A simultaneous flow of the specified commodities consists of separate flows of the individual commodities: ⟨f1, f2, . . . , fq, . . . , fk⟩
• Aflowfq ofcommodityqisafunctionfq :E→R,
where fq (x, y) is the amount of flow of commodity q on edge (x, y), which satisfies the flow conservation constraints.
(The capacity constraints not always present!)
• Flow conservation for commodity q:
the net flow of commodity q outgoing from the origin sq is dq;
the net flow of commodity q incoming to the destination tq is dq (equivalently, the net flow outgoing from tq is equal to −dq);
the net flow outgoing from each node v ∈ V − {sq, tq} is equal to 0.
• Formally, the flow conservation constraints for commodity q says that for each node v, the net flow from v is equal to:
d, ifv=s, q q
fq(v,x)− fq(z,v) = −dq, ifv=tq.
(v,x)∈E (z,v)∈E
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 19 / 27
0, ifv∈V−{sq,tq}.
Feasibility multicommodity-flow problem
Design simultaneous flow ⟨f1, f2, . . . , fk⟩ of all commodities which satisfies the capacity constrains:
for each edge (v, w) ∈ E, the total flow on this edge is at most the capacity u(v, w) of this edge, that is,
f(v, w) = [the total flow on edge (v, w)] In this example,
defn.
= fq(v, w) ≤
u(v, w).
f (p, q) = 3 + 2 + 4 = 9. s1
s2
a
b
s3=t1
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
20 / 27
d
3
26
2 24c
p
q
4
t3
k
q=1
t2
Minimum-cost multicommodity-flow problem
• Each edge (v, w) ∈ E, in addition to its capacity u(v, w), has also a cost c(v, w) associated with it.
s1
t2
d
2,1
4,4
7,2
c
6,2
3,5
5,3
7,1
a b6,3 3,6
s2 5,1 s3=t1
4,2
3,4
2,3
p
q
• The cost of a simultaneous flow ⟨f1, f2, . . . , fk⟩ is equal to
c(v,w)f(v,w) = c(v,w)[f1(v,w)+f2(v,w)+···+fk(v,w)].
(v,w)∈E (v,w)∈E
• Design simultaneous flow of all commodities which satisfies the capacity
constraints and has the minimum possible cost.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 21 / 27
t3
Minimum-congestion multicommodity-flow problem
• The congestion of flow on an edge (x, y) is defined as: f(x,y), the total flow on edge (x,y).
In this example, if u(p,q) = 10 and u(a,p) = 3, then the congestion:
s2 a
b
s3=t1
t2
on edge (p, q) is 9/10 = 0.9 (or 90%), on edge (a, p) is 4/3 = 1.33… (or 133%).
s1 d
2
4
c
• Design simultaneous flow of all commodities which minimises the maximum congestion, that is,
u(x, y)
minimise: maxf(x,y) : (x,y) ∈ E. u(x, y)
• Note that the optimal (minimal) congestion may be greater than 100%. 6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
22 / 27
3
2
6
p
q
4
t3
2
Computational approaches to multicommodity flow problems
• Specialised algorithms
A possible approach: start with some initial simultaneous flow, and iteratively keep improving it by re-routing (a fraction of) the flow of each commodity onto better paths.
Undirectededgecapacities:2; commodities:(b,c,2),(a,b,2),(a,c,2).
b
c optimal congestion 1.0 b c
a
←−
a
congestion 1.5; cannot improve by rerouting one path
• Mathematical programming
Express the mutlicommodity flow problem as a linear program (or other appropriate “mathematical program”) and use the general linear programming methods (a number of commercial and public-domain linear
programming packages are available).
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 23 / 27
−→
Exercises – LGT
1. We have an input network G for a minimum-cost flow problem and a flow f in this network which satisfies all supply and demand requirements and edge capacity constraints. Argue that if f′ is a flow in the residual network Gf which is positive only on the edges of one cycle, then f ↑ f′ is a flow in G which satisfies all supply and demand requirements and edge capacity constraints.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 24 / 27
Exercises – LGT (cont.)
2. A network and flow in this network are shown below. The numbers in parentheses next to an edge are the capacity (the first number) and the cost of this edge. The flow is highlighted in red.
(6,3)
(2,2) +8
(4,1) 4(4,1)
1
3
1
3 1
(1,5)
4
(8,1)
1 (2,3) (3,2)
+5
2 (3,8) (1,2)
−4
(5,4)
4 (4,3)
2
3 (4,3) (4,2)
−6
(4,3)
(a) Show that there is a negative cost cycle in the residual network.
−3
3 (4,1)
(b) Improve the cost of flow by sending flow along a negative cycle in the residual network. How does the flow and the cost of flow change?
(c) Compute a minimum-cost flow in this network using the Successive Shortest Paths algorithm. Give priority to the vertex with the initial supply +5 (when selecting from set S).
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 25 / 27
Exercises – SGT
Consider the following instance of the minimum-congestion multicommodity-flow problem.
Network:
Commodities:
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow
26 / 27
q
(4)
(2)
(3)
c
(4)
(5)
(3)
p
(1)
(5) a
b
commodity source destination demand
d
1bd3 2aq7 3bc4
Exercises – SGT (cont.)
1.
Check that the flow of each commodity given in the table below satisfies the flow conservation constraints. What is the maximum edge congestion?
2.
Show that the maximum edge congestion of the above flow can be improved by re-routing some flow of commodity 3 from edge (b, c) onto the path ⟨b, p, q, c⟩. By how much can you reduce this way the maximum edge congestion? We allow fractional flows (that is, flows on edges can be fractional numbers).
3.
By checking the total capacity of the edges going from the set of nodes {a, b} to the set of the remaining nodes {c, d, p, q}, argue that for this input, there is no flow which has the maximum edge congestion less than
edge → (a,b) (a,q) (b,c) (b,p) (c,d) (p,d) (p,q) (q,c)
commodity1: 0 0 2 1 2 1 0 0 commodity2: 3 4 0 3 0 0 3 0 commodity3: 0 0 3 1 0 0 1 1
7/6 ≈ 1.17.
6CCS3OME/7CCSMOME, Lecture 5: Min-cost flow, Multicommodity flow 27 / 27