Nikola KNEŽEVIĆ, PhD Faculty of Transport and Traffic Engineering ...
26
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
26
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
- universal service segment
- initial list of factors for the examination
- distributive system units
- postal services
- efficiency
- regression analysis
- business activities
- factors
- -1 unit
- unit
Publié par
Langue
English
ELE539A: Optimization of Communication Systems
Lecture 3B: Network Flow Problems
Professor M. Chiang
Electrical Engineering Department, Princeton University
February 12, 2007Lecture Outline
• Network flow problems
• Problem 1: Maximum flow problem
• Ford Fulkerson algorithm
• Problem 2: Shortest path routing
• Bellman Ford algorithm
• Simple IP routing: RIP
• Dynamic ProgrammingGraph Theory Notation
G = (V,E): directed graph with vertex set V and edge set E
b : external supply to each node i∈V
i
u : capacity of each edge (i,j)∈E
ij
c : cost per unit flow on edge (i,j)∈E
ij
I(i) ={j ∈V|(j,i)∈E}: set of start nodes of incoming edges to i
O(i)={j ∈V|(i,j)∈E}: set of end nodes of outgoing edges from i
Sources: {i|b > 0}. Sinks: {i|b < 0}
i i
Feasible flow f:
P P
• Flow conservation: b + f = f , ∀i∈V
i ji ij
j∈I(i) j∈O(i)
• Capacity constraint: 0≤f ≤u
ij ijBasic Formulation
Network flow problem:
P
minimize c f
ij ij
(i,j)∈E
P P
subject to b + f = f , ∀i∈V
i ji ij
j∈I(i) j∈O(i)
0≤f ≤u
ij ij
In matrix notation as a LP:
T
minimize c f
subject to Af =b
0f u
|V|×|E|
where A∈R is defined as
8
>
1, i is the start node of edge k
<
A =
−1, i is the end node of edge k
ik
>
:
0, otherwiseSpecial Cases
• Maximum flow problem (this lecture)
• Shortest path problem (this lecture)
• Transportation problem (uncapacitated bipartite graph)
P
minimize c f
ij ij
i,j
P
m
subject to f =d , j = 1,...,n
ij j
i=1
P
n
f =s , i = 1,...,m
ij i
j=1
f ≥ 0, i = 1,...,m,j = 1,...,n
ij
Variables f . Constants d ,s ,c
ij j i ij
• Assignment problem (homework):
m =n,d =s = 1 in transportation problem
j i6
Maximum Flow Problem
maximize b
s
subject to Af =b
b =−b
t s
b = 0, ∀i =s,t
i
0≤f ≤u
ij ij
Reformulated as network flow problem:
• Costs for all edges are zero
• Introduce a new edge (t,s) with infinite capacity and cost −1
• Minimize total cost is equivalent to maximize f
tsFord Fulkerson Algorithm
1. Start with feasible flow f
2. Search for an augmenting path P
3. Terminate if no augmenting path
4. Otherwise, if flow can be pushed, push δ(P) units of flow along P
and repeat Step 2
5. Otherwise, terminate
Q: How to find augmenting path?
Q: How much flow can be pushed?Augmenting Path
Idea: find a path where we can increase flow along every forward edge
and decrease flow along backward edge by the same amount. Still
satisfy constraints. Increase objective function
Augmenting path: a path from s to t such that f <u on forward
ij ij
edges and f > 0 on backward edges
ij
Augmenting flow amount along augmenting path P:
ff
δ(P)= min min (u −f ), min f
ij ij ij
(i,j)∈F (i,j)∈B
Can search for augmenting path by following possible paths leading
from s and checking conditions aboveExample
12
4/12
a b a b
16
20
20
4/16
9
4
4/9
10 4
s 7 t s 10
7
13
13
4/4
4
c d c d
14 4/14
8
4/12
a b a b
4
7/20
20
11/16
12
4
4 4
4 4/9
s t s 7/10
7/7
10 7
5
13 13
4
4/4
10 11/14
c d c d
4Example
8
12/12
a b a b
4
15/20
13
5
11/16
7
11
1/4
11 5
4
s t s
3 10 4/9
7/7
7
13 4
8/13
4/4
11/14
3
c d c d
11
12 12/12
a b a b
5 19/20
5 15
11/16
11 3 1/4
4 9
s t s
11 7 10
7/7
5 5
4
8 12/13
4/4
3 11/14
c d c d
11
