Presentation is loading. Please wait.

Presentation is loading. Please wait.

ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp

Similar presentations


Presentation on theme: "ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp"— Presentation transcript:

1 ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp. 132-141
副読本:組合せ最適化短編集(朝倉書店)第1章:マッチング問題に対する主・双対法のお話がある. ここでは,主・双対法を点被覆問題を例として解説する. 4.5節 主・双対法

2 問題 点の上に警備員(1人1万円)を配置して,すべての 道(グラフでは枝)をなるべく安く見張ろう! 4.5節 主・双対法

3 点の被覆(cover) 警備員が点3にたつと点線の道の見張りができる(枝が被覆される). 4.5節 主・双対法

4 グラフによる問題の記述 無向グラフ G=(V,E) 点上の重み関数 w(警備員の雇用費):以下では簡単のためwv=1(万円)とする.
目的:点の部分集合 S ですべての枝 E を被覆するものの中で,S内の点の重みの合計を最小にするものを求める. NP-困難->近似解法を設計しよう! 4.5節 主・双対法

5 整数計画としての定式化と線形計画緩和問題
(変数) xv :点v上に警備員を配置する 1,しない0 整数計画問題 線形計画問題に緩和 4.5節 主・双対法

6 双対問題の導出(Lagrange緩和を用いる方法)(1)
実行可能解なら必ず 0以下 非負のLagrange乗数yvwを乗じて目的関数に加える! 4.5節 主・双対法

7 双対問題の導出(Lagrange緩和を用いる方法)(2)
0以下の値 緩和(式を外す)と実行可能領域が広がるので, 目的関数値は良くなる! 下界になる! 4.5節 主・双対法

8 双対問題の導出(Lagrange緩和を用いる方法)(3)
点vに接続している 枝の集合 目的関数をxについて整理 下界が-∞にならないためには,xの係数がすべて0以上! 欲しいのは最良(最も大きな)下界->目的関数を最大化! 4.5節 主・双対法

9 双対問題の導出(Lagrange緩和を用いる方法)(4)
双対問題のできあがり! 双対変数の解釈:枝(道) e に置いておく警備員へのご褒美 ye 相補性条件を導こう!(忘れた人はテキスト p.47参照) 4.5節 主・双対法

10 相補性条件(主と双対の関係式) (最適解においては)双対定理より主問題と双対問題の最適値は一致! Lagrange緩和による 導出の途中の式
最適なx,yにおいては,必ず0になる! 4.5節 主・双対法

11 相補性条件の解釈 主相補性条件 点vに警備員が立つ-> 住民は合計1万円を支払う 双対相補性条件
道(枝)の住民がお金を支払う-> 道の両端のいずれかに警備員が立つ 上の2条件を満たしていれば(主も双対も)最適! 主・双対法のアイディア: 主相補性条件は常に満たしたまま,双対問題の目的関数値を改善(大きくする).(双対相補性条件は満たさない可能性あり!) 4.5節 主・双対法

12 主・双対法(基本形) 警備員なし(xv=0),ご褒美なし(ye=0)から出発 (主相補性は必ず満たす!)
被覆されていない枝e=(v,w)を選択 双対変数yvwを を満たすまで増やす(等号になった点をvとする). 点vに警備員を立てて(立てても主相補性条件は常に 満たすことに注意),2.へ 4.5節 主・双対法

13 主・双対法のスナップショット(1) 枝(2,3)を選択.点2もしくは 3に警備員が立つまで ご褒美(y23)を増やす.1万円 を配置.
4.5節 主・双対法

14 主・双対法のスナップショット(2) 枝(2,3)に1万円のご褒美 があるので点2にも警備員が 公募してくる! 4.5節 主・双対法

15 主・双対法のスナップショット(3) 警備されていない枝(5,6)の 住民が道(5,6)上に1万円配置. Y56=1と設定.
点5上に警備員が配置される. 4.5節 主・双対法

16 主・双対法のスナップショット(4) 点6にも警備員が公募してくる. すべての枝が被覆されたので 終了.答え(主・双対法による
近似解)は4人. 双対問題の実行可能解y23 =y56=1より, 下界は2.よって2倍以下の保証をもつ! 4.5節 主・双対法

17 主・双対法 (一様増加<公平にご褒美を払おう>, 逆削除ステップつき<無駄な警備員はクビにしよう!>)
主・双対法 (一様増加<公平にご褒美を払おう>, 逆削除ステップつき<無駄な警備員はクビにしよう!>) 警備員なし(xv=0),ご褒美なし(ye=0)から出発 被覆されていない枝eの集合 Violated を求める. Violated内の枝e(=vw)の双対変数yeを を満たすまで一様に増やす(等号になった点をvとする). 点vに警備員を立てて,2.へ xvを1にした(警備員を立たせた)逆順に,除いても 実行可能(すべての枝が被覆されている)なら警備員を削除. ->逆削除ステップ:基本形の例だと,点5の警備員をクビにする! 4.5節 主・双対法

18 逆削除ステップ付き一様増加 すべての枝がViolated; 点3に警備員が立つまで 一様にyを増加. 4.5節 主・双対法

19 逆削除ステップ付き一様増加 枝(1,2),枝(2,4),枝(4,6), 枝(5,8)がViolated; 点2に警備員が立つまで,
Violated内のyを一様に1/8 だけ増やす. 4.5節 主・双対法

20 逆削除ステップ付き一様増加 枝(4,6),枝(5,6)がViolated; 点6に警備員が立つまで, Violated内のyを一様に1/8
4.5節 主・双対法


Download ppt "ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp"

Similar presentations


Ads by Google