離散システム特論 powerpoint資料5

Class Plan
•
•
•
•
•
1-1．Graph グラフ
1-2．Graph Search グラフ探索
+ some graph properties
1-3．Network Flow ネットワーク・フロー
1-4．Algorithms＆Complexity アルゴリズムと計算量
• 2-1．Minimum Spanning Tree 最小木
( + data structures and sorting データ構造，整列）
• 2-2．Matroid マトロイド
3-0. Shortest path 最短路
• 3-1. Maximum Flow 最大流
• 3-2． Minimum Cost Flow 最小費用流
• ?4-1. Approximation algorithm 近似解法
• ?4-2． Heuristics
ヒューリスティック
Network Flows
classical , traditional (?)
• maximum flow
• minimum cost flow
Variants in flows
• generalized flow
• multicommodity flow
• dynamic flow
• Problem Formulation
• Optimality condition
• (Algorithm)
Maximum Flow Problem (最大流問題)
Given : directed graph G=(V,A)
total out flow from s
Find :
which satisfies
• flow bound constraints :
(容量制約)
and
• mass balance constraints :
(流量保存制約)
=
v
• feasible flow(可能流) : a flow satisfying the above two constraints
• maximum flow(最大流) : a feasible flow maximizing
Example
instance
capacity
3
4
5
s
2
3
入口
4
t
出口
4
3
2
Are the following flows feasible/maximum ?
3
1)
4
1
2
s
0
1
3
2)
2
1
s
1
4
4
3
t
4)
3
5)
4
4
1
s
2
1
3
4
2
2
1
t
3
4
2
2
1
t
3
3
3
s
1
s
2
3
t
4
4
t
2
3
4
4
1
3
2
3
3)
For evaluate a bottleneck of flow value …
• s-t cut :
• capacity of an s-t cut
3
3
4
5
3
s
2
4
t
3
4
4
5
3
s
2
2
total out flow from s :
v≠s
t
3
4
2
4
Feasible flow and s-t cut
total out flow from s :
Total out flow ∂φ（ｓ） ≦ capacity of δ+(X)
Maximum-flow Minimum-cut Theorem
(Corollary 4.2)
(s-t cut with minimum capacity)
Ford-Fulkerson(1956)
Augmenting path method(偽)
step0:
step1:
instance
Augmenting path
capacity
s
2
2
2
3
1
ε
step2:
4
1
3
ε
t
3
flow:
s
0
0
0
s
0
0
0
0
2
0
0
s
0
2
0
0
0
2
1
0
2
0
0
t
s
0
0
0
2
0
2
0
2
1
3
t
0
?
1
t
2
t
0
There is no s-t directed path.
3
caps
s
0
2
s
0 +1
2
2-1 1
0
3 -1
0
1 +1
t
2
2
0
1
1
2
1
2
☆ residual network G  (V, A ),u
1
A  AF  AB
2
2
2
1
1
1
2
2
1
arcs represent the possibility of
pushing flow back on arcs
4
1 2
1
2 1
3
t
t
3
AF  {a  A |  (a)  u(a)}, AB  {a r |  (a)  0} a r :reverse arc of a
s
3
t
s

1
3
1
2
2
4
2
u(a)   (a) (a  AF )
u (a)  
r
B
  (a ) (a  A )
1
2
3
t
Augmenting path method (本物)
step0:
step1: construct a residual network
step2: Find an s-t directed path P in G  (V, A )
If there is no such a path …
step3: compute ε
and update flow along
 P
Go to step1.
s
0
2
2
2
0
s
2
s
0
1
1
t
3
1
12
s
1
3
2
21
1
t
11
1
2
4
2
2
1
3
1
3
3
1
2
t
3
3
1
2
2
caps
1
1
4
2
2
1
2
← augmenting path
21
1
3
12
t
no augmenting path
t
When no augmenting path exists …
: feasible flow
There is no s-t directed path (augmenting path ) in G  (V, A )
s
s
t
t
X
X : set of vertices reachable
from s
→ s-t cut
total out flow from s
“Maximum “

Optimality condition
Theorem4.1 (Augmenting path theorem)
A feasible flow φ is maximum ⇔ there is no augmenting path in G  (V, A )
⇒) If there is an augmenting path in G  (V, A )
…..
） proved


⇒
Maximum-flow Minimum-cut Theorem
(s-t cut with minimum capacity)
Ford-Fulkerson(1956)
Max … min…
duality
Max flow problem
Min cut problem
Subject to
◆Show the dual problem
◆Show the complementary slackness condition
Review of LP (dual problem)
Example:
Maximize 4x1+x2+3x3
Subject to x1- x2- x3＝ 1
2x1+x2+2x3≦13
x1, x2, x3≧０
A (quick) estimate of the optimal value (upper bound)
Since x1, x2, x3 are nonnegative,
Obj func. = 4x1+x2+3x3 ≦ 4x1+2x2+4x3≦26
2nd constraint ×2
Obj func. = 4x1+x2+3x3 ≦ 5x1+x2+3x3≦27
2nd constraint ×2 + 1st constraint
Review of LP (dual problem)
Example:
Maximize 4x1+x2+3x3
Subject to x1- x2- x3＝ 1
2x1+x2+2x3≦13
x1, x2, x3≧０
Linear combination
1st constraint ×y1 + 2nd constraint ×y2
(y1+2y2)x1+ (-y1+y2)x2 +(-y1+2y2)x3 ≦ y1+13y2
If
y1+2y2 ≧ 4
-y1+y2 ≧1
-y1+2y2 ≧3
We need y2 ≧０
coefficient of each xi is at least as big as the
corresponding coefficient in obj. function.
then obj. function ≦ y1+13y2
Review of LP (dual problem)
dual
primal
m
minimize bi yi
n
maximize c j x j
i1
m
j1
n
subject to
 aij x j  bi
(i  1,..., )
j1
n
 aij x j  bi
subject t o
 aij yi  c j
( j  1,...,n)
i1
yi  0 (i   1,...,m)
(i   1,...,m)
j1
x j  0 ( j  1,...,n) 
The dual of the dual problem is always the primal problem

m  n
m
m

c j x j   aij yi x j   aij x j yi  bi yi

j1
j1i1
i1j1
i1

n
n
Review of LP (duality theorem)
x*
: primal opt. sol
⇒ There exists
s.t.
y*
: dual opt. sol
n
m
 c j x * j  bi y *i
j1


i1
Review of LP (complementary slackness)
x*
y*
: primal feasible sol
: dual feasible sol
x* y *
: opt. solutions
m
 aij y *i  c j or x * j  0 ( j  1,...n)
i1
  n
 a x *  b or y *  0 (i  1,...m)
i
i
 ij j
j1

(proof)

Form

m  n
m
m

c j x j   aij yi x j   aij x j yi  bi yi

j1
j1i1
i1j1
i1

n
n
Augmenting path method (complexity)
Analyze the worst case time complexity for the augmenting path method
step0:
step1: construct a residual network
step2: Find an augmenting path P inG  (V, A )
If there is no such a path, stop.
step3: compute ε
and update flow
Go to step1.
 P
along
Instance 1
capacity
M
M
1
s
t
M-1
1
M
M
s
residual network
M
M
1
1
M-1
M-1
1
M
1
s
1
1 M-1
t
M
M
1
s
t
1
M
M-1
Number of iterations : ?
M-1
t
Instance 2
M
1
3
1
r
M
5 1
( 1),
2
M4
M
r
1
s
t

r k  r k1
r k1  r k  r k1
M
M
2
M
4

P1=(s,2,1,3,4,t)
P2=(s,1,2,4,3,t)
P3=(s,3,1,2,4,t)
◆Find maximum flow
◆If the algorithm chooses augmenting path as P1, P2, P1, P3, P1, P2, P1, P3, ,,,
how many iterations the algorithm performs?
Rules for selecting augmenting paths
Maximum capacity augmenting path
… Find an augmenting path maximizing αε
•Max capacity augmenting path algo.
•Capacity scaling algo.
•MA ordering algo.
Minimum length augmenting path
… Find an augmenting path with least edges
•Min length augmenting path algo.
•Dinitz’s blocking flow algo.
Max capacity augmenting path algo.
step0:
step1: construct a residual network
step2: Find an augmenting path P in G  (V, A )
If there is no such a path, stop.
step3: compute ε
and update flow
Go to step1.
 P
along
An s-t directed path
maximize
min{uφ(a)|a∈A(P)}
Max capacity augmenting path
algo.(complexity)

※ integer capacity
* :
:
 ':
Opt. flow
A flow
Flow obtained by updating along a max cap. aug. path
(1
1
)( * (s)   (s))  ( * (s)   '(s))
m
 1 m 1
1  
 m  2
The number of iteration
 O(m log(nU))
× maxmin type shortest path
U=max{u(a)|a∈A}
Capacity scaling algorithm
※ integer capacity
Bit scaling
u(a) 
u
(a)

Capacity of kth scaling phase k

2 K k 

K  logU  1
φ ←２ φ
kth scaling phase
find a maximum fow φw.r.t uk

s
2
5
1
4
5
3
2 3
3
find a maximum fow φw.r.t uk+1
s
010
5
t
(k+1)th scaling phase
101
101
011
001
010 011
100
011
K=3 (log25=2.32…)
101
t
Capacity scaling algorithm
s
010
u1
s
0
101
101
011
001
010 011
100
011
1
1
t
s
0
0
0
1
0
1
1
0
0
0
0
10
10
0
s
01
00
10
01 01
10
２
×２
1
u2
01
t
0
Max flow
0
uk(a)=2uk-1(a) or 2uk-1(a)+1
101
t
01
２
0
0
0
２
0
1
0
0
0
t
0
Max flow
t
u3
010
101
101
011
001
010 011
100
011
101
t
Capacity scaling algorithm(complexity)
Step0: φ:=0, K  logU  1 k:=1
Step1: [k scaling phase] find a maximum flow
φ with respect to uk
 If k=K, then stop. Else k:=k+1, φ:=2φ,
Step2:
and go to step 1.

×２
Max flow
1
0
２
1
0
0
0
0
0
0
0
0
0
0
t
uk(a)=2uk-1(a) or 2uk-1(a)+1
２
２
0
1
0
u(a) 
uk (a)   K k 
2 
0
Max flow
t
Min cut value in the
auxiliary network:
≦m
(the number of cut edges)
Minimum length augmenting path
Other algorithms
Push-relabel algorithm
flow bound constraints
No augmenting path
Network simplex algorithm
preflow
mass balance constraints
Max flow on planar graph
s-t planar graph … the graph added the arc (t, s) is still planar
capacity
s
2
4
2
2
1
3
3
1
3
s-t cut = s*-t* path
min cut = shortest path
t
Class Plan
•
•
•
•
•
1-1．Graph グラフ
1-2．Graph Search グラフ探索
+ some graph properties
1-3．Network Flow ネットワーク・フロー
1-4．Algorithms＆Complexity アルゴリズムと計算量
• 2-1．Minimum Spanning Tree 最小木
( + data structures and sorting データ構造，整列）
• 2-2．Matroid マトロイド
• 3-1. Maximum Flow 最大流
• 3-2． Minimum Cost Flow 最小費用流
• ?4-1. Approximation algorithm 近似解法
• ?4-2． Heuristics
ヒューリスティック
minimum circulation problem
(最小費用循環流問題)
Given： directed graph G=(V,A)
capacity u: A → R+
cost
c: A → R
Find : flow
:A → R+ minimizing total cost
which satisfies
・flow bound constraints
and
・mass balance constraints
• feasible flow
• minimum cost flow
Example
instance
(cap,cost)
(3,-1)
(4,3)
(3,0)
(2,2)
(1,-1)
(1,-3)
(2,2)
(2,1)
(4,2)
0
3
0
0
0
0
2
1
0
2
0
0
1
1
0
0
2
1
0
2
total cost = 0
total cost = 12
0
1
1
0
0
1
0
total cost = -2
residual network w.r.t. a flow
☆ residual network G  (V, A ),u
A  AF  AB
AF  {a  A |  (a)  u(a)}, AB  {a r |  (a)  0} a r :reverse arc of a

arcs represent the possibility of
pushing flow back on arcs
u(a)   (a) (a  AF )
u (a)  
r
B

(a
)
(a

A

 )
 c(a) (a  AF )
c(a)  
r
B
c(a ) (a  A )
optimality condition (negative cycle…)
Let
be a feasible flow
The following statements are equivalent :
MCF-(a) :
is minimum cost flow
MCF-(b) : the residual network
negative-cost cycles
directed cycle C with
MCF-(c) : There exists π：V → R such that
holds for every
does not have any
(a) ⇒(b)
If the residual network has a negative cost cycle, …
(b) ⇒(a)
: a flow satisfying (b)
: optimal flow
: feasible flow in
can be decomposed into cycles in
⇒
is optimal
negative cycle canceling algorithm
step0 :
=0
step1 : construct the residual network
Shortest path algorithm
step2 : Find a negative-cost cycle C in
(cap,cost)
If there is no such a cycle, stop.
step3 : compute
(3,-1)
and update flow
along C.
(2,2)
Go to step1.
(1,-3)
0
1
0
0
0
0
(2,2)
0
1
1
0
(4,2)
0
0
0
0
residual network
0
optimal
(2,-1)
(3,-1)
(1,1)
(4,3)
(3,0)
(3,0)
(2,2)
(1,-3)
(2,2)
(4,2)
(1,2) (1,-2)
(1,-1)
(2,1)
(4,3)
(1,3)
(2,2)
(1,-1)
(2,1)
(4,2)
(1,-1)
(2,1)
0
0
0
(4,3)
(3,0)
LP form
Minimize
Subject to
◆Show the dual problem
◆Show the complementary slackness condition
Compare to optimality conditions
Optimality condition (reduced cost)
c p (a)  c(a)  p( a)  p(a)
potential
p  
Kilter diagram
c p (a)  0   (a)  0

p( a) 
p(

 a)
c p (a)  0   (a)  u(a)
c p (a)  0  0   (a)  u(a) 
u(a)

 (a)
Modified network w.r.t. p
G=(V, A)
Modified capacity
 0

u p (a)  u(a)
u(a)


 0
(c p (a)  0)

(c p (a)  0) l p (a)   0
u(a)
(c p (a)  0)

(c p (a)  0)
(c p (a)  0)
(c p (a)  0)
Optimality condition (positive cut)
A potential p is dual optimal if and only if
in the modified network w.r.t. p any cut δ(X) satisfies
 u p (a)   l p (a)
a  ( X )

Positive cut : a cut with

a  (X )
 u p (a)   l p (a)
a  ( X )
a  (X )
Positive cut canceling algorithm
step0 : p: any potential
Max flow algorithm
step1 : construct the modified network
step2 : Find a positive cut in modified network
(cap,cost)
If there is no such a cut, stop.
step3 : compute




m in c (a) | a    (a),c (a)  0 , 
p
p


  m in


m in c p (a) | a   (a),c p (a)  0  (3,0)


p(v)   (v  X)
and update potential p(v)  

1
 p(v)
Go to step1.
(3,-1)
(4,3)
(2,2)
(1,-3)
(v  X)
(2,2)
(2,1)

0
0
0
(0, 0)3
(0, 0)3
(0, 0)2
(1, 1)-1
(1, 1)-3
0
0
(0, 0)1
(0, 0)2
0
(0, 0)2
modified network
(Ip,up)cp
0
(4,2)
(0, 3)0 1
(0, 3)0
(3, 3)-1 0 
(0, 3)0
(1,-1)
(0, 0)2
(0, 1)0
(1, 1)-4
1
0
(0, 3)0
(0, 2)0
(0, 0)2
0
(0, 0)2
0
(0, 3)0 1
0
(0, 0)3
(0, 2)0
(0, 1)0
(1, 1)-2
1
(0, 2)0
(0, 2)0
2
(0, 0)4
0
Other algorithms
Primal dual algorithm
Network simplex algorithm
+Scaling technique

Download Report