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

問題 点の上に警備員（１人１万円）を配置して，すべての 道（グラフでは枝）をなるべく安く見張ろう！ ４．５節 主・双対法

点の被覆（cover） 警備員が点３にたつと点線の道の見張りができる（枝が被覆される）． ４．５節 主・双対法

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

整数計画としての定式化と線形計画緩和問題 （変数） xv ：点v上に警備員を配置する 1，しない0 整数計画問題 線形計画問題に緩和 ４．５節 主・双対法

双対問題の導出（Lagrange緩和を用いる方法）（１） 実行可能解なら必ず 0以下 非負のLagrange乗数yvwを乗じて目的関数に加える！ ４．５節 主・双対法

双対問題の導出（Lagrange緩和を用いる方法）（２） ０以下の値 緩和（式を外す）と実行可能領域が広がるので， 目的関数値は良くなる！ 下界になる！ ４．５節 主・双対法

双対問題の導出（Lagrange緩和を用いる方法）（３） 点vに接続している 枝の集合 目的関数をxについて整理 下界が－∞にならないためには，xの係数がすべて0以上！ 欲しいのは最良（最も大きな）下界->目的関数を最大化！ ４．５節 主・双対法

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

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

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

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

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

主・双対法のスナップショット（２） 枝(2,3)に１万円のご褒美 があるので点２にも警備員が 公募してくる！ ４．５節 主・双対法

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

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

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

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

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

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