ネットワーク理論講義補助資料
Text.
組合せ最適化とアルゴリズム
4.5 節 主・双対法
pp. 132-141


副読本:組合せ最適化短編集(朝倉書店)第1
章:マッチング問題に対する主・双対法のお話が
ある.
ここでは,主・双対法を点被覆問題を例として解
説する.
4.5節
主・双対法
1
問題
点の上に警備員(1人1万円)を配置して,すべての
道(グラフでは枝)をなるべく安く見張ろう!
1
クレオパトラ
5
2
3
シェイクスピア
ベートーベン
モナリザ
ニュートン
4.5節
4
ラスプーチン
主・双対法
ゴッホ
6
2
点の被覆(cover)
1
5
2
3
6
4
警備員が点3にたつと点線の道の見張りができる(枝が被覆される).
4.5節
主・双対法
3
グラフによる問題の記述



無向グラフ G=(V,E)
点上の重み関数 w(警備員の雇用費):以
下では簡単のためwv=1(万円)とする.
目的:点の部分集合 S ですべての枝 E を
被覆するものの中で,S内の点の重みの合
計を最小にするものを求める.
NP-困難->近似解法を設計しよう!
4.5節
主・双対法
4
整数計画としての定式化と線形
計画緩和問題

(変数) xv :点v上に警備員を配置する 1,
しない0
最小化  xv
整数計画問題
vV
条件 xv  xw  1 vw  E
xv  0,1 v  V
線形計画問題に緩和
0  xv v V
4.5節
主・双対法
5
双対問題の導出(Lagrange緩和
を用いる方法)(1)
最小化  xv
vV
条件 xv  xw  1 vw  E
0  xv v  V
1  xv  xw ( 0) vwV
実行可能解なら必ず 0以下
非負のLagrange乗数yvwを乗じて目的関数に加える!
4.5節
主・双対法
6
双対問題の導出(Lagrange緩和
を用いる方法)(2)
最小化  xv 
vV
 (1  x
vwE
v
 xw ) yvw
0以下の値
条件 xv  xw  1 vw  E
0  xv v  V
緩和(式を外す)と実行可能領域が広がるので,
目的関数値は良くなる!
下界になる!
4.5節
主・双対法
7
双対問題の導出(Lagrange緩和
を用いる方法)(3)
目的関数をxについて整理


最小化  1   ye  xv   yvw
vV 
e ( v ) 
vwE
点vに接続している
枝の集合
条件 0  xv v V
下界が-∞にならないためには,xの係数がすべて0以上!
欲しいのは最良(最も大きな)下界->目的関数を最大化!
4.5節
主・双対法
8
双対問題の導出(Lagrange緩和
を用いる方法)(4)
双対問題のできあがり!
最大化  yvw
vwE
条件 y


e ( v )
e
 1 v  V 0  ye e  E
双対変数の解釈:枝(道) e に置いておく警備員へのご褒美 ye
相補性条件を導こう!(忘れた人はテキスト p.47参照)
4.5節
主・双対法
9
相補性条件(主と双対の関係
式)
(最適解においては)双対定理より主問題と双対問題の最適値は一致!
 xv 
vV
 (1  x
vwE
v
 xw ) yvw
Lagrange緩和による
導出の途中の式


  1   ye  xv   yvw
vV 
e ( v ) 
vwE
最適なx,yにおいては,必ず0になる!
xv>0 
ye  0  xv  xw  1 4.5節
主・双対法
y


e ( v )
e
1
10
相補性条件の解釈
主相補性条件
xv>0 
y


e ( v )
e
1
点vに警備員が立つ->
住民は合計1万円を支払う
双対相補性条件
道(枝)の住民がお金を支払う->
ye  0  xv  xw  1 道の両端のいずれかに警備員が立つ
上の2条件を満たしていれば(主も双対も)最適!
主・双対法のアイディア:
主相補性条件は常に満たしたまま,双対問題の目的関数値を
改善(大きくする).(双対相補性条件は満たさない可能性あ
11
4.5節
主・双対法
り!)
主・双対法(基本形)
1. 警備員なし(xv=0),ご褒美なし(ye=0)から出発
(主相補性は必ず満たす!)
2. 被覆されていない枝e=(v,w)を選択
xv  xw  0 3. 双対変数yvwを
 ye  1 または
e ( v )
y


e ( w)
e
 1 を満たすまで増やす(等号になった点をvとする).
4. 点vに警備員を立てて(立てても主相補性条件は常に
満たすことに注意),2.へ
4.5節
主・双対法
12
主・双対法のスナップショット(1)
1
5
2
枝(2,3)を選択.点2もしくは
3に警備員が立つまで
ご褒美(y23)を増やす.1万円
を配置.
4.5節
3
4
主・双対法
6
13
主・双対法のスナップショット(2)
1
5
2
3
枝(2,3)に1万円のご褒美
があるので点2にも警備員が
公募してくる!
6
4
4.5節
主・双対法
14
主・双対法のスナップショット(3)
1
5
2
警備されていない枝(5,6)の
住民が道(5,6)上に1万円配置.
Y56=1と設定.
点5上に警備員が配置される.
4.5節
3
4
主・双対法
6
15
主・双対法のスナップショット(4)
1
5
点6にも警備員が公募してくる.
すべての枝が被覆されたので
終了.答え(主・双対法による
近似解)は4人.
2
双対問題の実行可能解y23 =y56=1より,
下界は2.よって2倍以下の保証をもつ!
4.5節
3
4
主・双対法
6
16
主・双対法
(一様増加<公平にご褒美を払おう>,
逆削除ステップつき<無駄な警備員はクビにしよう!>)
1. 警備員なし(xv=0),ご褒美なし(ye=0)から出発
2. 被覆されていない枝eの集合 Violated を求める.
3. Violated内の枝e(=vw)の双対変数yeを
 ye  1 または
e ( v )
y


e ( w)
e
 1 を満たすまで一様に増やす(等号になった点をvとする).
4. 点vに警備員を立てて,2.へ
5. xvを1にした(警備員を立たせた)逆順に,除いても
実行可能(すべての枝が被覆されている)なら警備員を削除.
->逆削除ステップ:基本形の例だと,点5の警備員をクビにする!
4.5節
主・双対法
17
逆削除ステップ付き一様増加
1
1
4
2
すべての枝がViolated;
点3に警備員が立つまで
一様にyを増加.
4.5節
1
4
1
4
1
4
4
主・双対法
1
4
3
5
1
4
1
4
1
4
6
18
逆削除ステップ付き一様増加
1
3
8
2
枝(1,2),枝(2,4),枝(4,6),
枝(5,8)がViolated;
点2に警備員が立つまで,
Violated内のyを一様に1/8
だけ増やす.
4.5節
3
8
1
4
1
4
4
主・双対法
1
4
3
5
3
8
1
4
3
8
6
19
逆削除ステップ付き一様増加
1
3
8
2
枝(4,6),枝(5,6)がViolated;
点6に警備員が立つまで,
Violated内のyを一様に1/8
だけ増やす.近似解は3人.
3
8
1
4
4
下界(yの値の合計)は2.75.
4.5節
1
4
1
4
主・双対法
3
5
1
2
1
4
1
2
6
20
ダウンロード

PowerPoint - LOG OPT HOME