グラフ・ネットワークの基礎用語

ネットワーク理論講義補助資料
Text.
組合せ最適化とアルゴリズム
4.3 節 Lagrange緩和
pp. 115-123


Lagrange緩和は,2.3.3 節(pp.44-48) で線形計
画の双対問題を導出するときに用いた.
ここでは,時間制約付きの最短路問題に対する
Lagrange緩和の適用を例に,Lagrange緩和の
一般論について解説
大名の例題
12時間以内に氷を献上せよ!
10,1
s
始点
5,10
1
1,15
t
終点
6,1
3,3 2,1
飛脚に払う費用
と移動時間
2
5,1
3
Lagrange緩和のアイディア
制約の時間を費用に換算! (1時間=2両)
10両+1時間×2(両/時間)
12
s
1
31
8
9 4
25
2
t
7
3
1時間=2両
変換された費用に対する最短路 s->1->2->3->t (最適値は31)
(本当の)費用=23両,時間=4時間 ->12時間以内だけど高い!
Lagrange緩和のアイディア
制約の時間を費用に換算(1時間=1両)
11
s
1
16
7
6 3
15
2
t
6
3
1時間=1両
新しい最短路 s->1->t (最適値は27)
(本当の)費用=11両,時間=16時間 ->12時間を超えてしまった!
1時間=?両にすれば良い?
数学者なら変数を導入! 1時間=λ(ラムダと読む)両とする.
10+λ
s
1
1+15λ
3+3λ 2+λ
5+10λ
2
5+λ
殿様が12時間にもってこいと言っている
のだから,12×λ(両)は負担する.
t
6+λ
3
[λを色々変えたときの最適パス
の費用-殿様からのカンパ]はどんな関数?
s->1->t:
(10+1)+(1+15)λ-12λ=11+4λ
s->1->2->3->t: (10+2+5+6)+(1+1+1+1)λ-12λ= 23-8λ
s->2->1->t:
=[
]
s->2->3->t:
=[
]
L(λ):一番安いパスを選択することによって
得られる関数(区分的に線形な凹関数)
L(λ)
9+16λ
23
11+4λ
16
16
15
11
9
0
23-8λ
1
2
λ
L(λ)が下界を与えることを示そう!
(時間)制約付き最短路問題の定式化(0-1整数計画)
注:数値を入れた具体的な導出はテキスト参照
最小化  cvw xvw
vwE
条件 
最短路の条件
 xwv 
w:wvE
x
w:swE
w:vwE
vw
 0, v  V \ s, t
x
w:wtE
制約付き最短路の
場合は0,1条件が必要!  1
x
枝vwの移動時間T vw
sw
T
vwE
wt
1
x  Tmax
vw vw
xe  {0,1}, e  E
制限時間 Tmax
線形計画に緩和(0-1条件をとる!)
(時間)制約付き最短路問題の線形計画緩和
最小化  cvw xvw
vwE
条件 
 x 
x
w:swE
sw
 1
x
 0, v  V \ s, t

1
wv
vw
時間制約条件
w:wvE
w:vwE
をLagrange緩和
(式に定数を乗じて
xwt
目的関数に加える)
w:wtE
T
vwE
x  Tmax
vw vw
xe  0, e  E
Lagrange緩和問題の導出(1)
(絶対に失敗しない方法)
時間制約を満たしていれば
必ず0以下
非負のLagrange乗数λ
最小化  cvw xvw  (  Tvw xvw Tmax )
vwE
条件 
 xwv 
w:wvE
x
w:swE
vwE
sw
x
w:vwE
vw
x
w:wtE
wt
 1
 0, v  V \ s, t
1
最短路問題の制約!
xe  0, e  E
0以下のものを目的関数に加えて,さらに制約条件を外した->最適値以下(下界)
Lagrange緩和問題の導出(2)
(時間制約を緩和した)Lagrange緩和問題
殿様からもらえる
制限時間分のカンパ
1時間をλ(両)と変換した費用
L( )  最小化  (cvw  Tvw ) xvw  Tmax
条件 
 xwv 
w:wvE
x
w:swE
vwE
sw
x
w:vwE
vw
x
w:wtE
wt
 1
 0, v V \ s, t
1
xe  0, e  E
最短路問題の制約!
Lagrange双対問題(なるべく良い下界を出そう!)
Lagrage双対問題
下界  最大化 L( )
 0
L(λ)
9+16λ
パスがすべてわから
ないとこんな図は書
けない!
23
実際にはすべてのパ
スを列挙することは難
しい!(数が多いか
ら)
11+4λ
16
16
15
11
9
0
23-8λ
1
2
λ
どうやってL(λ)の最大値を求めるの?
劣勾配法(現在の傾き(劣勾配)だけを頼りに山を登
る!)
9+16λ
L(λ)
現在地点 λ=0
最短路を解くとs->2->1->t
傾き(劣勾配)は16λ
右方向が頂上だ!
λ
どうやってL(λ)の最大値を求めるの?(2)
右にステップサイズ(歩幅) 1/8でジャンプ!
L(λ)
現在地点 λ=2 (=0+1/8×16)
最短路を解くとs->2->3->t
傾きは-8λ
左方向が頂上だ!
23-8λ
2
λ
どうやってL(λ)の最大値を求めるの?(2)
今度は左にステップサイズ1/8でジャンプ!
L(λ)
現在地点 λ=1 (=2+1/8×(-8))
最短路を解くとs->1->tと
s->1->2->3->tの2本がある.
傾きはそれぞれ4λと-8λだから,
ここが頂上だ!
11+4λ
最良の下界は15 (=11+4=23-8)
でも,最適値は16!
23-8λ
1
λ
ステップサイズ(歩幅)の選び方
L(λ)
9+16λ
小さすぎると登り切らず
23
に止まってしまう!
大きすぎると頂上を
飛び越して振動してしまう!
11+4λ
16
16
15
11
9
0
23-8λ
1
最初は大きく,段々と小さくしていく方法が良い.
2
λ