1. No category

離散最適化基礎論 (11)
演習問題
2015 年 1 月 9 日
岡本 吉央
提出締切： 2015 年 1 月 23 日
ただし，x ∈ RE が変数であり，δ(v) は頂点 v に接続する辺
復習問題 11.1 次の整数計画問題 (P) を考える．
全体の集合を表す．この問題 (P) の線形計画緩和 (LP) は
c> x
(P) maximize
以下の問題である．
x1 + 2x2 ≤ 2,
subject to
2x1 + x2 ≤ 2,
(LP)
maximize
subject to
x1 , x2 ∈ Z.
c> x
subject to
x1 + 2x2 ≤ 2,
max
w≥0
2x1 + x2 ≤ 2,
が
x1 ≥ 0, x2 ≥ 0.
3
2
G = (V, E) と非負頂点重み関数 w : V → R が入力として
与えられ，w に関する G の最小重み頂点被覆を出力する．
(LP) の最適値
(P) の最適値
次の問題 (P) は，最小重み頂点被覆問題を整数計画問題
として定式化したものである．
(P)
復習問題 11.2 次の整数計画問題 (P) を考える．
minimize
subject to
w(v)yv
∑
yv ≥ 1
(∀ e ∈ E),
yv ∈ {0, 1}
(∀ v ∈ V ).
v∈e
Ax ≤ b,
x ∈ Zn .
ただし，y ∈ RV が変数である．この問題 (P) の線形計画緩
ただし，変数は x であり，A ∈ Rm×n , b ∈ Rm , c ∈ Rn は定
和 (LP) は以下の問題である．
数である．この問題の線形計画緩和 (LP) は以下の問題で
ある．
(LP) minimize
subject to
∑
v∈V
c> x
maximize
(LP) の最適値
(P) の最適値
以上であるようなグラフ G が存在することを証明せよ．
が何であるか，定めよ．
(LP)
(∀ e ∈ E).
復習問題 11.4 最小重み頂点被覆問題では，無向グラフ
問題 (P) の整数性ギャップ，つまり，
subject to
(∀ v ∈ V ),
このとき，問題 (P) の整数性ギャップ，つまり，
maximize
(P) maximize
xe ≤ 1
0 ≤ xe ≤ 1
線形計画緩和 (LP) は以下の問題である．
c≥0
∑
e∈δ(v)
ただし，x1 , x2 が変数であり，c ∈ R2 は定数である．その
max
xe
e∈E
x1 ≥ 0, x2 ≥ 0,
(LP)
∑
>
∑
w(v)yv
v∈V
c x
subject to
Ax ≤ b.
∑
yv ≥ 1
(∀ e ∈ E),
0 ≤ yv ≤ 1
(∀ v ∈ V )
v∈e
問題 (LP) の許容領域が整凸多面体であるとき，(P) の整数
性ギャップが 1 となることを証明せよ．
このとき，任意の自然数 n ≥ 2 に対して問題 (P) の整数性
復習問題 11.3 最大重みマッチング問題では，無向グラフ
ギャップ，つまり，
G = (V, E) と非負辺重み関数 w : E → R が入力として与え
られ，w に関する G の最大重みマッチングを出力する．
max
w≥0
次の問題 (P) は，最大重みマッチング問題を整数計画問
が2−
題として定式化したものである．
∑
(P) maximize
xe
2
n
(P) の最適値
(LP) の最適値
以上であるような頂点数 n のグラフ G が存在する
ことを証明せよ．
e∈E
subject to
∑
xe ≤ 1
(∀ v ∈ V ),
(裏に続く)
e∈δ(v)
xe ∈ {0, 1}
(∀ e ∈ E).
1
追加問題 11.5 問題 11.3 にある問題 (P) と (LP) を考え
る．次の図に挙げるグラフを入力とするとき，(P) の整数
性ギャップが
5
4
以上となることを証明せよ．
追加問題 11.6 問題 11.3 にある問題 (P) と (LP) を考え
る．次の図に挙げるグラフを入力とするとき，(P) の整数
性ギャップが
8
7
以上となることを証明せよ．
追加問題 11.7 問題 11.4 にある問題 (P) と (LP) を考え
る．次の図に挙げるグラフを入力とするとき，(P) の整数
性ギャップが
4
3
以上となることを証明せよ．
2