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

ネットワーク理論講義補助資料
Text.
組合せ最適化とアルゴリズム
4.3 節 Lagrange緩和
pp. 115-123


Lagrange緩和は，2.3.3 節（pp.44-48) で線形計
画の双対問題を導出するときに用いた．
ここでは，時間制約付きの最短路問題に対する
Lagrange緩和の適用を例に，Lagrange緩和の
一般論について解説
大名の例題
１２時間以内に氷を献上せよ！
10,1
s
始点
5,10
1
1,15
t
終点
6,1
3,3 2,1
飛脚に払う費用
と移動時間
2
5,1
3
Lagrange緩和のアイディア
制約の時間を費用に換算！（１時間＝２両）
１０両＋１時間×２（両/時間）
12
s
1
31
8
9 4
25
2
t
7
3
１時間＝２両
変換された費用に対する最短路 s->1->2->3->t （最適値は31）
（本当の）費用＝23両，時間＝4時間 ->12時間以内だけど高い！
Lagrange緩和のアイディア
制約の時間を費用に換算（１時間＝１両）
11
s
1
16
7
6 3
15
2
t
6
3
１時間＝１両
新しい最短路 s->1->t （最適値は27）
（本当の）費用＝11両，時間＝16時間 ->12時間を超えてしまった！
１時間＝？両にすれば良い？
数学者なら変数を導入！１時間＝λ（ラムダと読む）両とする．
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緩和問題の導出（１）
（絶対に失敗しない方法）
時間制約を満たしていれば
必ず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緩和問題の導出（２）
（時間制約を緩和した）Lagrange緩和問題
殿様からもらえる
制限時間分のカンパ
１時間をλ（両）と変換した費用
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
λ

Download Report