印刷用スライド - 電気通信大学

今日の目標
今日の目標
離散最適化基礎論第 10 回
完全双対整数性：全域木 (2)
最小費用全域木問題の持つ完全双対整数性を理解する
岡本吉央
[email protected]
I
前回は準備
I
今回，証明
電気通信大学
2014 年 12 月 19 日
最終更新：2014 年 12 月 24 日
岡本吉央 (電通大)
13:20
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
1 / 46
最小費用全域木問題：第 4 の定式化
離散最適化基礎論 (10)
2014 年 12 月 19 日
2 / 46
2014 年 12 月 19 日
4 / 46
最小費用全域木問題：第 4 の定式化
目次
木
無向グラフ G = (V , E )
1
木とは？
最小費用全域木問題：第 4 の定式化
G が木であるとは，次の 2 つの条件を満たすこと
2
Kruskal のアルゴリズム
3
最小費用全域木問題と完全双対整数性：証明
I
G は連結である
I
G は閉路を部分グラフとして含まない
e
b
a
4
f
d
c
今日のまとめ
i
j
l
k
h
g
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
3 / 46
最小費用全域木問題：第 4 の定式化
離散最適化基礎論 (10)
最小費用全域木問題：第 4 の定式化
グラフの全域木
最小費用全域木問題
無向グラフ G = (V , E )
最小費用全域木問題とは？
全域木とは？
I
入力：無向グラフ G = (V , E )，非負辺費用関数 c : E → R
G の全域木とは，G の部分グラフで次を満たすもの
I
出力：G の全域木で，費用が最小のもの
I
木である
I
頂点集合が V である
全張木，生成木とも呼ぶことがある
4
v1
e
b
a
i
j
l
k
2
2
v8
5
3
1
v7
事実
h
g
v6
1
v5
v3
d
4
v4
2
1
f
c
岡本吉央 (電通大)
3
5
I
v2
2
最小費用全域木問題は効率よく解くことができる (Kruskal ’56, Prim ’57)
離散最適化基礎論 (10)
G が非連結であるとき，G の全域木は存在しない
効率よく = |V | と |E | に関する多項式時間で
2014 年 12 月 19 日
岡本吉央 (電通大)
5 / 46
最小費用全域木問題：第 4 の定式化
離散最適化基礎論 (10)
2014 年 12 月 19 日
6 / 46
最小費用全域木問題：第 4 の定式化
全域木の性質
用いる観察
木であるための必要十分条件
無向グラフ G = (V , E )
無向グラフ G = (V , E ) に対して，次の 3 つは同値
観察
1
G は閉路を含まない，かつ，G は連結である (つまり，G は木である)
2
G は閉路を含まない，かつ，|E | = |V | − 1 である
3
G は連結である，かつ，|E | = |V | − 1 である
I
定式化 1 は
1
に基づいている
I
定式化 2 は
2
に基づいて行う
I
定式化 3 は
3
に基づいて行う
I
定式化 4 は
2
に基づいて行うが，1 つ観察を用いる
(証明は演習問題)
|E | ≥ |V | ⇒ G は閉路を含む
証明は『数理解析』又は『グラフとネットワーク』を参照
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
7 / 46
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
8 / 46
最小費用全域木問題：第 4 の定式化
最小費用全域木問題：第 4 の定式化
補題
補題：証明の続き
補題
補題
無向グラフ G = (V , E ) に対して，次の 2 つは同値
2
4
無向グラフ G = (V , E ) に対して，次の 2 つは同値
G は閉路を含まない，かつ，|E | = |V | − 1 である
2
|E (S)| ≤ |S| − 1 がすべての S ⊆ V (S 6= ∅, V ) に対して成り立つ，
かつ，|E | = |V | − 1 である
4
G は閉路を含まない，かつ，|E | = |V | − 1 である
|E (S)| ≤ |S| − 1 がすべての S ⊆ V (S 6= ∅, V ) に対して成り立つ，
かつ，|E | = |V | − 1 である
ただし，E (S) は S に両端点を持つ G の辺全体の集合
ただし，E (S) は S に両端点を持つ G の辺全体の集合
証明：G において，|E | = |V | − 1 が成り立つと仮定する
証明：G において，|E | = |V | − 1 が成り立つと仮定する
I
I
I
I
I
G が閉路を含むと仮定する (その閉路を C とする)
C の頂点集合を S とすると，S 6= ∅
このとき，|E (S)| ≥ C の辺数 = |S|
一方，|E (V )| = |E | = |V | − 1 < |V | なので，S 6= V
したがって，ある S ⊆ V (ただし，S 6= ∅, V ) に対して，
|E (S)| > |S| − 1
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
I
G が閉路を含まないと仮定する
I
このとき，G の部分グラフも閉路を含まない
I
したがって，任意の S ⊆ V (S 6= ∅, V ) に対して，
部分グラフ G [S] = (S, E (S)) を考えると，G [S] も閉路を含まない
I
∴ |E (S)| ≤ |S| − 1
岡本吉央 (電通大)
9 / 46
最小費用全域木問題：第 4 の定式化
離散最適化基礎論 (10)
2014 年 12 月 19 日
最小費用全域木問題：第 4 の定式化
最小費用全域木問題：定式化 4
最小費用全域木問題：定式化 4
最小費用全域木問題：01 整数計画問題としての定式化 4
最小費用全域木問題：01 整数計画問題としての定式化 4
x ∈ RE は変数
x ∈ RE は変数
∑
minimize
∑
minimize
c(e)xe
subject to
xe ≤ |S| − 1
(∀ S ⊆ V , (S 6= ∅, V )),
∑
subject to
xe ≤ |S| − 1
(∀ S ⊆ V , (S 6= ∅, V )),
e∈E (S)
e∈E (S)
∑
c(e)xe
e∈E
e∈E
∑
10 / 46
∑
xe = |V | − 1,
xe = |V | − 1,
e∈E
e∈E
xe ∈ {0, 1}
xe ∈ {0, 1}
(∀ e ∈ E )
これは正しい定式化
(∀ e ∈ E )
ここからの目標
定式化 4 の線形計画緩和が整数性を持つことの証明
I
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
道具：Kruskal のアルゴリズム
岡本吉央 (電通大)
11 / 46
離散最適化基礎論 (10)
Kruskal のアルゴリズム
2014 年 12 月 19 日
12 / 46
Kruskal のアルゴリズム
目次
Kruskal のアルゴリズム
最小費用全域木問題を効率よく解く方法
1
Kruskal のアルゴリズム
最小費用全域木問題：第 4 の定式化
1
2
Kruskal のアルゴリズム
2
3
最小費用全域木問題と完全双対整数性：証明
4
今日のまとめ
G の辺を費用の小さい順に並べる
(c(e1 ) ≤ c(e2 ) ≤ · · · ≤ c(em ) であると仮定する)
T := ∅
3
すべての i := 1, . . . , m に対して，以下を繰り返し
{
T ∪ {ei } (T ∪ {ei } が閉路を含まないとき)
T :=
T
(T ∪ {ei } が閉路を含むとき)
4
T を出力
これは正しいアルゴリズム (必ず最小費用全域木を出力する)
I
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
13 / 46
証明は『アルゴリズム論第一』か『アルゴリズム論第二』を参照
岡本吉央 (電通大)
離散最適化基礎論 (10)
Kruskal のアルゴリズム
14 / 46
Kruskal のアルゴリズム
Kruskal のアルゴリズム：実行例
Kruskal のアルゴリズム：階層構造 (ラミナ)
10
14
9
6
8
10
12
5
6
8
12
13
3
X4
15
7
4
離散最適化基礎論 (10)
X8
14
9
13
1
岡本吉央 (電通大)
2014 年 12 月 19 日
X7
2014 年 12 月 19 日
15 / 46
15
X6
岡本吉央 (電通大)
1
5
3
X2
X1
4
X3
離散最適化基礎論 (10)
7
X5
2014 年 12 月 19 日
16 / 46
最小費用全域木問題と完全双対整数性：証明
最小費用全域木問題と完全双対整数性：証明
目次
最小費用全域木問題：定式化 4
最小費用全域木問題：01 整数計画問題としての定式化 4
1
x ∈ RE は変数
最小費用全域木問題：第 4 の定式化
(P)
2
∑
minimize
c(e)xe
e∈E
Kruskal のアルゴリズム
∑
subject to
xe ≤ |S| − 1
(∀ S ⊆ V , (S 6= ∅, V )),
e∈E (S)
3
∑
最小費用全域木問題と完全双対整数性：証明
xe = |V | − 1,
e∈E
4
xe ∈ {0, 1}
今日のまとめ
(∀ e ∈ E )
ここからの目標
定式化 4 の線形計画緩和が整数性を持つことの証明
I
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
道具：Kruskal のアルゴリズム
岡本吉央 (電通大)
17 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
2014 年 12 月 19 日
最小費用全域木問題と完全双対整数性：証明
最小費用全域木問題：定式化 4 — 線形計画緩和
最小費用全域木問題：定式化 4 — 線形計画緩和の双対問題
最小費用全域木問題：定式化 4 の線形計画緩和
最小費用全域木問題：定式化 4 の線形計画緩和の双対問題
x ∈ RE は変数
y ∈ R2
(LP) minimize
∑
c(e)xe
V −{∅,V }
(DLP)
，z ∈ R, w ∈ RE は変数
∑
∑
maximize
−
(|S| − 1)ys − (|V | − 1)z −
we
e∈E
S∈2V −{∅,V }
∑
subject to
xe ≤ |S| − 1
(∀ S ⊆ V , (S 6= ∅, V )),
−
subject to
e∈E (S)
∑
18 / 46
∑
e∈E
yS − z − we ≤ c(e)
(∀ e ∈ E ),
S:e⊆S(V
xe = |V | − 1,
e∈E
0 ≤ xe ≤ 1
(∀ e ∈ E )
yS ≥ 0
(∀ S ∈ 2V − {∅, V }),
we ≥ 0
(∀ e ∈ E )
復習：2V は V の冪集合 (べき集合) で，V の部分集合全体の集合のこと
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
19 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
2014 年 12 月 19 日
最小費用全域木問題と完全双対整数性：証明
最小費用全域木問題：定式化 4 — 完全双対整数性の証明の方針
完全双対整数性の証明：(LP) の許容解
行列 A ∈ Zm×n ，ベクトル b ∈ Zm ，凸多面体 P = {x ∈ Rn | Ax ≤ b}
Kruskal のアルゴリズムを実行
I 選ばれた |V | − 1 個の辺を，選ばれた順に f1 , . . . , f|V |−1 とする
完全双対整数性とは？ (再確認)
I
不等式系 Ax ≤ b が完全双対整数性 (total dual integrality) を持つ，
(あるいは，TDI (totally dual integral) である) とは，
任意の c ∈ Zn に対して，次の最適化問題が整数最適解を持つこと
(DLP)
A> y = c, y ≥ 0
subject to
このとき，x ∗ ∈ RE を次で定義
{
0 (e 6∈ {f1 , . . . , f|V |−1 }),
xe∗ =
1 (e ∈ {f1 , . . . , f|V |−1 })
I
この x ∗ は (P) の許容解
(∵ Kruskal のアルゴリズムは全域木を出力する)
I
「(P) の許容集合 ⊆ (LP) の許容集合」なので，x ∗ は (LP) の許容解
証明の方針：実際に，(DLP) の整数最適解を構成する
1
(LP) の許容解を，Kruskal のアルゴリズムによって構成する
2
(DLP) の整数許容解を，Kruskal のアルゴリズムから構成する
3
その 2 つの目的関数値が一致することを確認する
4
弱双対定理から，これらは最適解である
離散最適化基礎論 (10)
2014 年 12 月 19 日
つまり，c(f1 ) ≤ · · · ≤ c(f|V |−1 )
I
b> y
minimize
岡本吉央 (電通大)
岡本吉央 (電通大)
21 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
完全双対整数性の証明：(DLP) の許容解
Kruskal のアルゴリズムを実行
I 選ばれた |V | − 1 個の辺を，選ばれた順に f1 , . . . , f|V |−1 とする
y ∗ ∈ R2
I
2014 年 12 月 19 日
22 / 46
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：(DLP) の許容解 — 準備
I
20 / 46
V −{∅,V }
つまり，c(f1 ) ≤ · · · ≤ c(f|V |−1 )
yS∗
Xk ：(V , {f1 , . . . , fk }) の連結成分で fk を含むものの頂点集合
，z ∗ ∈ R, w ∗ ∈ RE を次で定義


c(f`(k) ) − c(fk ) (ある k に対して， S = Xk のとき),
=
ただし， `(k) = min{i > k | fi ∈ δ(Xk )}


0
(それ以外のとき),
z ∗ = −c(f|V |−1 )
10
we∗ = 0
X8
14
9
6
8
(∀ e ∈ E )
12
13
X4
X7
15
X6
10
5
4
8
12
3
13
X2
X1
X8
14
9
6
1
X3
X4
7
X7
X5
15
X6
1
5
3
X2
X1
4
X3
7
X5
注：c(e) がすべての e ∈ E に対して整数 ⇒ y ∗ , z ∗ , w ∗ も整数 (ベクトル)
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
23 / 46
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
24 / 46
最小費用全域木問題と完全双対整数性：証明
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：(DLP) に対する許容性 (1)
完全双対整数性の証明：(DLP) に対する許容性 (2)
yS∗ ≥ 0 が成り立つのはなぜか？
I ある k に対して，S = Xk である場合のみ考える
I このとき，y ∗ = c(f`(k) ) − c(fk ) で，`(k) = min{i > k | fi ∈ δ(Xk )}
S
I つまり，`(k) > k なので，
Kruskal のアルゴリズムにおいて，f`(k) は fk よりも後に追加された
I ∴ c(f`(k) ) ≥ c(fk )
I ∴ y ∗ = c(f`(k) ) − c(fk ) ≥ 0
S
もう 1 つの不等式制約が成り立つのはなぜか？
I
X1 , . . . , X|V |−2 のどれが e ∈ E を含むか考える
I
e を含むものは「包含関係の鎖」を作る
つまり，ある k1 < k2 < · · · < ki が存在して，
e ⊆ Xk1 ⊆ Xk2 ⊆ · · · ⊆ Xki となり，
任意の k 6∈ {k1 , . . . , ki } に対して，e 6⊆ Xk
10
X8
14
9
6
10
8
X4
12
13
X4
X7
1
5
X7
3
X2
X1
15
X6
X3
4
12
13
9
6
8
X8
14
1
5
3
X2
X1
15
X6
4
X3
7
X5
7
X5
費用 9 の辺を e とすると，e ⊆ X6 ⊆ X7 ⊆ X8
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
25 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
完全双対整数性の証明：(DLP) に対する許容性 (2) 続き
もう 1 つの不等式制約が成り立つのはなぜか？
もう 1 つの不等式制約が成り立つのはなぜか？
このとき，
I
yX∗k
= c(fk2 ) − c(fk1 )
yX∗k
2
= c(fk3 ) − c(fk2 )
1
I
つまり，
∑
yS∗ =
S:e⊆S(V
= c(f|V |−1 ) − c(fi )
i
∑
つまり，
∑
−
yS∗ − z ∗ − we∗ = −c(f|V |−1 ) + c(fk1 ) + c(f|V |−1 ) − 0 = c(fk1 )
S:e⊆S(V
..
.
yX∗k
i
26 / 46
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：(DLP) に対する許容性 (2) 続き
I
2014 年 12 月 19 日
I
ここで，c(fk1 ) ≤ c(e) であることを導く
I
fk1 = e ならば c(fk1 ) = c(e)
I
よって，fk1 6= e と仮定する
yX∗k = c(f|V |−1 ) − c(fk1 )
j
j=1
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
27 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
2014 年 12 月 19 日
28 / 46
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：(DLP) に対する許容性 (2) 続き
最小費用全域木問題：定式化 4 — 完全双対整数性の証明の方針 (確認)
もう 1 つの不等式制約が成り立つのはなぜか？
I まず，e ⊆ Xk であり，fk ⊆ Xk である
1
1
1
I Kruskal のアルゴリズムの動作から，部分グラフ (V , {f1 , . . . , fk −1 })
1
において，fk1 の両端点は異なる連結成分に含まれる
I Xk は e を含む最小の Xk だから，e の両端点もその部分グラフの
1
異なる連結成分に含まれなければならない
I つまり，Xk−1 に e を追加しても Xk が得られていた
I しかし，Kruskal のアルゴリズムは fk を選び，e を選ばなかった
1
I Kruskal のアルゴリズムの動作から，c(fk ) ≤ c(e) となる
1
行列 A ∈ Zm×n ，ベクトル b ∈ Zm ，凸多面体 P = {x ∈ Rn | Ax ≤ b}
完全双対整数性とは？ (再確認)
不等式系 Ax ≤ b が完全双対整数性 (total dual integrality) を持つ，
(あるいは，TDI (totally dual integral) である) とは，
任意の c ∈ Zn に対して，次の最適化問題が整数最適解を持つこと
(DLP)
minimize
subject to
b> y
A> y = c, y ≥ 0
証明の方針：実際に，(DLP) の整数最適解を構成する
f k1
1
(LP) の許容解を，Kruskal のアルゴリズムによって構成する
2
(DLP) の整数許容解を，Kruskal のアルゴリズムから構成する
3
その 2 つの目的関数値が一致することを確認する
4
弱双対定理から，これらは最適解である
e
X k1
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
29 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
完全双対整数性の証明：目的関数値の一致 — 補題 (2)
まず，次を証明する
証明 (続き)：任意の k ≥ 1 を考える
I
補題
任意の k ∈ {1, . . . , |V | − 2} に対して
∑
(|S| − 1) · yS∗ =
S⊆Xk
∑
任意の k 0 ≤ k に対して次が正しいと仮定する
∑
∑
c(e) − (|Xk 0 | − 1) · c(f`(k 0 ) )
−
(|S| − 1) · yS∗ =
S⊆Xk 0
c(e) − (|Xk | − 1) · c(f`(k) )
I
e∈E (Xk )∩F
ただし，F = {f1 , . . . , f|V |−1 }
このとき，次を証明する
∑
−
(|S| − 1) · yS∗ =
S⊆Xk+1
証明：k に関する帰納法
I
I
I
I
I
I
k = 1 のときを考える
|X1 | = 2 なので，|X1 | − 1 = 1
左辺 = −(c(f`(1) ) − c(f1 )) = c(f1 ) − c(f`(1) )
右辺 = c(f1 ) − c(f`(1) )
したがって，左辺 = 右辺
岡本吉央 (電通大)
30 / 46
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：目的関数値の一致 — 補題 (1)
−
2014 年 12 月 19 日
離散最適化基礎論 (10)
2
3
31 / 46
∑
c(e) − (|Xk+1 | − 1) · c(f`(k+1) )
e∈E (Xk+1 )∩F
場合分け
1
2014 年 12 月 19 日
e∈E (Xk 0 )∩F
fk+1 の両端点が (V , {f1 , . . . , fk }) の孤立点であるとき
fk+1 の一方の端点のみが (V , {f1 , . . . , fk }) の孤立点であるとき
fk+1 のどちらの端点も (V , {f1 , . . . , fk }) の孤立点でないとき
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
32 / 46
最小費用全域木問題と完全双対整数性：証明
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：目的関数値の一致 — 補題 (3)
完全双対整数性の証明：目的関数値の一致 — 補題 (4)
1
fk+1 の両端点が (V , {f1 , . . . , fk }) の孤立点であるとき
2
fk+1 の一方の端点のみが (V , {f1 , . . . , fk }) の孤立点であるとき
I
つまり，|Xk+1 | = 2
I
I
左辺 = −(c(f`(k+1) ) − c(fk+1 )) = c(fk+1 ) − c(f`(k+1) )
つまり，ある頂点 v ∈ V と添え字 k 0 ≤ k が存在して，
Xk+1 = Xk 0 ∪ {v }，かつ，fk+1 = f`(k 0 )
I
右辺 = c(fk+1 ) − c(f`(k+1) )
I
また，このとき，E (Xk+1 ) ∩ F = (E (Xk 0 ) ∩ F ) ∪ {fk+1 }
I
したがって，左辺 = 右辺
fℓ(k+1)
fk+1
fk+1
Xk+1
fℓ(k+1)
岡本吉央 (電通大)
Xk ′
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
33 / 46
最小費用全域木問題と完全双対整数性：証明
Xk+1
v
離散最適化基礎論 (10)
2014 年 12 月 19 日
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：目的関数値の一致 — 補題 (5)
完全双対整数性の証明：目的関数値の一致 — 補題 (6)
2
fk+1 の一方の端点のみが (V , {f1 , . . . , fk }) の孤立点であるとき
3
I
したがって，証明したいことの左辺
I
つまり，ある 2 つの添え字 k 0 , k 00 ≤ k が存在して，
Xk+1 = Xk 0 ∪ Xk 00 ，Xk 0 ∩ Xk 00 = ∅，かつ，fk+1 = f`(k 0 ) = f`(k 00 )
I
また，このとき，
E (Xk+1 ) ∩ F = (E (Xk 0 ) ∩ F ) ∪ (E (Xk 00 ) ∩ F ) ∪ {fk+1 }
∑
= −
∑
(|S| − 1)yS∗
S⊆Xk+1
= −
(|S| − 1)yS∗ − (|Xk+1 | − 1)yX∗k+1
S⊆Xk 0
∑
=
fk+1 のどちらの端点も (V , {f1 , . . . , fk }) の孤立点でないとき
c(e) − (|Xk 0 | − 1)c(f`(k 0 ) ) − (|Xk+1 | − 1)(c(f`(k+1) ) − c(fk+1 ))
fℓ(k+1)
fk+1
e∈E (Xk 0 )∩F
∑
=
34 / 46
c(e) − (|Xk+1 | − 2)c(fk+1 ) − (|Xk+1 | − 1)(c(f`(k+1) ) − c(fk+1 ))
Xk ′
Xk ′′
Xk+1
e∈E (Xk 0 )∩F
∑
=
c(e) + c(fk+1 ) − (|Xk+1 | − 1)c(f`(k+1) )
e∈E (Xk 0 )∩F
∑
=
c(e) − (|Xk+1 | − 1)c(f`(k+1) )
e∈E (Xk+1 )∩F
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
35 / 46
最小費用全域木問題と完全双対整数性：証明
離散最適化基礎論 (10)
2014 年 12 月 19 日
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：目的関数値の一致 — 補題 (7)
完全双対整数性の証明：目的関数値の一致 — 補題 (8)
3
fk+1 のどちらの端点も (V , {f1 , . . . , fk }) の孤立点でないとき
3
fk+1 のどちらの端点も (V , {f1 , . . . , fk }) の孤立点でないとき
I
したがって，証明したいことの左辺
I
したがって，証明したいことの左辺
∑
= −
∑
(|S| − 1)yS∗
S⊆Xk+1
= −
(|S| − 1)yS∗ −
S⊆Xk 0
=
∑
c(e) − (|Xk 0 | − 1)c(f`(k 0 ) )+
e∈E (Xk 0 )∩F
∑
(|S| − 1)yS∗ − (|Xk+1 | − 1)yX∗k+1
S⊆Xk 00
c(e)−(|Xk 00 |−1)c(f`(k 00 ) )−(|Xk+1 |−1)(c(f`(k+1) )−c(fk+1 ))
e∈E (Xk 00 )∩F
c(e) − (|Xk 0 | − 1)c(f`(k 0 ) )+
∑
=
e∈E (Xk 0 )∩F
∑
∑
=
∑
36 / 46
∑
c(e) +
e∈E (Xk 0 )∩F
c(e)
e∈E (Xk 00 )∩F
−(|Xk 0 | − 1)c(fk+1 ) − (|Xk 00 | − 1)c(fk+1 )
−(|Xk 0 | + |Xk 00 | − 1)(c(f`(k+1) ) − c(fk+1 ))
∑
∑
c(e)+
c(e)+c(fk+1 )−(|Xk 0 |+|Xk 00 |−1)c(f`(k+1) )
=
c(e)−(|Xk 00 |−1)c(f`(k 00 ) )−(|Xk+1 |−1)(c(f`(k+1) )−c(fk+1 ))
e∈E (Xk 00 )∩F
e∈E (Xk 0 )∩F
e∈E (Xk 00 )∩F
∑
=
c(e) − (|Xk+1 | − 1)c(f`(k+1) )
e∈E (Xk+1 )∩F
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
岡本吉央 (電通大)
37 / 46
最小費用全域木問題と完全双対整数性：証明
f|V |−1 が Xk 0 と Xk 00 を結ぶとする
I
つまり，V = Xk 0 ∪ Xk 00 ，Xk 0 ∩ Xk 00 = ∅，
f`(k 0 ) = f`(k 00 ) = f|V |−1 ，(E (Xk 0 ) ∩ F ) ∪ (E (Xk 00 ) ∩ F ) ∪ {f|V |−1 } = F
I
∗ ∗ , w ∗ ) の目的関数値は
このとき，
∑ (DLP) における許容解 (y , z ∑
−
(|S| − 1)ys∗ − (|V | − 1)z ∗ −
we∗
S∈2V −{∅,V }
= −
∑
(|S| − 1)ys∗ −
S⊆Xk 0
f|V |−1
X
k ′′
=
V
∑
e∈E
(|S| − 1)yS∗ + (|V | − 1)c(f|V |−1 )
S⊆Xk 00
e∈E (Xk 0 )∩F
∑
=
∑
e∈E (Xk 0 )∩F
I
離散最適化基礎論 (10)
∑
c(e) − (|Xk 0 | − 1)c(f`(k 0 ) )+
c(e) − (|Xk 00 | − 1)c(f`(k 00 ) ) + (|V | − 1)c(f|V |−1 )
e∈E (Xk 00 )∩F
岡本吉央 (電通大)
38 / 46
完全双対整数性の証明：目的関数値の一致 — 補題の利用 (2)
I
X
2014 年 12 月 19 日
最小費用全域木問題と完全双対整数性：証明
完全双対整数性の証明：目的関数値の一致 — 補題の利用 (1)
k′
離散最適化基礎論 (10)
2014 年 12 月 19 日
39 / 46
c(e) +
∑
c(e) + c(f|V |−1 ) =
e∈E (Xk 00 )∩F
∑
c(e)
e∈F
これは (LP) における許容解 x ∗ の目的関数値
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
40 / 46
最小費用全域木問題と完全双対整数性：証明
今日のまとめ
結論
目次
分かったこと
定式化 4 (の線形計画緩和) の不等式系は完全双対整数性を持つ
1
最小費用全域木問題：第 4 の定式化
2
Kruskal のアルゴリズム
3
最小費用全域木問題と完全双対整数性：証明
4
今日のまとめ
つまり，線形計画緩和の許容領域は凸多面体
もう 1 つ分かること
Kruskal のアルゴリズムは正しく最小費用全域木を出力する
つまり，Kruskal のアルゴリズムの正しさを証明するために
線形計画法と凸多面体を利用した
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
41 / 46
岡本吉央 (電通大)
離散最適化基礎論 (10)
今日のまとめ
2014 年 12 月 19 日
42 / 46
今日のまとめ
今日の目標
この講義のねらい：流れ
今日の目標
solution
最小費用全域木問題の持つ完全双対整数性を理解する
I
前回は準備
I
今回，証明
combinatorial
optimization
problem
3
3
5
4
6
8
6
4
2
8
1
3 2
7
integer
program
1
x2 2
2
1
good
linear
program+ structure
x1 −2x2 =−2
−2x1 −3x2 =−6
1
x2 2
2
1
x1 −2x2 =−2
−2x1 −3x2 =−6
x1
O
formulation
x1
O
3
3
relaxation
■ 組合せ最適化問題を整数計画問題として定式化
■ 整数計画問題を線形計画問題として緩和
■ 線形計画問題の「よい」構造を観察
■ 線形計画問題を用いて組合せ最適化問題の解決 ←次回もココ
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
43 / 46
岡本吉央 (電通大)
離散最適化基礎論 (10)
2014 年 12 月 19 日
44 / 46

Download Report