1. No category

今日の目標
今日の目標
離散最適化基礎論 第 9 回
完全双対整数性：全域木 (1)
最小費用全域木問題の持つ完全双対整数性を理解する
岡本 吉央
[email protected]
I
今日は準備
I
次回に証明
電気通信大学
2014 年 12 月 12 日
最終更新：2014 年 12 月 13 日
岡本 吉央 (電通大)
08:37
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
1 / 30
最小費用全域木問題の定式化：復習
離散最適化基礎論 (9)
2014 年 12 月 12 日
2 / 30
2014 年 12 月 12 日
4 / 30
最小費用全域木問題の定式化：復習
目次
木
無向グラフ G = (V , E )
木とは？
1
2
最小費用全域木問題の定式化：復習
G が木であるとは，次の 2 つの条件を満たすこと
I
G は連結である
I
G は閉路を部分グラフとして含まない
最小費用全域木問題と完全双対整数性
e
b
a
3
f
d
今日のまとめ
c
i
j
l
k
h
g
「連結である」ことの定義は次のスライドで
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
3 / 30
最小費用全域木問題の定式化：復習
離散最適化基礎論 (9)
最小費用全域木問題の定式化：復習
グラフの連結性
木の辺数
無向グラフ G = (V , E )
木の辺数
グラフが連結であるとは？
任意の木 G = (V , E ) に対して
G が連結であるとは，
任意の 2 頂点 u, v ∈ V に対して，u から v へ至る道が存在すること
|E | = |V | − 1
連結ではないグラフは非連結と呼ばれる
e
b
a
f
e
b
a
d
c
i
j
l
k
f
c
c
i
j
l
k
非連結グラフ
i
j
l
k
h
h
g
f
d
d
h
g
e
b
a
g
|V | = 12, |E | = 11
連結グラフ
注：
「グラフが連結する」とは言わない
岡本 吉央 (電通大)
証明は『数理解析』又は『グラフとネットワーク』を参照
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
5 / 30
最小費用全域木問題の定式化：復習
離散最適化基礎論 (9)
2014 年 12 月 12 日
最小費用全域木問題の定式化：復習
グラフの全域木
最小費用全域木問題
無向グラフ G = (V , E )
最小費用全域木問題とは？
全域木とは？
I
入力：無向グラフ G = (V , E )，非負辺費用関数 c : E → R
G の全域木とは，G の部分グラフで次を満たすもの
I
出力：G の全域木で，費用が最小のもの
I
木である
I
頂点集合が V である
v2
全張木，生成木とも呼ぶことがある
4
v1
e
b
a
f
i
j
l
k
2
2
v8
5
3
1
v7
事実
h
岡本 吉央 (電通大)
v6
1
v5
v3
c
4
v4
2
1
d
g
3
2
5
I
6 / 30
最小費用全域木問題は効率よく解くことができる (Kruskal ’56, Prim ’57)
離散最適化基礎論 (9)
G が非連結であるとき，G の全域木は存在しない
効率よく = |V | と |E | に関する多項式時間で
2014 年 12 月 12 日
7 / 30
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
8 / 30
最小費用全域木問題の定式化：復習
最小費用全域木問題の定式化：復習
最小費用全域木問題：定式化 1
最小費用全域木問題：定式化 1 の例
記法：δ(S) = S に一方の端点，V − S にもう一方の端点を持つ
辺全体の集合
Variables xa
最小費用全域木問題：01 整数計画問題としての定式化 1
x∈
RE
1
xb
は変数
xc
xe
2
minimize
1
Costs
2
xd
∑
3
xa , xb , xc , xd , xe ∈ R は変数
c(e)xe
e∈E
∑
subject to
xe ≤ |C | − 1
minimize
(∀ C : G の閉路),
subject to
e∈C
∑
xe ≥ 1
2xa + xb + 3xc + 2xd + xe
xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3,
xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1,
(∀ S ⊆ V : S 6= ∅, S 6= V ),
xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1,
e∈δ(S)
xe ∈ {0, 1}
(∀ e ∈ E )
xa , xb , xc , xd , xe ∈ {0, 1}
これは正しい定式化
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
9 / 30
最小費用全域木問題の定式化：復習
離散最適化基礎論 (9)
2014 年 12 月 12 日
最小費用全域木問題の定式化：復習
全域木の性質
最小費用全域木問題：定式化 2
木であるための必要十分条件
最小費用全域木問題：01 整数計画問題としての定式化 2
無向グラフ G = (V , E ) に対して，次の 3 つは同値
x ∈ RE は変数
1
G は閉路を含まない，かつ，G は連結である (つまり，G は木である)
2
G は閉路を含まない，かつ，|E | = |V | − 1 である
3
minimize
定式化 1 は
1
に基づいている
I
定式化 2 は
2
に基づいて行う
I
定式化 3 は
3
に基づいて行う
∑
c(e)xe
e∈E
G は連結である，かつ，|E | = |V | − 1 である
I
10 / 30
subject to
∑
xe ≤ |C | − 1
(∀ C : G の閉路),
e∈C
∑
xe = |V | − 1,
e∈E
xe ∈ {0, 1}
(∀ e ∈ E )
これも正しい定式化
証明は『数理解析』又は『グラフとネットワーク』を参照
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
11 / 30
最小費用全域木問題の定式化：復習
離散最適化基礎論 (9)
最小費用全域木問題：定式化のまとめ
最小費用全域木問題：01 整数計画問題としての定式化 3
定式化 1
minimize
∑
I
subject to
c(e)xe
I
xe ≥ 1
I
xe = |V | − 1,
2014 年 12 月 12 日
14 / 30
カットに対する制約 と 辺数に対する等式制約
疑問
e∈E
xe ∈ {0, 1}
閉路に対する制約 と 辺数に対する等式制約
定式化 3
(∀ S ⊆ V : S 6= ∅, S 6= V ),
e∈δ(S)
∑
閉路に対する制約 と カットに対する制約
定式化 2
e∈E
∑
12 / 30
最小費用全域木問題の定式化：復習
最小費用全域木問題：定式化 3
x ∈ RE は変数
2014 年 12 月 12 日
どの定式化が完全双対整数性を持つのだろうか？
(∀ e ∈ E )
これも正しい定式化
注意
同じ組合せ最適化問題を様々な方法で定式化できる
「よい定式化」と「悪い定式化」がある
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
13 / 30
岡本 吉央 (電通大)
最小費用全域木問題と完全双対整数性
離散最適化基礎論 (9)
最小費用全域木問題と完全双対整数性
目次
最小費用全域木問題：定式化 1 の例
1
xb
1
最小費用全域木問題の定式化：復習
Variables xa
xc
xe
2
Costs
xa , xb , xc , xd , xe ∈ R は変数
最小費用全域木問題と完全双対整数性
minimize
subject to
3
1
2
xd
2
3
今日のまとめ
2xa + xb + 3xc + 2xd + xe
xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3,
xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1,
xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1,
xa , xb , xc , xd , xe ∈ {0, 1}
(xa , xb , xc , xd , xe ) = (1, 1, 0, 0, 1) は最適解で，最適値は 4
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
15 / 30
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
16 / 30
最小費用全域木問題と完全双対整数性
最小費用全域木問題と完全双対整数性
最小費用全域木問題：定式化 1 の例 — 線形計画緩和
定式化 1
1
xb
Variables xa
最小費用全域木問題：定式化のまとめ
閉路に対する制約 と カットに対する制約
I
xe
xc
2
1
3
Costs
閉路に対する制約 と 辺数に対する等式制約
I
2
xd
→持たない
定式化 2
定式化 3
xa , xb , xc , xd , xe ∈ R は変数
minimize
subject to
カットに対する制約 と 辺数に対する等式制約
I
2xa + xb + 3xc + 2xd + xe
疑問
xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3,
どの定式化が完全双対整数性を持つのだろうか？
xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1,
xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1,
0 ≤ xa , xb , xc , xd , xe ≤ 1
(xa , xb , xc , xd , xe ) = (1/2, 1/2, 0, 1/2, 1/2) は許容解で，目的関数値は 3
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
17 / 30
最小費用全域木問題と完全双対整数性
1
minimize
1
1
1
1
1
Costs
Variables xa
minimize
xa + xb + xf ≤ 2, xb + xc + xe ≤ 2, xc + xd + xf ≤ 2,
xe
xf
xd
1
Costs
xa + xb + xf ≤ 2, xb + xc + xe ≤ 2, xc + xd + xf ≤ 2,
xa + xd + xe ≤ 2, xa + xb + xc + xd ≤ 3,
xa + xc + xe + xf ≤ 3, xb + xd + xe + xf ≤ 3,
xa + xc + xe + xf ≤ 3, xb + xd + xe + xf ≤ 3,
xa + xb + xc + xd + xe + xf + xg = 4,
xa + xb + xc + xd + xe + xf + xg = 4,
xa , xb , xc , xd , xe , xf , xg ∈ {0, 1}
0 ≤ xa , xb , xc , xd , xe , xf , xg ≤ 1
離散最適化基礎論 (9)
2014 年 12 月 12 日
(xa , xb , xc , xd , xe , xf , xg ) = (1, 1/2, 1, 1/2, 1/2, 1/2, 0) は最適解で，
最適値は 4
岡本 吉央 (電通大)
19 / 30
最小費用全域木問題と完全双対整数性
離散最適化基礎論 (9)
2014 年 12 月 12 日
20 / 30
最小費用全域木問題と完全双対整数性
最小費用全域木問題：定式化のまとめ
最小費用全域木問題：定式化 3 の例
3
xb
定式化 1
2
xc
閉路に対する制約 と カットに対する制約
Variables xa
→持たない
3
xf
xd
定式化 2
xe
閉路に対する制約 と 辺数に対する等式制約
→持たない
定式化 3
minimize
2
Costs
2
3
3xa + 3xb + 2xc + 2xd + 3xe + 2xf
xa + xb ≥ 1, xb + xc + xf ≥ 1, xc + xd ≥ 1,
subject to
カットに対する制約 と 辺数に対する等式制約
I
1
1
1
xa + xd + xe ≤ 2, xa + xb + xc + xd ≤ 3,
岡本 吉央 (電通大)
I
1
xc
xa + xb + xc + xd + xe + xf + 3xg
subject to
(xa , xb , xc , xd , xe , xf , xg ) = (1, 1, 1, 0, 0, 0, 1) は最適解で，最適値は 6
I
3
xg
xa + xb + xc + xd + xe + xf + 3xg
subject to
1
xb
3
xg
xc
18 / 30
最小費用全域木問題：定式化 2 の例 — 線形計画緩和
xb
Variables xa
2014 年 12 月 12 日
最小費用全域木問題と完全双対整数性
最小費用全域木問題：定式化 2 の例
xe
xf
xd
離散最適化基礎論 (9)
xd + xe + xf ≥ 1, xa + xe ≥ 1, xa + xc + xf ≥ 1,
疑問
xa + xb + xc + xd ≥ 1, xa + xb + xd + xe + xf ≥ 1,
どの定式化が完全双対整数性を持つのだろうか？
xb + xe ≥ 1, xb + xd + xf ≥ 1, xb + xc + xd + xe ≥ 1,
xa + xb + xc + xe + xf ≥ 1, xc + xe + xf ≥ 1,
xa + xc + xf ≥ 1, xa + xd + xf ≥ 1,
xa + xb + xc + xd + xe + xf = 4,
xa , xb , xc , xd , xe , xf ∈ {0, 1}
(xa , xb , xc , xd , xe , xf ) = (1, 1, 1, 1, 0, 0) は最適解で，最適値は 10
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
岡本 吉央 (電通大)
21 / 30
最小費用全域木問題と完全双対整数性
最小費用全域木問題：定式化のまとめ
3
xf
定式化 1
2
xc
xd
xe
subject to
22 / 30
3
xb
minimize
2014 年 12 月 12 日
最小費用全域木問題と完全双対整数性
最小費用全域木問題：定式化 3 の例 — 線形計画緩和
Variables xa
離散最適化基礎論 (9)
2
Costs
I
2
閉路に対する制約 と カットに対する制約
→持たない
定式化 2
3
I
3xa + 3xb + 2xc + 2xd + 3xe + 2xf
閉路に対する制約 と 辺数に対する等式制約
→持たない
定式化 3
xa + xb ≥ 1, xb + xc + xf ≥ 1, xc + xd ≥ 1,
I
xd + xe + xf ≥ 1, xa + xe ≥ 1, xa + xc + xf ≥ 1,
カットに対する制約 と 辺数に対する等式制約
xa + xb + xc + xd ≥ 1, xa + xb + xd + xe + xf ≥ 1,
疑問
xb + xe ≥ 1, xb + xd + xf ≥ 1, xb + xc + xd + xe ≥ 1,
どの定式化が完全双対整数性を持つのだろうか？
xa + xb + xc + xe + xf ≥ 1, xc + xe + xf ≥ 1,
→持たない
解答：どれも持たない
xa + xc + xf ≥ 1, xa + xd + xf ≥ 1,
xa + xb + xc + xd + xe + xf = 4,
0 ≤ xa , xb , xc , xd , xe , xf ≤ 1
(xa , xb , xc , xd , xe , xf ) = (1/2, 1/2, 1, 1, 1/2, 1/2) は許容解で，最適値は 9.5
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
23 / 30
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
24 / 30
最小費用全域木問題と完全双対整数性
今日のまとめ
最小費用全域木問題：次回予告
目次
次回予告
完全双対整数性を持つ最小費用全域木問題の定式化
I
それは，ここで考えた 3 つの定式化とは違う
I
証明には Kruskal のアルゴリズムを用いる
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
25 / 30
1
最小費用全域木問題の定式化：復習
2
最小費用全域木問題と完全双対整数性
3
今日のまとめ
岡本 吉央 (電通大)
離散最適化基礎論 (9)
今日のまとめ
2014 年 12 月 12 日
26 / 30
今日のまとめ
今日の目標
この講義のねらい：流れ
今日の目標
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
■ 組合せ最適化問題を整数計画問題として定式化
■ 整数計画問題を線形計画問題として緩和
■ 線形計画問題の「よい」構造を観察
■ 線形計画問題を用いて組合せ最適化問題の解決 ←次回もココ
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
27 / 30
岡本 吉央 (電通大)
離散最適化基礎論 (9)
2014 年 12 月 12 日
28 / 30