情報数理学

１４．プライマルデュアル法
1
線形計画法の双対の概念を応用した近似アルゴリズム
がある。プライマルデュアル法（主双対法）という。
１４．１ＬＰ双対性入門
まず、次のような線形計画問題を考える。
問題Ａ（主問題）
目的関数
min
f (x ) = 7x 1 + x 2 + 5x 3
制約条件
x 1 - x 2 + 3x 3 ³ 10 L（１）
5x 1 + 2x 2 - x 3 ³ 6 L（２）
x 1, x 2 , x 3 ³ 0
2
問題Ａのような形をＬＰの標準形という。
制約条件を満たす解を、実行可能解という。
例えば、
x = (2, 1, 3)
は実行可能解。
実際、
1g2 - 1g1 + 3g3 = 10 ³ 10
5g2 + 2g1 - 1g3 = 9 ³ 6
L（１）
L（１）
このとき、目的関数値は、
f (x ) = 7g2 + 1g1 + 5g3 = 30
3
最適値は実行関数値以下であるので、この場合３０以下になる。
このことは実行可能関数値は、最適値の上界を与えているとみ
なせる。
f (x )
最適値
実行可能解
ここで、下界について考える。
係数から、（１）式と（２）式の和をとると、目的関数値
の下界を導くことができる。
4
f (x ) = 7x 1 + x 2 + 5x 3
³ 6x 1 + x 2 + 2x 3
= (x 1 - x 2 + 3x 3 ) + (5x 1 + 2x 2 - x 3 )
³ 10 + 6 = 16
x3
\ f (x ) ³ 16
このように、制約式に非負数を乗じて加えると、目的関数の
下界が得られる。この非負数に注目してもう一つのＬＰ問題を
得ることができる。下解はできるだけ大きくするほうが良いこと
に注意うする。
5
問題Ｂ（双対問題）
目的関数
max
制約条件
f * (y ) = 10y1 + 6y 2
y1 + 5y 2 £ 7
L（１）
*
- y1 + 2y 2 £ 1 L（ 2）
*
3y1 - y 2 £ 5 L（ 3）
y1, y 2 ³ 0
*
制約式の不等号の向きが変化しないように、
非負の条件が必要である。
6
このようにして得られたＬＰ問題を、元の問題に対する
双対問題（dual,デュアル）という。
双対問題に対して、元の問題を主問題（primal,プライマル)
という。
0
双対可能解
f (x )
最適値
実行可能解
7
双対関係
問題Ａ（主問題）
目的関数
min
f (x ) =
問題Ｂ（双対問題）
目的関数
n
å
cj x j
max
f * (y ) =
j= 1
制約条件
n
m
aij x j ³ bi
(i = 1, L , m )
j=1
å
bi y i
i= 1
制約条件
å
m
å
aij y i £ c j
( j = 1, L , n )
i= 1
xj ³ 0
( j = 1, L , n )
yj ³ 0
(i = 1, L , m )
双対問題の双対問題は、主問題になる。
8
弱双対定理
弱双対定理
x = (x 1 , L , x n ) と y = (y 1 , L , y m ) がそれぞれ、
主問題と双対問題の実行可能解のとき、次式が成り立つ。
f (x ) ³ f (y )
*
n
\
å
j= 1
m
cj x j ³
å
bi y i
i= 1
9
双対定理
双対定理
x * = (x *1, L , x *n ) とy * = (y *1, L , y *m ) をそれぞれ、
主問題と双対問題の最適解のとき、次式が成り立つ。
*
*
*
f (x ) = f (y )
n
\
å
m
cj x
*
j= 1
j
=
å
bi y
*
i
i= 1
f (x )
0
双対可能解
最適値
実行可能解
10
相補条件
相補条件
x = (x 1 , L , x n ) と y = (y 1 , L , y m ) がそれぞれ、
主問題と双対問題の実行可能解のとき、次式が成り立つ。
このとき、 x と y が最適解であるための必要十分条件は、
以下の条件が成立することである。
（１）主相補条件：各 1 £ j £ n に対して、
m
x j = 0 あるいは
å
aij y i = c j
である。
i= 1
（２）双対相補条件：各 1 £ i £ m に対して、
n
yj = 0
あるいは
å
aij x j = bi
である。
j= 1
11
１４．２プライマルデュアル法
相補条件を緩和することにより、近似アルゴリズムが得られる。
緩和相補条件
（１）主相補条件： a ³ 1 とする。
各 1 £ j £ n に対して、 x j = 0 あるいは
1
cj £
a
m
å
である。
aij y i £ c j
i= 1
（２）双対相補条件： b ³ 1 とする。
各 1 £ i £ m に対して、 y j = 0
あるいは
n
bi £
å
aij x j £ b gbi
である。
j=1
12
プライマルデュアル法の近似率
近似率
緩和した相補条件を共に満足するとき、
以下が成り立つ。
n
å
m
c j x j £ (a gb )å bi y i
j= 1
i= 1
\ f * (y ) £ f (x ) £ (a gb ) f * (y )
よって、 a gb
近似アルゴリズムである。
13
１４．３集合カバー
ある集合 U = {e1, L , en } （台集合という）と、その部分集合からなる
族 S== {S 1, S 2 , L , S m }, S i Í Uが与えられたとき、族の中のいくつかの
集合を選んで、その和集合が台集合をふくむようにする。さらに、こ
の族の各要素には、コストが割り当てられている。このとき、次の式
を満たすような部分族 C=でコスト最小のものを求める。
C=
= {S p , L , S q } Í S ,U Í
Ｕ
US
k
Sk Î C
5
S1 4
S2 １
２
３ S
3
1
５
６
3
４
S5
C=は、台集
合 U をカバー
するという。
S4 2
14
集合カバーの難しさ
集合カバー問題は、ＮＰ完全である。
証明略
15
集合カバーの整数計画法による定式化
コスト関数を c : S=® ¤ + とする。
目的関数
min
f (x ) =
c(S )x S
SÎ S
制約条件
å
å
xS ³ 1
(e Î U )
S :e Î S
xS Î {0,1}
(S Î S )
線形緩和
16
集合カバーの緩和線形計画法
目的関数
min
f (x ) =
c(S )x S
SÎ S
制約条件
å
å
xS ³ 1
(e Î U )
標準形になっ
ている。
少数集合カ
バー
S :e Î S
xS ³ 0
(S Î S )
双対問題
17
少数集合カバーの双対問題
目的関数
max
*
f (y ) =
å
ye
eÎ U
制約条件
å
ye £ c(S )
(S Î S )
eÎ U
ye ³ 0
(e Î U )
各要素eに対応する”物
質”を、集合Sに詰め込
むことをイメージすると
よい。直感的に、各集合
Sには、ある一定以上の
物質を詰め込むことが
できない。（この条件を、
破ることを、オーバー
パックということがあ
る。）
18
関数値の関係
少数最適値
整数最適値
OPT f OPT
f (x )
0
整数主実行可能解
少数双対可能解
少数主実行可能解
19
１４．４集合カバーへのプライマル
デュアル法の適用
（１）主相補条件：全てのS Î S
xS ¹ 0
Þ
å
に対して、
ye = c(S )
e:e Î S
主相補条件は、
厳密解の条件。
\ a = 1
（２）双対相補条件：
S Î S に対して、要素 e Î U 頻度の最大値を
k
とする。このとき、
双対相補条件
全ての e Î U に対して、
が、緩和されて
いる。
ye ¹ 0
Þ
å
S :e Î S
x S £ 1gk
\ b = k
20
相補条件の利用
集合Sは、
å
ye = c(S )
e:e Î S
を満たすとき、タイトと呼ばれる。
主問題の変数は整数性を保ちながら更新する。
しかも、タイトな集合のみから集合を集合カバーに選ぶ。
双対変数の値が非零要素のみ、
でカバーされる。
k
個までの集合
21
アルゴリズム
集合カバー（近似率 k ）
１．（初期化）
x ¬ 0 ;y ¬ 0 ;
２．すべての要素がカバーされるまで以下を繰り返す。
２．１：カバーされていない要素を１つ選びe とし、
e を含むどれかの集合がタイトになるまで y e の
値を増加する；
２．２：タイトな集合をすべてカバーに選んで、
x を更新する；
２．３：これらの集合に含まれている要素は、カ
バーされているとする。
３．集合カバーとしてx を出力する。
22
アルゴリズムの動作例１
Ｕ
x = (S 1, S 2 , S 3 , S 4 , S 5 )
y = (e1, e2 , e3 , e4 , e5 , e5 )
5
S1 4
S2 １
２
3
４
U
５
S5
x = (0, 0, 0, 0, 0)
３ S
3
1
６
y = (0, 0, 0, 0, 0, 0)
S4 2
e 1 選択
y 1 の増加
1
5
S1 １
２
k = 3
x = (0,1, 0, 0, 0)
S5
３ S
3
1
６
S4 2
y = (3, 0, 0, 0, 0, 0)
23
U1
5
S1 １
S 5 x = (0, 1, 0, 0, 0)
y = (3, 0, 0, 0, 0, 0)
２
３ S
3
1
６
S4 2
e 2 選択
y 2 の増加
U2
４
S 5 x = (1, 1, 0, 0, 0)
y = (3, 1, 0, 0, 0, 0)
S3
1
６
S4 2
24
U2
４
S 5 x = (1, 1, 0, 0, 0)
y = (3, 1, 0, 0, 0, 0)
S3
1
６
U3
S4 2
e 6 選択
y 6 の増加
x = (1, 1, 1, 0, 0)
y = (3, 1, 0, 0, 0, 1)
25
解
Ｕ
S1 4
S2 １
２
3
４
５
３ S
3
1
x = (1, 1, 1, 0, 0)
y = (3, 1, 0, 0, 0, 1)
６
f (x ) = 4 + 3 + 1 = 8
f * (y ) = 3g(3 + 1 + 1) = 15
26
アルゴリズムの動作例２
U
k = 3
5
S1 4
S2 １
２
3
４
５
S5
x = (0, 0, 0, 0, 0)
３ S
3
1
６
y = (0, 0, 0, 0, 0, 0)
S4 2
e 5 選択
y 5 の増加
U1
3
S1 4
S2 １
２
１
x = (0, 0, 0, 1, 0)
S5
y = (0, 0, 0, 0, 2, 0)
３ S
3
1
４
27
U1
3
S1 4
S2 １
２
１
S 5 x = (0, 0, 0, 1, 0)
３ S
3
1
y = (0, 0, 0, 0, 2, 0)
４
e 3 選択
y 3 の増加
U
2
2
S1 3
S2 １
２
１
S5
x = (0, 0, 1, 1, 0)
y = (0, 0, 1, 0, 2, 0)
４
28
U2
2
S1 3
S2 １
２
１
S5
x = (0, 0, 1, 1, 0)
y = (0, 0, 1, 0, 2, 0)
４
e 2 選択
y 2 の増加
U
3
S1 1
x = (0, 0, 1, 1, 1)
S2 １
y = (0, 2, 1, 0, 2, 0)
１
４
29
U3
S1 1
x = (0, 0, 1, 1, 1)
S2 １
y = (0, 2, 1, 0, 2, 0)
１
４
U4
e 4 選択
y 4 の増加
x = (0, 1, 1, 1, 1)
y = (0, 2, 1, 1, 2, 0)
30
解
U
5
S2 １
２
3
４
５
S5
３ S
3
1
６
x = (0, 1, 1, 1, 1)
y = (0, 2, 1, 1, 2, 0)
S4 2
f (x ) = 3 + 1 + 2 + 5 = 11
f * (y ) = 3g(2 + 1 + 1 + 2) = 18
31
近似率
相補条件より、直ちに以下のように求められる。
ìï a = 1
ï
í
ïï b = k (頻度）
ïî
n
å
j=1
m
c j x j £ (a gb )å bi y i
i= 1
\ f * (y ) £ f (x ) £ kf * (y )
よって、k-近似アルゴリズムである。
32
関数値の関係
少数最適値
少数双対可能解
少数主実行可能解
整数最適値
0
整数主実行可能解
f (x )
OPT f OPT
緩和少数双対可能解
k gOPT f
アルゴリズムでは、相補条件より
この範囲に含まれる整数解が得られる。33
アルゴリズムの正当性
アルゴリズムでは、
の更新は整数性を満たしている。
しかも、以下の２つを満足している。
○すべての要素がカバーされている。
○すべての集合が、オーバーパックされていない。
（タイトな集合を選んでいくので自動的に満足する。）
以上より、アルゴリズムは、集合カバーに対する
整数の実行可能解を出力する。
34
最悪の問題例
U
１
e1
１
e2
L
en
１
en - 1
1+ e
en + 1
最適値
1+ e
アルゴリズムの出力
（
を最初に選ぶ）
n+ e
35

Download Report