ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp

Presentation on theme: "ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp"— Presentation transcript:

1 ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp. 115-123
ここでは，時間制約付きの最短路問題に対する Lagrange緩和の適用を例に，Lagrange緩和の一般論について解説

2 大名の例題 １２時間以内に氷を献上せよ！ 終点 始点 飛脚に払う費用 と移動時間

3 Lagrange緩和のアイディア 制約の時間を費用に換算！ （１時間＝２両）
１０両＋１時間×２（両/時間） 変換された費用に対する最短路 s->1->2->3->t （最適値は31） （本当の）費用＝23両，時間＝4時間　->12時間以内だけど高い！

4 Lagrange緩和のアイディア 制約の時間を費用に換算（１時間＝１両）
新しい最短路 s->1->t　（最適値は27） （本当の）費用＝11両，時間＝16時間　->12時間を超えてしまった！

5 １時間＝？両にすれば良い？ 1 t s 2 3 数学者なら変数を導入！ １時間＝λ（ラムダと読む）両とする． 1+15λ 10+λ 3＋3λ
殿様が12時間にもってこいと言っている のだから，12×λ（両）は負担する． 1 t 10+λ 3＋3λ s 2＋λ 6＋λ [λを色々変えたときの最適パス の費用－殿様からのカンパ]はどんな関数？ 2 3 5+10λ 5+λ s->1->t: 　 (10+1)+(1+15)λ-12λ=11+4λ s->1->2->3->t: ( )+( )λ-12λ= 23-8λ s->2->1->t: =[ ] s->2->3->t: =[ ]

6 L(λ)：一番安いパスを選択することによって得られる関数（区分的に線形な凹関数）

7 L(λ）が下界を与えることを示そう！ （時間）制約付き最短路問題の定式化（0-1整数計画） 最短路の条件 枝vwの移動時間Tvw
注：数値を入れた具体的な導出はテキスト参照 最短路の条件 枝vwの移動時間Tvw 制限時間 Tmax 制約付き最短路の 場合は0,1条件が必要！

8 線形計画に緩和（0-1条件をとる！） （時間）制約付き最短路問題の線形計画緩和 時間制約条件 をLagrange緩和 （式に定数を乗じて
目的関数に加える）

9 Lagrange緩和問題の導出（１） （絶対に失敗しない方法）
時間制約を満たしていれば 必ず0以下 非負のLagrange乗数λ 最短路問題の制約！ 0以下のものを目的関数に加えて，さらに制約条件を外した->最適値以下（下界）

10 Lagrange緩和問題の導出（２） 殿様からもらえる （時間制約を緩和した）Lagrange緩和問題 制限時間分のカンパ
１時間をλ（両）と変換した費用 最短路問題の制約！

11 Lagrange双対問題（なるべく良い下界を出そう！）
Lagrage双対問題 パスがすべてわからないとこんな図は書けない！ 実際にはすべてのパスを列挙することは難しい！（数が多いから）

12 どうやってL(λ）の最大値を求めるの？ 劣勾配法（現在の傾き（劣勾配）だけを頼りに山を登る！）
9+16λ L(λ） 現在地点 λ=0 最短路を解くとs->2->1->t 傾き（劣勾配）は16λ 右方向が頂上だ！ λ

13 どうやってL(λ）の最大値を求めるの？(2) 右にステップサイズ（歩幅） 1/8でジャンプ！
現在地点 λ=2 (=0+1/8×16) 最短路を解くとs->2->3->t 傾きは－8λ 左方向が頂上だ！ 23－8λ λ 2

14 どうやってL(λ）の最大値を求めるの？(2) 今度は左にステップサイズ1/8でジャンプ！
現在地点 λ=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

15 ステップサイズ（歩幅）の選び方 小さすぎると登り切らず に止まってしまう！ 大きすぎると頂上を 飛び越して振動してしまう！
最初は大きく，段々と小さくしていく方法が良い．