Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Arthur Charpentierarthur.charpentier@univ-rennes1.fr
https://freakonometrics.github.io/

Université Rennes 1, 2017

Graphs, Networks & Flows@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

1Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flows & Matching
Ahuja, Magnanti & Orlin (1993) Network Flows: Theory, Algorithms, andApplications. Prentice-Hall
Bazaraa, Jarvis & Sherali (2010) Linear Programming and Network Flows Wiley.
Ford & Fulkerson (1962) Flows in Networks. Princeton University Press.
Goldberg, Tardos & Tarjan Network Flow Algorithms@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

2Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
Consider 5 cities,1> v = c ( " Rennes " ," Paris " ," Lyon " ," Marseille " ,"Toulouse " )2> x = c ( -1.6742900 ,2.348800 ,4.846710 ,5.38107 ,1.443670)

3> y = c (48.1119800 ,48.853410 ,45.748460 ,43.29695 ,43.6042600)

4> library ( maps )5> france <- map ( database = " france " , col = " grey " )6> points (x ,y , pch =19 , cex =2 , col = " red " )7> text (x ,y ,v , pos =3 , col = " red " )It can also be seen as a complete weighted graph.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

3Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
1> df = data . frame ( name =v , lat =y , lon =x , index
=1:5)

2

> D = round ( G e o D i s t a n c e I n M e t r e s M a t r i x ( df ) /
1000)

3

> library ( igraph )4> i = c ( rep (1 ,4) , rep (2 ,3) , rep (3 ,2) ,4)

5> j = c (2:5 ,3:5 ,4:5 ,5)6> df = data . frame ( a = i , b =j , w = diag ( D [i , j ]) )7

> g = graph . data . frame ( df , directed = FALSE )8> V ( g ) $ label = v

9> plot (g , edge . label = E ( g ) $ w )What is the path with minimal cost (length) that goes through all cities (andreturns back home) ?

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

4Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
Can be formulated as an integer linear programming problem. Set xij = Ai,j (xused since it is the unknown component), ui be some dummy variable, and cij
denote the distance from city i to city j. Consider
min

n
n
X
X

cij xij

i=1 j6=i,j=1

0 ≤ xij ≤ 1

i, j = 1, . . . , n;ui ∈ Zi = 1, . . . , n;nXxij = 1

j = 1, . . . , n;xij = 1i = 1, . . . , n;ui − uj + nxij ≤ n − 1

2 ≤ i 6= j ≤ n.

i=1,i6=jnX
j=1,j6=i@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

5Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
Let D = [Di,j ] denote the distance matrix, with Di,i = ∞, ci,j otherwise
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes

∞

309

562

766

556

Paris

309

∞

393

661

588

Lyon

562

393

∞

276

360

Marseille

766

661

276

∞

320

Toulouse

556

588

360

320

∞

5 cities, 5! = 24 possibilities (with assymmetric costs, otherwise 12).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

6Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
One can use brute force search1> library ( combinat )2> M = matrix ( unlist ( permn (1:5) ) , nrow =5)3> sM = M [ , M [1 ,]==1]

4> sM = rbind ( sM ,1)

5> traj = function ( vi ) {

6

+

s =0

7

+

for ( i in 1:( length ( vi ) -1) ) s = s + D [ vi [ i ] ,vi [ i +1]]

8+

return ( s ) }9> d = unlist ( lapply (1: ncol ( sM ) , function ( x )traj ( sM [ , x ]) ) )10> sM = rbind ( sM , d )11> sM [ , which . min ( d ) ]
d

12
13

1

2

@freakonometrics

3

4

freakonometrics

5

1 1854freakonometrics.hypotheses.org

7Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman Problem
12 cities, 12! = 39, 916, 800 possibilities (with assymmetric costs, otherwise 20
millions).

1> v2 = c (v , " Strasbourg " ," Angers " ," Bordeaux " ,"Dijon " ," Nancy " ," Montpellier " , " Nevers " )2> x2 = c (x,7.75 , -0.55 , -0.566667 ,5.016667 ,6.2 ,3.883333 ,3.166667)

3> y2 = c (y,48.583333 ,47.466667 ,44.833333 ,47.316667 ,48.683333 ,43.6 ,46.983333)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

8Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Branch and bound, Little algorithm, from Little, Murty, Sweeney & Karel (1963)
An algorithm for the traveling salesman problem
Step 1 find a lower bound for the total coste by removing to each raw the smallest element
Derive reduced matrix D
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes

∞

0

253

457

247

(-309)

Paris

0

∞

84

352

279

(-309)

Lyon

286

117

∞

0

84

(-276)

Marseille

490

385

0

∞

44

(-276)

Toulouse

236

268

40

0

∞

(-320)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

9Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithmand by removing to each column the smallest element
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes

∞

0

253

457

203

(-309)

Paris

0

∞

84

352

235

(-309)

Lyon

286

117

∞

0

40

(-276)

Marseille

490

385

0

∞

0

(-276)

Toulouse

236

268

40

0

∞

(-320)(-44)
Again D can be non-symmetric (and it will be afterwards).
Starting value for the cost: 309+309+276+276+320+44=1534@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

10Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Step 2: compute regrets (min on rows and columns)
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes

∞

0

253

457

203

Paris

0

∞

84

352

235

Lyon

286

117

∞

0

40

Marseille

490

385

0

∞

0

Toulouse

236

268

40

0

∞

(117)

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

(203)

(320)

11

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes∞0 (320)

253

457

203

Paris

0

∞

84

352

235

Lyon

286

117

∞

0

40

Marseille

490

385

0

∞

0

Toulouse

236

268

40

0

∞

(236)

@freakonometrics

freakonometrics

(84)

(320)

freakonometrics.hypotheses.org

12Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes∞0 (320)

253

457

203

Paris

0 (320)

∞

84

352

235

Lyon

286

117

∞

0

40

Marseille

490

385

0

∞

0

Toulouse

236

268

40

0

∞

(0)

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

(40)

(40)

13

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Rennes

Paris

Lyon

Marseille

Toulouse

Rennes∞0 (320)

253

457

203

Paris

0 (320)

∞

84

352

235

Lyon

286

117

∞

0 (40)

40

Marseille

490

385

0 (40)∞

0 (40)

Toulouse

236

268

40

0 (40)∞

Select the maximal regret path (arbitrarily if not unique) : Rennes → Paris (RP).
Consider now two alternatives:• either we keep (RP)• either we remove (RP)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

14Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
If we exclude (RP), the cost is known : 1534+320=1854.
If we include, consider the simplified matrix
Rennes

Lyon

Marseille

Toulouse

Paris

∞

84

352

235

Lyon

286

∞

0

40

Marseille

490

0

∞

0

Toulouse

236

40

0

∞

Here (PR) is ∞ otherwise, it will be a round trip.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

15

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Then derive the reduced matrix
Rennes

Lyon

Marseille

Toulouse

Paris

∞

0

268

151

(-84)

Lyon

50

∞

0

40

(0)

Marseille

254

0

∞

0

(0)

Toulouse

0

40

0

∞

(0)

(-236)
Total (reduction) cost is 84+236=320.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

16Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
And again, compute regrets
Rennes

Lyon

Marseille

ToulouseParis∞

0 (151)

268

151

Lyon

50

∞

0 (40)

40

Marseille

254

0 (0)

∞

0 (40)

Toulouse

0 (50)

40

0 (0)

∞

The maximal regret path is Paris → Lyon (PL). Consider now two alternatives:• either we keep (PL)• either we remove (PL) : cost will be 1534+320+151=2005
If we include, consider the simplified matrix (with possibly ∞ for (LP))@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

17Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
RennesMarseille

Toulouse

Lyon

50

0

40

Marseille

254

∞

0

Toulouse

00∞Note that this matrix cannot be simplified, here.
RennesMarseille

Toulouse

Lyon

50

0

40

(0)

Marseille

254

∞

0

(0)

Toulouse

0

0

∞

(0)

(0)

(0)

(0)

So the total cost if we keep (RL) is 1534+320=1854@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

18Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Then compute regrets
RennesMarseille

ToulouseLyon

50

0 (40)

40

Marseille254∞

0 (294)

Toulouse

0 (50)0 (0)∞The maximal regret path is Marseille → Toulouse (MT)Consider now two alternatives:• either we keep (MT)• either we remove (MT) : cost will be 1854+294
If we include, consider the simplified matrix (with ∞ for (TM))@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

19Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

RennesMarseille

Lyon

50

0

Toulouse

0∞

Here again no simplification. The regret matrix is

Lyon
Toulouse

RennesMarseille50

0 (50)

0 (50)∞The maximal regret path is Lyon → Marseille (LM)Consider now two alternatives:• either we keep (MT): cost will be 1854+0• either we remove (MT) : cost will be 1854+50@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

20Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Little Algorithm
Here we have constructed a search tree.

click to visualize the construction

click to visualize the construction

Remark This is an exact algorithm@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

21Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman
Exact algorithms are usually extremely slow. For Little Algorithm, the maximal
number of nodes, with n cities, is of order Nn with Nn = (n − 1)[1 + Nn−1 ] (withis of order n!).
1

> library ( TSP )2> df2 = data . frame ( name = v2 , lat = y2 , lon = x2 , index=1:12)

3> D2 = round ( G e o D i s t a n c e I n M e t r e s M a t r i x ( df2 ) /
1000)

4

> listeFR = TSP ( D2 , v2 )5

> tour = solve _ TSP ( listeFR , method = " nn " )6> COORD = df2 [ as . numeric ( tour ) ,]7

> COORD = rbind ( COORD , COORD [1 ,])8> france <- map ( database = " france " , col = " grey " )9> lines ( COORD $ lon , COORD $ lat , lwd =3 , col = " blue ")@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

22Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman1> tour = solve _ TSP ( listeFR , method = " nn " )2> COORD = df2 [ as . numeric ( tour ) ,]3

> COORD = rbind ( COORD , COORD [1 ,])4> france <- map ( database = " france " , col = " grey " )5> lines ( COORD $ lon , COORD $ lat , lwd =3 , col = " blue " )

6

>

7

> tour = solve _ TSP ( listeFR , method = " nn " )8> COORD = df2 [ as . numeric ( tour ) ,]9

> COORD = rbind ( COORD , COORD [1 ,])10> france <- map ( database = " france " , col = " grey " )11> lines ( COORD $ lon , COORD $ lat , lwd =3 , col = " blue " )It is not stable... local optimization?

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

23Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman
Historically, introduced by William Rowan Hamilton
in the context of dodecahedrons.
A Hamiltonian path is a path in agraph that visits eachvertice exactly once
Done with n = 20 cities (regular aglebraic structure)

Dantzig, Fulkerson & Johnson (1954) Solution of a large-scale traveling-salesman
problem with n = 49 cities (US State capitals)
In 2000, it was perfomed on n = 15, 000 cities, nowadays close to 2 million.
See also Applegate et al. (2006) The traveling salesman problem: a computational
study.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

24Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Stochastic Algorithm
One can use a Greedy Algorithm
Heuristically, makes locally optimal choices at each stage
with the hope of finding a global optimum.
nearest neighbour, “at each stage visit an unvisited citynearest to the current city”(1) start on an arbitrary vertex as current vertice.
(2) find out the shortest edge connecting current verticeand an unvisited vertice v.
(3) set current vertice to v.
(4) mark v as visited.
(5) if all the vertices in domain are visited, then terminate.
(6) Go to step 2.
click to visualize the construction@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

25Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Stochastic Algorithm
E.g. descent algorithm, where we start from an initial guess, then consider at
each step one vertice s, and in the neighborhood of s, denoted V (s) searchf (s? ) = 0min {f (s0 )}s ∈V (s)If f (s? ) < f (s) then s = s? .
See Lin (1965) with 2 opt or 3 opt, see also Lin & Kernighan(1973) An Effective Heuristic Algorithm for the TravelingSalesman Problem
The pairwise exchange or 2-opt technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge
removal into a new and shorter tour.
click to visualize the construction@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

26Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Kruskal’s algorithm is a minimum-spanning-tree algorithm, see Kruskal (1956)
On the shortest spanning subtree of a graph and the traveling salesman problem@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

27Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Select edge e = (u, v) ∈ E which minimizes ω ,e = argmin{ω }∈EThen remove e from the set of electible edges
E = E\{e}and mark that edge F = {e}@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

28Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Select edge e = (u, v) ∈ E which minimizes ω ,e = argmin{ω }∈EThen remove e from the set of electible edges
E = E\{e}and mark that edge F = F ∪ {e}If the minima is not unique, choose randomly@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

29Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
E = E\{E1 ∪ E2 } where we remove• all edges E1 such that E ∪ E1 contains a cycle (here Rennes-Paris)• all edges from a node that appears twice in E (here all edges connected toAngers)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

30Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
As long as there are no cycle, set e = argmin{ω } and then remove e from the set∈Eof electible edges E = E\{e}, and mark those F = F ∪ {e}@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

31Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Here again remove• all edges E1 such that E ∪ E1 contains a cycle (here Rennes-Paris)• all edges from a node that appears twice in E (here all edges connected toAngers)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

32Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Select edge e = (u, v) ∈ E which minimizes ω ,e = argmin{ω }∈EThen remove e from the set of electible edges
E = E\{e}and mark it F = F ∪ {e}@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

33Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Remove• all edges E1 such that E ∪ E1 contains a cycle (here Rennes-Paris)• all edges from a node that appears twice in E (here all edges connected toAngers)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

34Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Select edge e = (u, v) ∈ E which minimizes ω ,e = argmin{ω }∈EThen remove e from the set of electible edges
E = E\{e}and mark it F = F ∪ {e}Here e=Strasbourg-ParisIf the minima is not unique, choose randomly@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

35Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
Last but not least, remove• all edges E1 such that E ∪ E1 contains a cycle (here Rennes-Paris)• all edges from a node that appears twice in E (here all edges connected toAngers)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

36Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Spanning Algorithm
The collection of edges that were marked in F is our best cycle.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

37Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Christofides Algorithm
Use a spanning algorithm (as in Kruskal algorithm) G = (V, E) but
allow for vertices to have more than 2 incident edges.
Let V1 denote the set of vertices with odd degree, and let G1 = (V1 , E1 )denote the induced subgraph of G = (V, E).
Find a perfect coupling G01 of G1 (discussed in the next course).
Consider graph G0 with vertices V and edges E ∪ E10 .
If there are still vertices v with degree exceeding 2, consider shortcuts
i.e. (u, v) and (v, w) becomes (u, w).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

38Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Genetic Algorithm
See Potvin (1996) Genetic algorithms for the traveling salesman problem
Mutation can be used to diversify solutions by alterating (randomly) an
individual (possibly bit string)
Cross-Over is obtained by mixing two individuals (single point or two points)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

39Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Traveling Salesman
Can be performed on a (much) larger scalee.g. 48 State capitals in mainland U.S.
see Cook (2011) In Pursuit of the Traveling Salesman
for a survey.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

40Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Application of the Traveling Salesman Problem
See Fischetti & Pisinger (2016) Optimizing wind farm cable routing considering
power losses
See Fischetti & Monaci (2016) Proximity search heuristics for wind farm optimallayout@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

41Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Motivation
Harris & Ross (1955) Fundamentals of a Method for Evaluating Rail Net Capacities@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

42Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Motivation
Harris & Ross (1955) Fundamentals of a Method for Evaluating Rail Net Capacities@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

43Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Motivation
Harris & Ross (1955) Fundamentals of a Method for Evaluating Rail Net Capacities

The goal was to study the Soviet ability to transport things from the Asian sideto European side
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

44Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Motivation
Harris & Ross (1955) Fundamentals of a Method for Evaluating Rail Net Capacities

Also to study minimum cut@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

45Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
A Flow Network with capacities is F = (G, c) where G = (V, E) is a network,c : E → R is a capacity function, on each edge.
The absence of an edge can be seen equivalently as a 0 capacity: if (u, v) ∈/ E, weassume c(u, v) = 0.
Problem: it is not a cycle, water must come from somewhere (a source) and getout somewhere else (a sink).
The source node is supposed to have ressources, and the ink node is here
insatiable.
For every vertice v ∈ V , there is a path from the source s to the sink t through v.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

46Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow

Transform the network by adding two vertices to V : a source s and a sink t.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

47Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
Then add edges to E, e = (s, v) with s ∈ in(v)) and e = (v, t) for t ∈ out(v),@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

48Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flowand set values c on those new edges.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

49Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
A flow in G is a real-valued function f : V × V 7→ R, that satisfies these threeproperties:• Capacity constraint:
For all u, v ∈ V , we require f (u, v) ≤ c(u, v)
Flow from one vertex to another must not exceed given capacity.
• Skew symmetry (convention):
For all u, v ∈ V , we require f (u, v) = −f (v, u).
Flow from vertex u to vertex v is negative of flow in reverse direction.
• Flow conservation:
For all u ∈ V \{s, t}, we requireXf (u, v) = 0.

v∈V@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

50Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
The value of flow f is defined as the total flow leaving the source (and thus
entering the sink):X|f | =f (s, v)v∈V

X

The total positive flow entering vertice v ∈ V isf (u, v) and the totalu∈V,f (u,v)>0

positive flow leaving vertice u ∈ V isX

f (u, v)v∈V,f (u,v)>0

The total net flow at a vertice v ∈ V is the total positive flow leaving v minus thetotal positive flow entering v
A flow f in flow network G is integer-valued if f (u, v) is an integer for allu, v ∈ V .

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

51Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
Consider two vertices u, v ∈ V , and a flow f (u, v) = 9 from u to v

One might think of having f (u, v) = 15 and f (v, u) = 6

but keep in mind the skew symmetry f (u, v) = −f (v, u)Here the 6 from v to u are cancelled.
(cancellation will arise implicity in most algorithms).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

52Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Network Flow
For convenience, if V1 , V2 ⊂ V , denote f (V1 , V2 ) =X

f (u, v)u∈V1 ,v∈V2

Thus, flow conservation can be written f (u, V ) = 0 for any u ∈ V \{s, t}
Further f (V1 , V1 ) = 0 (because of skew symmetry)
and f (V1 , V2 ) = −f (V2 , V1 ) = 0
Finally, consider V1 , V2 , V3 ⊂ V with V1 ∩ C2 = ∅, thenf (V1 ∪ V2 , V3 ) = f (V1 , V3 ) + f (V2 , V3 ).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

53Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts
An s − t cut is a partitionning of V between two blocks Vs and Vt , sur that
Vt = V \Vs , with s ∈ Vs and t ∈ Vt
If f is a flow in G = (V1 ∪ V2 , E), then the net flow across the cut (Vs , Vt ) isdefined to be f (Vs , Vt ), and its capacity is capacity c(Vs , Vt ).
Note that it can include negative flows.
A minimum cut is a cut with minimum capacity over all cuts.
Proposition Let f be a flow in a flow network G with source s and sink t, let(Vs , Vt ) be a cut of G. Then the flow across (Vs , Vt ) is f (Vs , Vt ) = |f |.
Proof f (Vs , Vt ) = f (Vs , V ) − f (Vs , Vs ) = f (Vs , V ) = f (s, V ) + f (Vs \{s}, V ) =f (s, V ) = |f |.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

54Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts
Proposition The value of a flow f in a network G is (upper-)bounded by thecapacity of any cut (Vs , Vt ) in G.
X X
X X
Proof |f | = f (Vs , Vt ) =f (u, v) ≤c(u, v) = c(Vs , Vt )u∈Vs v∈Vt

u∈Vs v∈Vt

The minimum cut problem is to find an s − t cut with minimum capacity.
Example : on each edge e, write “f (e)/c(e)”@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

55Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts
Flow Value Theorem : Let f be a flow, and (V1 , V2 ) denote any s − t cut, then
the net flow accross the cut is equal to the flow value
XXX
f (e) −
f (e) =f ({s, v}) = |f |e∈out of(V1 )As a consequence, |f | ≤e∈into(V1 )Xv∈Vf (e), i.e. the flow value is at most the capacitye∈out ofV1

of a cut.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

56Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts
A cut is a vertice partition
V = Vs ∪ Vt with s ∈ Vs and t ∈ Vt . Its capacity is
X
cap(Vs , Vt ) =c((u, v)) (below, Vs is denoted S).
u∈Vs ,v∈out(u)Capacity = 10 + 5 + 15 = 30
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

57

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts

Capacity = 30 + 8 + 15 + 9 = 62

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

58Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017s − t Cuts

Capacity = 10 + 5 + 15 = 30

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

59Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Flows
Keep in mind that we represent f (e) and c(e) on the same edge.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

60Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Flows
Below another feasable flow

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

61Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Flows

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

62Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Flows & Cuts

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

63Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
See electrical power distribution in Canada
Power is generated in Vancouver (the source s) and all remaining power istransported to Winnipeg (the sink t).
Each high voltage cable has limited capacity (in MegaWatts).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

64Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
There a two cables between Edmonton and Calgary, and we care about the net
flow, Edmonton (v1 ) → Calgary (v2 ).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

65Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
What could be the/a maximum flow f ? ?
The flow out of s is lower than the capacity out, i.e. |f ? | ≤ 13 + 16 = 29
The flow into t is lower than the capacity into, i.e. |f ? | ≤ 20 + 4 = 24
Is the maximum flow |f ? | = 24 ? One can start with the feasible flow, for instancei.e. |f | = 19... can we go up to 24 ?

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

66Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Define a so-called residual network and find an augmenting path from s to t.

The residual capacity of this path is 4.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

67Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The new flow is the following@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

68Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The associated residual network is the following

There are no augmenting path...

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

69Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Let us start again with the same network, with capacities@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

70Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
We can start with a path, from s to t

The maximal capactity of this flow is 4

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

71Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The flow network f is here, and |f | = 4@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

72Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Consider the residual network, and pick an augmenting path from s to t

The maximal capactity of this flow is 7.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

73Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The flow network f is here, and |f | = 4 + 7 = 11

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

74Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Consider the residual network, and pick an augmenting path from s to t

The maximal capactity of this flow is 8.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

75Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The flow network f is below, and |f | = 4 + 7 + 8 = 19

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

76Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Consider the residual network, and pick an augmenting path from s to t

The maximal capactity of this flow is 4.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

77Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
The flow network f is below, and |f | = 4 + 7 + 8 + 4 = 23

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

78Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Electricity Flow, an Example
Consider the residual network, and there is no augmenting path from s to t

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

79Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Max-flow min-cut
Max-flow min-cut theorem: If f is a flow in a flow network G = (V, E) withsource s and sink t, then the following conditions are equivalent:• f is a maximum flow in G
• residual network Gf contains no augmenting path• there is a cut (Vs , Vt ) such that c(Vs , Vt ) = |f |How to compute the maximum flow, in practice ?

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

80Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Ford-Fulkerson
A first idea is the Ford-Fulkerson method, from Flows in Networks• start with some feasible flow
• get the residual flow network (a graph that shows where extra capacity isavailable)• augment paths (where extra capacity is available)• look also at cuts, that provide an upper bound for the maximum flow
The residual flow network is the network flow F = ((V, E), cf ) wherecf (e) = c(e) − f (e), ∀e ∈ E.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

81Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Ford-Fulkerson
Define the residual capacity between u and v, with respect to some flow f ascf (u, v) = c(u, v) − f (u, v) if (u, v) ∈ E
f (v, u) if (v, u) ∈ E

0 otherwise

because the flow either goes from u to v, or from v to u.
The residual network of f has the same vertices as G, but u and v are connected(edge u → v) if cf (u, v) > 0, and the weight of that edge is cf (u, v).
We can actually restrict ourself to Ef where Ef = {e ∈ E, cf (e) > 0}.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

82Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Residual Capacity
The residual capacity cp (f ) of an augmenting path p is the maximum additional
flow we can allow along that path,cp (f ) = min{cf (e), e ∈ path p}.
The Ford-Fulkerson algorithm is the following. Consider a network G with nodess, t and capacity c.
• for each edge (u, v) ∈ E , set f (u, v) = f (v, u) = 0• while there is a path p from s to t in the residual network Gf do• set cf (p) = min{cf (u, v) for (u, v) ∈ p}
• for each edge (u, v) ∈ p do
• f (u, v) = f (u, v) + cf (p) while f (v, u) = −f (u, v)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

83Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Ford-Fulkerson
If chosen poorly, algorithm can be extremely long, see@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

84Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Edmonds-Karp to improve Ford-Fulkerson
The Ford-Fulkerson algorithm is a greedy algorithm that computes the maximum
flow in a flow network, also called Edmonds–Karp algorithm.
See Ford & Fulkerson (1962) Flows in Networks
The Ford–Fulkerson algorithm can be implemented to solve the bipartite
matching problem in O(mn) time.
The Hopcroft–Karp 1973 algorithm solves in O(mn1/2 ) time, as the Even–Tarjan
1975, see also wikipedia
The Mądry 2013 solves in O(m10/7 ) time.
For non-bipartite graph matching, Blossom algorithm from (Edmonds 1965) is :O(n4 ) but the Micali–Vazirani 1980 algorithm solves in in O(mn1/2 ) time (seewikipedia)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

85Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Linear Programming
A linear program is a collection of linear constraints on some real-valued
variables, with come linear objective function.
A polytope is an n-dimensional body, with flat faces
A polytope is a convex polytope if for any point in the polytope, the line segmentjoining the two points lies within the polytope.
The feaseable region of a linear program is a convex polytope.
An extremal point is a corner point of the feasible region. Note that it cannot be
expressed as the convex co,bination of two (or more) in the polytope
A general program is either T max c xx∈Rd+
 s.t. Ax ≤ b
for some k × d matrix A,@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

86Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Linear Programming
or


 T

 min c xx∈Rd+
 s.t. Ax ≥ b
There are three possible cases• the feasible region is empty: there are no optimal values• the feasible region is unbounded: the optimal value is unbounded• the feasible region is a bounded convex polytope: an optimal value exist@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

87Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Linear Programming
Maximal Flow problems can be expressed as a Linear Programming problem Xf (u, v)
max


E


(u,v)∈E
XX s.t.
f (u, v) =f (v, u) ∀u, v ∈ V (conservation)(u,v)∈E(u,v)∈Es.t. f (u, v) ≤ c(u, v) ∀(u, v) ∈ E (capacity constraint)
s.t. f (u, v) ≥ 0 ∀(u, v) ∈ E@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

88Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Simplex & Interior Point Methods
Simplex Method (see wikipedia)
Consider a standard linear program T
max c · x subject to Ax ≤ b and x ≥ 0xThe linear program can be represented as a tableau of the form

1 −cT 0
0 A bInterior Point Method (see wikipedia)
In contrast to the simplex algorithm (which finds an optimal solution by
traversing the edges between vertices on a polyhedral set) interior-point methods
move through the interior of the feasible region.
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

89Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Extensions
Let us get back to the initial Soviet Railway example.
Note that there are several sources and several sinks.

How to find the maximum flow in the standard network ?
Consider a super source S that is connected to all sources, with infinite capacities
Consider a super sink T that is connected to all sinks, with infinite capacities@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

90Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Extensions
Consider a super source S that is connected to all sources, with infinite capacities
Consider a super sink T that is connected to all sinks, with infinite capacities@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

91Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Extensions
Other problems were mentioned in that example, like find edge-disjoint paths, orvertice-disjoint paths: what is the minimum number of train tracks needed to be
destroyed to prevent any transportation from the Asian side to the European
side?
Given a graph G = (V, E), with a source s and a sink t, what is the maximum
number of edge-disjoint paths from s to t ?
This can be solve easily with flow networks, defining a flow network with unit
capacities, for every edges. It is a 0-1 network (here, maximum flow can becomputed efficiently)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

92Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Extensions
Theorem Given a 0-1 flow network with a maximum flow f ? and maximum
number of edge-disjoint paths k ? , then |f ? | = k ? .
Proof: (1) By having a flow of 1 through every disjoint path, we obtain a flow ofsize k ? so |f ? | ≥ k ? .
(2) The converse is obtained by induction (starting with the case |f ? | = 0)
Consider a maximum flow (of size m ).
Remove every edge with 0 flow through it.
Find a path from s to t (it exists since |f ? | > 0).
Remove the edges of the path, to obtain a network with a flow of size m − 1
By the induction hypothesis , there are m − 1 edge-disjoint paths in this network.
Bring back the removed path, to obtain at least m edge-disjoint paths@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

93Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Networks & Flows : Extensions
Given a graph G = (V, E), with a source s and a sink t, what is the minimum
number of edges needed to be removed so that no path from s to t remains
Again, consider some 0 − 1 network, and find a maximum flow in this network.
Theorem Given a 0-1 flow network with a maximum flow f ? and minimum
number of edges needed to disconnect s from t k ? , then |f ? | = k ? .
Proof We have seen that f ? was actually the maximum number of edge-disjoint
paths|f ? | ≤ k ? since there are |f ? | edge-disjoint paths, and we need to remove at least
one edge from each|f ? | ≥ k ? since the minum cut is a set of disconnecting edges. And by the
max-flow/ min-cut theorem, there are |f ? | edges in the min-cut.
Menger Theorem (1927) the minimum number of disconnecting edges is equal
to the maximum number of edge-disjoint paths@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

94Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching
Consider a transport company, with three plants {A, B, C} and threeconstruction sites {L, M, N }Plants can supply (capacity), per week {sA , sB , sC }, {300, 300, 100}
Site can demand (requirement), per week {dL , dM , dN }, {200, 200, 300}
and costs of transportation are given in the following matrix
L

M

N

A

4

3

8

B

7

5

9

C

4

5

5

Let x(i, j) denote the number of units to be transported from source i todestination j@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

95Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching
Let si denote the supply and dj denote the demand, and c(i, j) the cost per unit,
from source i to destination j
X
X
Here total supply = total demand, i.e.
si =
dj
i

j

Hence, it is called a balanced problem.
Optimisation program is

min


X X


i

j



x(i, j)c(i, j)subject toXx(i, j) = si , ∀i,j@freakonometrics

freakonometricsXx(i, j) = dj , ∀j, x(i, j) ≥ 0, ∀i, j.

ifreakonometrics.hypotheses.org

96Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching
Initial solution - Northwest Corner Rule
1. Start by selecting the cell in the most “North-West” corner of the table.
2. Assign the maximum amount to this cell that is allowable based on therequirements and the capacity constraints.
3. Exhaust the capacity from each row before moving down to another row.
4. Exhaust the requirement from each column before moving right to anothercolumn.
5. Check to make sure that the capacity and requirements are met@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

97Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching
Stepping Stone Method
1. Select an unused square to be evaluated.
2. Beginning at this square, trace a closed path back to the original square via
squares that are currently being used (only horizontal or vertical moves allowed).
You can only change directions at occupied cells.
3. Beginning with a plus (+) sign at the unused square, place alternative minus(-) signs and plus signs on each corner square of the closed path just traced.
4. Calculate an improvement index, Ii j by adding together the unit cost figures
found in each square containing a plus sign and then subtracting the unit costs ineach square containing a minus sign.
5. Repeat steps 1 to 4 until an improvement index has been calculated for all
unused squares.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

98Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching• If all indices computed are greater than or equal to zero, an optimal solution
has been reached.
• If not, it is possible to improve the current solution and decrease total shipping
costs.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

99Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
A matching is stable if no unmatched man and woman each prefers the other tohis or her spouse.
The problem is to find a stable matching for any dating pool.
Iterative Process(0) each individual ranks the opposite sex(1) each man proposes to his top choiceeach woman rejects all but her top suitor(k) each man rejected on day (k − 1) proposes to his top remaining choiceeach woman rejects all but her top remaining suitor@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

100Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
It is a deferred-acceptance algorithm.
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara

Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(1.1)] {M, N } 7→ A and L 7→ B

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

101Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(1.2)] A 7→ M and B 7→ L : couples (A, M ) and (B, L) are engaged
Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(2.1)] N 7→ B
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

102Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(2.2)] B 7→ N : couples (A, M ) and (B, N ) are engaged
Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(3.1)] L 7→ C
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

103Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
Run the algorithm
Ana

Luke

Matthew

NormanLuke

Beatrice

Clara

Ana

Beatrice

Matthew

NormanLuke

Matthew

Ana

Clara

Beatrice

Clara

NormanMatthew

Luke

NormanAna

BeatriceClara[(3.2)] C 7→ L : couples (A, M ), (B, N ) and (C, L) are engaged@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

104Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Optimal Matching with Ranks
Theorem The deferred-acceptance algorithm arranges stable marriages.
Heuristically, each of the women that a given man prefers to his wife rejected him
in favor of a suitor she preferred.
Theorem (Gale-Shapley) In the solution found by the deferred-acceptancealgorithm, every man gets his best possible match
Theorem (Conway) In the stable matching found by the male-proposing
algorithm, every woman gets her worst possible match
Corrolary Waiting to receive proposals is a bad strategy.
Should people lie to improve the result ?
Theorem (Dubins-Freedman) No man (or group of men) can improve theirresults in the male-proposing algorithm by submitting false preferences.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

105Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Circulation with Supply and Demand
Flows with supply and demand corresponds to multiple sources and sinks
Each source has a certain amount of flow to give (its supply).
Each sink wants to get a certain amount of flow (its demand).

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

106Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Circulation with Supply and Demand
We want to find a flow f such that ∀e ∈ E, f (e) ∈ [0, c(e)]XX
and for each v ∈ V ,f (u, v) −f (u, v) = d(v)
uin

uout

The demand d(v) is the excess flow that should come into node.
Let S be the set of nodes with negative demands (supply). Let T be the set ofnodes with positive demands (demand).
X
X
In order for there to be a feasible ow, we must haved(s) +
d(t) = 0s∈S

Define D =

X

t∈T

d(t)

t∈T

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

107Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Circulation with Supply and Demand
To get back to a maximum flow problem, introduce a super source s? with edges
to every vertice in S and a super sink t? with edges to every vertice in T
Capacity of edge (s? , s) is −d(s) while capacity of edge (t, t? ) is d(t) .
Now we can use nax-flow algorithms to find a flow f .

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

108Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

More on Matching
Consider a set of vertices V , a matching is a set of edges E that do not have a setof common vertices : a matching is a graph (V, E) where each node has either
zero or one edge incident to it (see brilliant.org)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

109Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

More on Matching
A maximal matching is a matching to which no more edges can be added without
increasing the degree of one vertices to two (it is locally optimal)
A maximum matching is a matching with the largest possible number of edges (itis globally optimal)
A bipartite graph is a graph whose vertices can be divided into two disjoint andindependent sets V1 and V2 , with V1 ∩ V2 = ∅, such that every edge connects a
vertex in V1 to one in V2 (called A and B in the pictures).
Consider directed graphs, with edges from V1 to V2 .
Assume further that all edges have unit capacity.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

110Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

More on Matching
For a bipartite matching, with value k• there are no node in V1 which has more than one outgoing edge, where there isa flow• there are no node in V2 which has more than one incoming edge, where there isa flow• the number of edges between V1 and V2 carrying flow is equal to k
A perfect matching is a matching in which each node has exactly one edge
incident on it
König’s theorem states that, in bipartite graphs, the maximum matching is equalin size to the minimum vertex cover.
Hall’s marriage theorem provides a characterization of bipartite graphs whichhave a perfect matching and the Tutte theorem provides a characterization for
arbitrary graphs.
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

111Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)
See the Task Assignment Problem
A set of tasks that need to be complete.
A set of people , each qualified to do a different subset of tasks.
Each person can perform at most one task. Each task is performed by at mostone person.
Assign as many tasks as possible to people
Consider the bipartite graph, (V, E), where V = V1 ∪ Var2 , with V1 is the set ofpeople, V2 is the set of tasks. And there is an edge between every person andevery task that the person is qualified to do
A matching in an undirected graph is a set of vertice - disjoint edges.
The size of a matching is the number of edges in it.
A matching is possible on any kind of graph
A maximum matching of G is a matching of maximum size.
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

112Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)
How can we find such a matching?
Recall that on G = (V1 ∪ V2 , E),Xv∈V1d(v) =

Xd(v) = nE = |E|,v∈V2

since every edge of E contributes 1 to the sum of the degrees in each side
Simple case: assume that• Each person is qualified to do exactly k of the jobs.
• Every job has exactly k people that are qualified for it@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

113Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)
Since each person is qualified to do exactly k of the tasksXd(v) = k|V1 |v∈V1Since each task has exactly k people that are qualified to do itXd(v) = k|V2 |v∈V2Thus k|V1 | = k|V2 |, i.e. necessarily |V1 | = |V2 |A perfect matching of a graph G = (V, E) is a matching of size |V |/2.
So, a perfect matching for a bipartite graph can be obtained only when bothsides have the same size.
Consider a bipartite graph (V1 ∪ V2 , E), and a vertice v ∈ V1 , then the neighbor
set of v is
N (v) = {u ∈ V2 such that (v, u) ∈ E}.
and for a subset A1 ∈ V1 ,N (A1 ) = {u ∈ V2 such that (v, u) ∈ E for some v ∈ A1 }.
@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

114

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

If there is a subset A1 ⊂ V1 such that |A1 | > |N (A1 )| ten there is no perfectmatching in G.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

115Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)
Hall’s (Marriage) Theorem Consider a bipartite graph (V1 ∪ V2 , E) with
|V1 | = |V2 |, there exists a perfect matching in G if and only if for every A1 ⊂ V1 ,|A1 | ≤ |N (A1 )|Hall’s (Marriage) Theorem Consider a bipartite graph (V1 ∪ V2 , E), there
exists a perfect matching in G if and only if for every A1 ⊂ V1 , |A1 | ≤ |N (A1 )|Consider a bipartite graph G = (V1 ∪ V2 , E), the deficiency of G is

def(G) = max |A1 | − |N (A1 )|A1 ⊂V1

E.g. on the graph on the right def(G) = 1
Note that def(G) ≥ 0@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

116Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)

Theorem Consider a bipartite graph G = (V1 ∪ V2 , E), thenthe size of the maximum matching is V1 − def(G).
In a bipartite graph G = (V1 ∪ V2 , E), and let M denote amatchin. A path is alternating for M if it starts with an unmatched vertice of V1 and every other edge of it is in M .

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

117Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)

An alternating path is augmenting for M if it also ends withan unmatched vertice.
Let M denote an an augmenting path, then by switching theedges that are in M with the edges that are not, we obtain alarger matching.
Theorem If a matching M in a bipartite graph G = (V1 ∪V2 , E) is not a maximum matching, then there exists an augmenting path for M .

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

118

Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (0/1 weights)
This can be used to set up an algorithm to find a maximum matching
Consider a bipartite graph G = (V1 ∪ V2 , E), start with any maching M (even asingle edge)
Repeatedly find an augmenting path for M , and use it to find a larger matching@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

119Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matchings and Network Flows
Given a bipartite graph G = (V1 ∪ V2 , E), why not use a max-flow algorithm tofind a maximum matching of G ?
Add a source s and edges to every vertice of V1 , and a sink t and edges to every
vertice of V2
Direct edges from s to vertices of V1 , then to vertices of V2 and finally to t.
Set capacities to 1.
There is a bijection between the matchings of G and the flows of the network.
Theorem A max-matching corresponds to a max-flow.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

120Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Try the following one@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

121Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (general weights)
Consider now the case where non-negative weights w(e) are assigned to each edgee ∈ E, see as a cost matrix w
Example : you want to send three sales managers to three cities. They areincities {A, B, C} and they need to visit {D, E, F }Here are the cost of airplane ticksts
D

E

F

A

250

400

350

B

400

600

350

C

200

400

250

Where should you send each of your salespeople in order to minimize airfare?

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

122Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Bipartite Matching (general weights)
One possible assignment/matching is {A, D}, {B, E},{C, F }, and the total costis 1100
One possible assignment/matching is {A, D}, {B, F },{C, E}, and the total costis 1000
There are n! ways of assigning n resources to n tasks.
Theorem: If a number is added to or subtracted from all of the entries of any
one row or column of a cost matrix, then on optimal assignment for the resulting
cost matrix is also an optimal assignment for the original cost matrix.

@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

123Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Hungarian Algorithm (Kuhn-Munkres)
Step 1. Subtract the smallest entry in each row from all entries of its row.
Step 2. Subtract the smallest entry in each column from all entries of its column.
Step 3. Draw lines through appropriate rows and columns so that all zero
entries of the cost matrix are covered and minimum number of such lines is used.
Step 4. Test for Optimality:(i) If the minimum number of covering lines is n, an optimal assignment of zeros
is possible and we are finished.
(ii) If the minimum number of covering lines is less than n, an optimal
assignment of zeros is not yet possible. In that case, proceed to Step 5.
Step 5. Determine the smallest entry not covered by any line. Subtract thisentry from each uncovered row, and then add it to each covered column. Returnto Step 3 (see hrefhttps://brilliant.org/wiki/hungarian-matching/brilliant.org)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

124Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Hungarian Algorithm (Kuhn-Munkres)
In our previous example
Step 1:
D

E

F

D

E

F

A

250

400

350

A

0

150

100

B

400

600

350

B

50

250

0

C

200

400

250

C

0

200

50

D

E

F

D

E

F

A

0

150

100

A

0

0

100

B

50

250

0

B

50

100

0

C

0

200

50

C

0

50

50

∼

Step 2:@freakonometrics

freakonometrics∼

freakonometrics.hypotheses.org

125Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Hungarian Algorithm (Kuhn-Munkres)
Step 3. Cover all the zeros of the matrix with the minimum number of horizontal
or vertical lines@freakonometrics

freakonometrics

D

E

F

A

0

0

100

B

50

100

0

C

0

50

50

freakonometrics.hypotheses.org

126Arthur Charpentier, Master Statistique & Économétrie - Université Rennes 1 - 2017

Hungarian Algorithm (Kuhn-Munkres)
Step 4. Since the minimal number of lines is 3, an optimal assignment of zeros ispossible and we are finished
Since the total cost for this assignment is 0, it must be an optimal assignment.
D

E

F

D

E

F

A

0

0

100

A

250

400

350

B

50

100

0

B

400

600

350

C

0

50

50

C

200

400

250

∼

(we keep the same assignment to the original cost matrix)@freakonometrics

freakonometrics

freakonometrics.hypotheses.org

127