1. No category

今日の目標
今日の目標
離散最適化基礎論 第 11 回
整数性ギャップ：下界
整数性ギャップについて，次を理解する
岡本 吉央
[email protected]
I
整数性ギャップの定義
I
整数性ギャップの重要性
I
整数性ギャップに対する下界の導出法
電気通信大学
2015 年 1 月 9 日
最終更新：2015 年 1 月 9 日
岡本 吉央 (電通大)
10:44
離散最適化基礎論 (11)
2015 年 1 月 9 日
岡本 吉央 (電通大)
1 / 43
ここまでのまとめ と ここからの話
離散最適化基礎論 (11)
2015 年 1 月 9 日
2 / 43
ここまでのまとめ と ここからの話
目次
この講義のねらい：流れ
solution
1
2
ここまでのまとめ と ここからの話
整数性ギャップ：定義
3
6
3
5
3
4
integer
program
combinatorial
optimization
problem
4
6
整数性ギャップ：下界
最大重みマッチング問題
最小重み頂点被覆問題
1
x2 2
2
8
1
3 2
4
2
1
1
x2 2
x1 −2x2 =−2
2
−2x1 −3x2 =−6
x1 −2x2 =−2
1
−2x1 −3x2 =−6
x1
7
8
good
linear
program+ structure
O
x1
O
3
formulation
3
relaxation
■ 組合せ最適化問題を整数計画問題として定式化
今日のまとめ
■ 整数計画問題を線形計画問題として緩和
■ 線形計画問題の「よい」構造を観察
■ 線形計画問題を用いて組合せ最適化問題の解決
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
岡本 吉央 (電通大)
3 / 43
ここまでのまとめ と ここからの話
離散最適化基礎論 (11)
2015 年 1 月 9 日
4 / 43
ここまでのまとめ と ここからの話
この講義のねらい
整数計画問題の線形計画緩和
x ∈ Rn , y ∈ Rm は変数，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定数
解きやすい問題
解きにくい問題
多項式時間解法が存在する
NP 困難性が証明されている
(DLP) + 整数制約：(D)
整数計画問題：(P)
疑問
どうしてそのような違いが生まれるのか？
maximize
c >x
subject to
Ax ≤ b,
minimize
subject to
b> y
A> y = c, y ≥ 0,
y ∈ Zm
x ∈Z
n
解きやすい問題が持つ「共通の性質」は何か？
(P) の線形計画緩和：(LP)
部分的な回答
問題の持つ「多面体構造」が「美しい」と解きやすい
maximize
c >x
「多面体構造」が「美しい」
subject to
Ax ≤ b
凸多面体の整数性
(LP) の双対問題：(DLP)
minimize
subject to
b> y
A> y = c, y ≥ 0
観察
(P) の最適値 ≤ (LP) の最適値 = (DLP) の最適値 ≤ (D) の最適値
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
岡本 吉央 (電通大)
5 / 43
ここまでのまとめ と ここからの話
離散最適化基礎論 (11)
2015 年 1 月 9 日
6 / 43
ここまでのまとめ と ここからの話
整数計画問題の線形計画緩和
この講義のねらい：再考
観察 (再掲)
(P) の最適値 ≤ (LP) の最適値 = (DLP) の最適値 ≤ (D) の最適値
解きやすい問題
解きにくい問題
多項式時間解法が存在する
NP 困難性が証明されている
特に，
疑問
(P) の最適値 = (LP) の最適値 かつ (DLP) の最適値 = (D) の最適値 ⇒
どうしてそのような違いが生まれるのか？
(P) の最適値 = (LP) の最適値 = (DLP) の最適値 = (D) の最適値
解きやすい問題が持つ「共通の性質」は何か？
部分的な回答
つまり，次の 2 つが成り立つ場合が重要
I
(P) の最適値 = (LP) の最適値
I
(DLP) の最適値 = (D) の最適値
問題の持つ「多面体構造」が「美しい」と解きやすい
部分的な回答：言い換え
解きにくい問題の持つ「多面体構造」は「美しくない」
凸多面体に整数性がない
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
7 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
8 / 43
ここまでのまとめ と ここからの話
整数性ギャップ：定義
ここからの話
目次
部分的な回答：言い換え
解きにくい問題の持つ「多面体構造」は「美しくない」
1
ここまでのまとめ と ここからの話
2
整数性ギャップ：定義
3
整数性ギャップ：下界
最大重みマッチング問題
最小重み頂点被覆問題
4
今日のまとめ
凸多面体に整数性がない
今回と次回の目標
I
多面体構造の「美しくなさ」を定量化する
I
整数性ギャップの解析法を見る
岡本 吉央 (電通大)
整数性ギャップ
離散最適化基礎論 (11)
2015 年 1 月 9 日
岡本 吉央 (電通大)
9 / 43
離散最適化基礎論 (11)
整数性ギャップ：定義
2015 年 1 月 9 日
整数性ギャップ：定義
整数計画問題の線形計画緩和：再掲
整数性ギャップ：最大化問題
x ∈ Rn , y ∈ Rm は変数，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定数
x ∈ Rn は変数，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定数
c >x
maximize
Ax ≤ b,
subject to
整数計画問題：(P)
(DLP) + 整数制約：(D)
整数計画問題：(P)
minimize
b> y
subject to
>
A y = c, y ≥ 0,
c >x
subject to
Ax ≤ b,
(P) の整数性ギャップとは次の量
x ∈Z
n
y ∈Z
x ∈ Zn
整数性ギャップとは？
maximize
m
max
c≥0
(P) の線形計画緩和：(LP)
maximize
c >x
subject to
Ax ≤ b
10 / 43
(P) の線形計画緩和：(LP)
(LP) の双対問題：(DLP)
minimize
subject to
(LP) の最適値
(P) の最適値
これは (P) が
最大化問題であるときの定義
b> y
maximize
c >x
A> y = c, y ≥ 0
subject to
Ax ≤ b
観察
観察
(P) の整数性ギャップ ≥ 1
(P) の最適値 ≤ (LP) の最適値 = (DLP) の最適値 ≤ (D) の最適値
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
整数性ギャップ (integrality gap) は整数ギャップとも呼ぶ
11 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：定義
整数性ギャップ：例 (1)
x ∈ Rn は変数，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定数
整数計画問題：(P)
整数計画問題：(P)
整数性ギャップとは？
>
c x
x ∈Z
n
x1 + 2x2 ≤ 2,
x2
2x1 + x2 ≤ 2,
x1 , x2 ∈ Z
(P) の線形計画緩和：(LP)
Ax ≥ b
subject to
subject to
x1 ≥ 0, x2 ≥ 0,
これは (P) が
最小化問題であるときの定義
c >x
minimize
c >x
(P) の最適値
max
c≥0 (LP) の最適値
(P) の線形計画緩和：(LP)
x ∈ R2 は変数，c ∈ R2 は定数
maximize
(P) の整数性ギャップとは次の量
Ax ≥ b,
subject to
maximize
c >x
subject to
x1 + 2x2 ≤ 2,
観察
2x1 + x2 ≤ 2,
(P) の整数性ギャップ ≥ 1
x1 ≥ 0, x2 ≥ 0
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
13 / 43
岡本 吉央 (電通大)
整数性ギャップ：定義
subject to
x1 + 2x2 ≤ 2,
離散最適化基礎論 (11)
x ∈ R2 は変数，c ∈ R2 は定数
x2
14 / 43
x2
(1)
(1)
(2)
(2)
2x1 + x2 ≤ 2,
x1 ≥ 0, x2 ≥ 0,
(3)
x1 , x2 ∈ Z
x1
(3)
(P) の線形計画緩和：(LP)
c ∈ 法錐 (2) のとき，
つまり，ある 0 ≤ λ ≤ 1 に対して c > = (2 − λ, 1 + λ) のとき，
x1
>
maximize
c x
subject to
x1 + 2x2 ≤ 2,
c ∈ 法錐 (1) ∪ 法錐 (3) のとき，
2x1 + x2 ≤ 2,
x1 ≥ 0, x2 ≥ 0
岡本 吉央 (電通大)
2015 年 1 月 9 日
整数性ギャップ：例 (3)
整数計画問題：(P)
c >x
x1
整数性ギャップ：定義
整数性ギャップ：例 (2)
maximize
12 / 43
整数性ギャップ：定義
整数性ギャップ：最小化問題
minimize
2015 年 1 月 9 日
離散最適化基礎論 (11)
(LP) の最適値
=1
(P) の最適値
2015 年 1 月 9 日
15 / 43
(2 − λ) 23 + (1 + λ) 32
(LP) の最適値
2
=
=
(P) の最適値
max{2 − λ, 1 + λ}
max{2 − λ, 1 + λ}
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
16 / 43
整数性ギャップ：定義
整数性ギャップ：定義
整数性ギャップ：例 (3)
整数性ギャップ：重要な性質
x2
(1)
命題
(LP) の許容領域が整凸多面体 ⇒
(2)
証明：(LP) の許容領域が整凸多面体であると仮定する
I このとき，任意の c ≥ 0 に対して，(P) の最適値 = (LP) の最適値
I したがって，((P) が最大化問題のときは)
(3)
x1
ここで，max{2 − λ, 1 + λ} は λ =
1
2
(P) の整数性ギャップ = max
c≥0
のとき最小となり，そのとき，
I
2
4
2
= 3 =
max{2 − λ, 1 + λ}
3
2
(P) が最小化問題であるときも同様
この意味で，整数性ギャップは
(LP) の許容集合が整凸多面体であることからどれだけ離れているか
という量を表している
4
(P) の整数性ギャップ =
3
離散最適化基礎論 (11)
2015 年 1 月 9 日
岡本 吉央 (電通大)
17 / 43
離散最適化基礎論 (11)
整数性ギャップ：下界
18 / 43
2015 年 1 月 9 日
20 / 43
整数性ギャップの解析
1
ここまでのまとめ と ここからの話
2
整数性ギャップ：定義
4
2015 年 1 月 9 日
整数性ギャップ：下界
目次
3
(LP) の最適値
= max 1 = 1
c≥0
(P) の最適値
整数性ギャップの重要性
したがって，
岡本 吉央 (電通大)
(P) の整数性ギャップ = 1
いろいろな組合せ最適化問題の整数計画定式化 (P) と
その線形計画緩和 (LP) を考えて，
整数性ギャップが何であるか，解析したい
例とする問題
整数性ギャップ：下界
最大重みマッチング問題
最小重み頂点被覆問題
I
最大重みマッチング問題
I
最小重み頂点被覆問題
I
今回は下界を証明する
I
次回は上界を証明する
今日のまとめ
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
19 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
最大重みマッチング問題
整数性ギャップ：下界
最大重みマッチング問題
グラフにおけるマッチング
最大重みマッチング
無向グラフ G = (V , E )
無向グラフ G = (V , E )
各辺 e ∈ E に対する非負重み w (e) ≥ 0 (辺重み関数 w : E → R)
マッチングとは？
最大重みマッチングとは？
G のマッチングとは辺部分集合 M ⊆ E で，
M のどの 2 辺も同じ頂点に接続しないもの
v2
v2
v6
v4
v6
e∈M
e∈M 0
v4
v1
v1
v8
v8
v5
v3
w に関する G の最大重みマッチングとは
G のマッチング M ⊆ E で，
∑
∑
G の任意のマッチング M 0 に対して
w (e) ≥
w (e) を満たすもの
v2
v5
v3
v7
4
v7
v1
{{v1 , v3 }, {v2 , v5 }, {v2 , v6 }} は
マッチングではない
4
v4
v6
2
2
v8
5
{{v1 , v2 }, {v4 , v7 }, {v6 , v8 }} は
マッチングである
3
2
2
1
1
v5
5
v3
3
1
v7
マッチングの辺 e ∈ M は e の端点を飽和する
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
21 / 43
岡本 吉央 (電通大)
最大重みマッチング問題
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
最大重みマッチング問題
最大重みマッチング問題
最大重みマッチング問題の定式化
最大重みマッチング問題とは？
最大マッチング問題：01 整数計画問題としての定式化
I
入力：無向グラフ G = (V , E )，非負辺重み関数 w : E → R
I
出力：G のマッチングで，重みが最大のもの
x ∈ RE は変数
(P) maximize
v2
3
2
4
2
1
v3
5
subject to
2
2
∑
xe ≤ 1
(∀ v ∈ V ),
e∈δ(v )
v8
1
v5
w (e)xe
e∈E
v6
5
v1
4
v4
∑
22 / 43
xe ∈ {0, 1}
3
1
(∀ e ∈ E )
記法：δ(v ) = v に接続する辺全体の集合
v7
事実
最大重みマッチング問題は効率よく解くことができる
(Edmonds, ’65)
効率よく = |V | と |E | に関する多項式時間で
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
23 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
24 / 43
整数性ギャップ：下界
最大重みマッチング問題
整数性ギャップ：下界
最大重みマッチング問題の線形計画緩和
最大重みマッチング問題の定式化 (P) を考える
(P) の線形計画緩和
x∈
RE
最大重みマッチング問題
最大重みマッチング問題の整数性ギャップ (下界)
命題
は変数
(LP)
∑
maximize
(P) の整数性ギャップ ≥
w (e)xe
e∈E
∑
subject to
xe ≤ 1
を満たすようなグラフが存在する
(∀ v ∈ V ),
証明の方針
e∈δ(v )
0 ≤ xe ≤ 1
(∀ e ∈ E )
(P) の整数性ギャップ = max
(LP) の最適値
(P) の最適値
3
2
I
そのようなグラフを構成すればよい
このとき，
w ≥0
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
整数性ギャップ：下界
1
(P) の最適値 = 1
2
(LP) の最適値 ≥ 3/2
2015 年 1 月 9 日
26 / 43
2015 年 1 月 9 日
28 / 43
2015 年 1 月 9 日
30 / 43
最大重みマッチング問題
最大重みマッチング問題の整数性ギャップ (下界)：証明 (2)
証明：頂点数 3 の閉路を考える
I すべての辺 e ∈ E に対して w (e) = 1 のときを考える
次の 2 つを証明する
離散最適化基礎論 (11)
最大重みマッチング問題
最大重みマッチング問題の整数性ギャップ (下界)：証明
I
岡本 吉央 (電通大)
25 / 43
示したいこと (1) ：(P) の最適値 = 1
I
すべての辺 e に対して w (e) = 1 なので，
(P) の最適値は最大マッチングの要素数に等しい
I
したがって，(P) の最適値 = 1
このとき，
(LP) の最適値
(P) の最適値
w = 1 のときの (LP) の最適値
w = 1 のときの (P) の最適値
3/2
3
=
1
2
(P) の整数性ギャップ = max
w ≥0
≥
≥
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
岡本 吉央 (電通大)
27 / 43
離散最適化基礎論 (11)
最大重みマッチング問題
整数性ギャップ：下界
最大重みマッチング問題の整数性ギャップ (下界)：証明 (3)
最大重みマッチング問題
目次
示したいこと (2) ：(LP) の最適値 ≥ 3/2
I
(∀ e ∈ E )
xe = 1/2
I
1
ここまでのまとめ と ここからの話
2
整数性ギャップ：定義
3
整数性ギャップ：下界
最大重みマッチング問題
最小重み頂点被覆問題
4
今日のまとめ
(LP) に対する次の許容解 x を考える
これが本当に許容解であることを確認する
I
頂点 v に接続する 2 辺が e1 , e2 であるとき
∑
xe = xe1 + xe2 = 1/2 + 1/2 = 1 ≤ 1
e∈δ(v )
∑
I
この許容解 x の目的関数値 =
I
したがって，(LP) の最適値 ≥ 許容解 x の目的関数値 = 3/2
岡本 吉央 (電通大)
e∈E
xe = 3/2
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
29 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
最小重み頂点被覆問題
整数性ギャップ：下界
最小重み頂点被覆問題
頂点被覆
最小頂点被覆
無向グラフ G = (V , E )
無向グラフ G = (V , E )
頂点被覆とは？
最小頂点被覆とは？
G の頂点被覆とは頂点部分集合 C ⊆ V で，
G のどの辺もある C の頂点に接続しているもの
G の最小頂点被覆とは頂点被覆 C ⊆ V で，
G の任意の頂点被覆 C 0 に対して |C | ≤ |C 0 | を満たすもの
v2
v2
v6
v4
v1
v8
v2
v8
{v2 , v3 , v4 , v5 , v6 , v7 } は
頂点被覆である
v7
v3
{v1 , v2 , v3 , v5 , v8 } は
頂点被覆ではない
離散最適化基礎論 (11)
v1
v8
2015 年 1 月 9 日
v5
v3
v7
{v2 , v3 , v4 , v5 , v6 , v7 } は
最小頂点被覆ではない
頂点被覆の頂点は，それに接続する辺を覆う (被覆する)
岡本 吉央 (電通大)
v8
v5
v3
岡本 吉央 (電通大)
v7
{v1 , v2 , v5 , v7 , v8 } は
最小頂点被覆である
最小頂点被覆問題は NP 困難問題
31 / 43
v6
v4
v1
v5
v7
v2
v6
v4
v1
v5
v3
v6
v4
離散最適化基礎論 (11)
(Karp 1972)
2015 年 1 月 9 日
32 / 43
整数性ギャップ：下界
最小重み頂点被覆問題
整数性ギャップ：下界
最小重み頂点被覆問題の定式化
最小重み頂点被覆問題
最小重み頂点被覆問題の線形計画緩和
無向グラフ G = (V , E )，非負頂点重み関数 w : V → R
無向グラフ G = (V , E )，非負頂点重み関数 w : V → R
最小重み頂点被覆問題の定式化
(P) の線形計画緩和
(P) minimize
∑
w (v )yv
∑
(LP) minimize
v ∈V
subject to
∑
w (v )yv
v ∈V
yv ≥ 1
(∀ e ∈ E ),
∑
subject to
v ∈e
yv ∈ {0, 1}
yv ≥ 1
(∀ e ∈ E ),
0 ≤ yv ≤ 1
(∀ v ∈ V )
v ∈e
(∀ v ∈ V )
このとき，
(P) の整数性ギャップ = max
w ≥0
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
岡本 吉央 (電通大)
33 / 43
最小重み頂点被覆問題
(P) の最適値
(LP) の最適値
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
最小重み頂点被覆問題
最小重み頂点被覆問題の整数性ギャップ (下界)
最小重み頂点被覆問題の整数性ギャップ (下界)：証明
最小重み頂点被覆問題の定式化 (P) を考える
証明：すべての 2 頂点間に辺があるグラフ (完全グラフ) を考える
I すべての頂点 v ∈ V に対して w (v ) = 1 のときを考える
命題
任意の n ≥ 2 に対して
(P) の整数性ギャップ ≥ 2 −
2
n
I
次の 2 つを証明する
1
(P) の最適値 = n − 1
2
(LP) の最適値 ≤ n/2
34 / 43
を満たすような頂点数 n のグラフが存在する
このとき，
証明の方針
I
そのようなグラフを構成すればよい
w ≥0
≥
≥
岡本 吉央 (電通大)
離散最適化基礎論 (11)
整数性ギャップ：下界
2015 年 1 月 9 日
岡本 吉央 (電通大)
35 / 43
最小重み頂点被覆問題
離散最適化基礎論 (11)
整数性ギャップ：下界
最小重み頂点被覆問題の整数性ギャップ (下界)：証明 (2)
36 / 43
最小重み頂点被覆問題
示したいこと (2) ：(LP) の最適値 ≤ n/2
I
(P) の目的関数値は必ず整数であり，それは頂点被覆の要素数
I
要素数が n − 2 以下の頂点部分集合 S を考えると，
S に端点を持たない辺が存在する
I
つまり，S は頂点被覆ではなく，(P) の最適値 ≥ n − 1
I
一方，要素数 n − 1 の頂点被覆は存在するので，(P) の最適値 ≤ n − 1
I
したがって，(P) の最適値 = n − 1
I
(LP) に対する次の許容解 y を考える
yv = 1/2
I
I
辺 e ∈ E の端点が a, b ∈ V であるとき，
∑
yv = ya + yb = 1/2 + 1/2 = 1 ≥ 1
v ∈e
離散最適化基礎論 (11)
2015 年 1 月 9 日
(∀ v ∈ V )
これが本当に許容解であることを確認する
S
整数性ギャップ：下界
2015 年 1 月 9 日
最小重み頂点被覆問題の整数性ギャップ (下界)：証明 (3)
示したいこと (1) ：(P) の最適値 = n − 1
岡本 吉央 (電通大)
(P) の最適値
(LP) の最適値
w = 1 のときの (P) の最適値
w = 1 のときの (LP) の最適値
n−1
2
=2−
n/2
n
(P) の整数性ギャップ = max
∑
I
この許容解 y の目的関数値 =
I
したがって，(LP) の最適値 ≤ 許容解 y の目的関数値 = n/2
岡本 吉央 (電通大)
37 / 43
最小重み頂点被覆問題
v ∈V
yv = n/2
離散最適化基礎論 (11)
2015 年 1 月 9 日
38 / 43
2015 年 1 月 9 日
40 / 43
今日のまとめ
目次
最小重み頂点被覆問題の定式化 (P) を考える
いま証明した命題
任意の n ≥ 1 に対して
2
(P) の整数性ギャップ ≥ 2 −
n
1
ここまでのまとめ と ここからの話
2
整数性ギャップ：定義
3
整数性ギャップ：下界
最大重みマッチング問題
最小重み頂点被覆問題
4
今日のまとめ
を満たすような頂点数 n のグラフが存在する
次回証明する命題
任意のグラフに対して
(P) の整数性ギャップ ≤ 2
つまり，完全グラフが最も整数性ギャップの大きい例となっている
I この意味で，
「最小重み頂点被覆問題の整数性ギャップは 2 に等しい」
ということがある
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
39 / 43
岡本 吉央 (電通大)
離散最適化基礎論 (11)
今日のまとめ
今日の目標
今日の目標
整数性ギャップについて，次を理解する
I
整数性ギャップの定義
I
整数性ギャップの重要性
I
整数性ギャップに対する下界の導出法
岡本 吉央 (電通大)
離散最適化基礎論 (11)
2015 年 1 月 9 日
41 / 43