Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Numerical Methods for Optimization

Lecture 6: Maximum flow problems

Ola Jabali

DEIB, Politecnico di Milano

(2020/2021)

*Adapted slides from Edoardo Amaldi

1 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Outline
• Maximum flow problems
• Cuts and feasible flows
• Ford-Fulkerson’s algorithm
• Maximum bipartite matching

2 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Example

Maximum flow problem

Given a network G = (V, A) with an integer capacity kij ≥ 0 for each arc (i, j) ∈ A, and
nodes s, t ∈ V , determine a feasible flow from s to t of maximum value

3 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Example

4 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Feasible solution

Maximum flow problem

Given a network G = (V, A) with an integer capacity kij ≥ 0 for each arc (i, j) ∈ A, and
nodes s, t ∈ V , determine a feasible flow from s to t of maximum value

5 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cut example

6 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Application areas

Network flows
A class of network optimisation problems dealing with the distribution of
flow (“products") from a point of origin to a point of destination.
• A “product" can be gas, water, data, waste etc.
• Applications in energy, transportation and telecommunication

7 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Maximum flow problem

Setting

• Given a network on directed and connected graph G = (V, A)

with a source s ∈ V and a sink t ∈ V with s 6= t, and a capacity
kij ≥ 0 for each arc (i, j) ∈ A
• A feasible flow ~ x ∈ Rm with a
x from s to t is a vector ~
component xij corresponding to arc (i, j) ∈ A, and satisfying
the capacity constraints 0 ≤ xij ≤ kij , ∀(i, j) ∈ A

The value of the flow ~

x is
X
f (s) = xsj
(s,j)∈δ + (s)

where δ + (s) = {(s, j) : (s, j) ∈ A} and the flow balance is

X X
xhj − xih = 0, ∀h ∈ V \ {s, t}
(h,j)∈δ + (h) (i,h)∈δ − (h)

8 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Maximum flow problem

Given a network G = (V, A) with an integer capacity kij ≥ 0 for each arc
(i, j) ∈ A, and nodes s, t ∈ V , determine a feasible flow from s to t of
maximum value.

Model

max f
subject to
P
(s,j)∈δ + (s) xsj = f
P
(j,t)∈δ − (t) xjt = f
P P
(h,j)∈δ + (h) xhj − (i,h)∈δ − (h) xih = 0 ∀h ∈ V \ {s, t}
xij ≤ kij ∀(i, j) ∈ A
xij ≥ 0 ∀(i, j) ∈ A
f ≥0

where f denotes the value of the feasible flow

9 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cuts

Definitions
• A cut separating s from t is δ(S) of G with s ∈ S ⊂ V and t ∈ V \ V
• The capacity of the cut δ(S) induced by S is
X
k(S) = kij
(i,j)∈δ + (s)

10 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cuts and feasible flows

Definition
Given a feasible flow ~x from s to t and a cut δ(S) with s ∈ S and t ∈
/ S, the
value of the feasible flow x through the cut δ(S) is
X X
f (S) = xij − xij
(i,j)∈δ + (S) (i,j)∈δ − (S)

11 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Feasible flows
Property 1
Given a feasible flow ~x from s to t, for each cut δ(S), with S ⊆ V ,
separating s from t, we have

f (S) = f (s)

This implies that net flow sent across the cut δ(S) is equal to the amount
reaching t.
12 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cut example

13 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cuts and feasible flows

Property 2
For each feasible flow ~x from s to t and each cut δ(S), with S ⊆ V ,
separating s from t, we have

f (S) = k(S),

where f (S) is the flow the cuts and k(S) is the capacity of the cut
Proof
X X X
f (S) = xij − xij ≤ kij = k(S)
(i,j)∈δ + (S) (i,j)∈δ − (S) (i,j)∈δ + (S)

Implications of properties 1 & 2 on the previous example

f (s) = f (S1 ) ≤ k(S1 ) = 42

f (s) = f (s) ≤ k(s) = 30
f (s) = f (S2 ) ≤ k(S2 ) = 28
14 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Cuts and feasible flows

Consequence
If f (S) = k(S) for a subset S ⊆ V with s ∈ S and t ∈
/ S, then ~x is a flow of
maximum value and the cut δ(S) is of minimum capacity

Note
The property f (S) ≤ k(S) for each feasible flow ~x and cut δ(S) separating
s from t, expresses a weak duality relationship between the two problems:
• Primal problem: given G = (V, A) with integer capacities on the arcs
and s, t ∈ V , determine a feasible flow of maximum value.
• Dual problem: given G = (V, A) with integer capacities on the arcs and
s, t ∈ V , determine a cut (separating s from t) of minimum capacity

15 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s algorithm
Idea
Start from a feasible flow x and try to iteratively increase its value f by
sending, at each iteration, an additional amount of flow along a path from s
to t with a strictly positive residual capacity

Saturated / empty arcs

• An arc (i, j) ∈ A is saturated if xij = k
• An arc (i, j) ∈ A is empty if xij = 0

16 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s algorithm
Improving a given solution
Can the value of the current feasible flow ~x be increased?

• If (i, j) is not saturated (i.e., xij ≤ kij ), we can increase xij

• If (i, j) is not empty (i.e., xij ≥ 0), we can decrease xij while
respecting 0 ≤ xij ≤ kij

Intuition

17 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Residual network

Definition
Given a feasible flow ~x for G = (V, A), we construct the residual network
Ḡ = (V, Ā) associated to ~x, which accounts for all possible flow variations
with respect to ~x.
• If (i, j) is not saturated, (i, j) ∈ Ā with k̄ij = kij − xij
• If (i, j) is not empty (j, i) ∈ Ā with k̄ji = xij > 0

18 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Augmenting path

Definition
Give a the current feasible flow ~x, a path p from s to t is an augmenting path
is a path along which a positive flow can be sent

19 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s algorithm

Main structure
• At each iteration: given a feasible flow ~x, look for an augmenting path
p from s to t in G, this is done by constructing Ḡ and then searching for
a path from s to t in Ḡ
• If there exists an augmenting path from s to t in Ḡ , then the current
flow x is not optimal. Find the bottleneck capacity δ of p and augment
flow along p by δ
• If p does not exist then stop because ~x is optimal

20 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s example

Initial feasible flow ~x0 = 0

of value f0 = 0 (you may
start with any feasible flow)

Given ~x0 construct Ḡ. An

augmenting path along is
found along which we can
send δ = 2 additional units
of flow

21 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s example

Generate ~x1 according to

the found augmenting path.
Feasible flow ~x1 of value
f1 = 2

Given ~x1 construct Ḡ. An

augmenting path along is
found along which we can
send δ = 2 additional units
of flow

22 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s example

Generate ~x2 according to

the found augmenting path.
Feasible flow ~x2 of value
f1 = 4

Given ~x2 construct Ḡ. An

augmenting path along is
found along which we can
send δ = 1 additional units
of flow

23 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s example

Generate ~x3 according to

the found augmenting path.
Feasible flow ~x3 of value
f1 = 5

Given ~x3 construct Ḡ. No

augmenting path is found. t
is not reachable from s in Ḡ
S ∗ = {1, 4} is the subset of
all the nodes reachable from
+
the source s (δḠ = ∅)

24 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Ford-Fulkerson’s example
Consider ~x3 and
S ∗ = {1, 4} found in its
corresponding Ḡ (when no
augmenting path is found)

The feasible flow of ~x3 has

a value of f3 = 5 and the
cut δG (S ∗ ) = 5!

Observation: All outgoing

arcs of δG (S ∗ ) = 5 are
saturated and all entering 25 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Exactness

Proposition
Ford-Fulkerson’s algorithm is an exact algorithm

Proof
A feasible flow x is of maximum value ⇐⇒ t is not reachable from s in the residual network Ḡ associated
to ~
x
⇒ If there exists an augmenting path, ~x is not optimal
+
⇐ If t is not reachable from s, there exists a cut of Ḡ such that δḠ (S ∗ ) = ∅ (where s ∈ S ∗ ⊂ V )
+ − ∗
By definition we have a) every (i, j) ∈ δG(S ∗ ) is saturated, and b) (i, j) ∈ δG (S ) is empty. Therefore,

∗ ∗
X X X
f (S ) = xij − xij = xij − 0 = k(S )
+ − +
(i,j)∈δ (i,j)∈δ (i,j)∈δ
G(S ∗ ) G(S ∗ ) G(S ∗ )

x is of maximum value and the cut induced by S ∗ ,

Weak duality: f (S) ≤ k(S) ⇒ the feasible flow ~
namely δG (S ∗ ), is of minimum capacity.

Theorem (Ford-Fulkerson)
The value of a feasible flow of maximum value = the capacity of a cut of minimum capacity

26 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Summary of Ford-Fulkerson’s algorithm

27 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

The problem
Given m engineers, n tasks and for each engineer the list of tasks she can
perform. Assign the tasks to the engineers so that: a) each engineer is
assigned at most one task and b) each task is assigned to at most one
engineer
The objective is to maximized the number of tasks that are executed
(engineers involved).

28 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Bipartite graph of competences

Matching
Given an undirected bipartite graph
G = (V, E), a matching M ⊆ E is
subset of non adjacent edges

The problem
Given a bipartite graph G = (V, E), determine a matching with a maximum
number of edges

29 / 30
Introduction Maximum flow problem Cuts and feasible flows Ford-Fulkerson’s algorithm Maximum bipartite matching

Maximum bipartite matching

Note
Having several sources or sinks with a single type of product can be handled
by adding an artificial source node or an artificial sink node

Correspondence between the feasible flows (from s to t) of value f and the

matchings containing f edges

30 / 30