1. No category

離散最適化基礎論 (9)
演習問題
2014 年 12 月 12 日
岡本 吉央
提出締切： 2014 年 12 月 19 日
今回の演習問題はすべて，最小費用全域木問題を扱う．最
とにする．
小費用全域木問題では，無向グラフ G = (V, E) と非負辺費
minimize
用関数 c : E → R が入力として与えられたとき，G の全域
subject to
とは，その辺の費用の和であるとする．
∑
xe ≤ |C| − 1
∑
題としての定式化として，次のものを考え，(P1) と呼ぶこ
xe = |V | − 1,
e∈E
xe ∈ {0, 1}
とにする．
subject to
(∀ e ∈ E)
次の図で表される入力を考える．
c(e)xe
1
e∈E
∑
(∀ C : G の閉路),
e∈C
復習問題 9.1 最小費用全域木問題に対する 01 整数計画問
∑
c(e)xe
e∈E
木で費用が最小のものを出力する．ただし，全域木の費用
minimize
∑
xe ≤ |C| − 1
3
(∀ C : G の閉路),
1 1
1
1
e∈C
∑
xe ≥ 1
(∀ S ⊆ V : S 6= ∅, S 6= V ),
1
e∈δ(S)
xe ∈ {0, 1}
(∀ e ∈ E).
ただし，各辺の横に書かれている数がその辺の費用を表す
ものとする．
ただし，δ(S) は S に一方の端点，V − S にもう一方の端点
1. 上の図で表される入力に対して，定式化 (P2) によっ
を持つ辺全体の集合を表す．
て得られる 01 整数計画問題を具体的に書き下してみ
次の図で表される入力を考える．
よ．その際，グラフの各辺には適当な名前を与えて，
1
区別できるようにせよ．また，最適解の 1 つと最適
2
3
1
値を答えよ．(ヒント：Kruskal のアルゴリズムなど，
最小費用全域木問題に対するアルゴリズムを用いても
2
よい．)
ただし，各辺の横に書かれている数がその辺の費用を表す
2. 小問 1 で得られた定式化の線形計画緩和 (LP2) を書
き下してみよ．
ものとする．
1. 上の図で表される入力に対して，定式化 (P1) によっ
て得られる 01 整数計画問題を具体的に書き下してみ
よ．その際，グラフの各辺には適当な名前を与えて，
区別できるようにせよ．また，最適解の 1 つと最適
値を答えよ．(ヒント：Kruskal のアルゴリズムなど，
最小費用全域木問題に対するアルゴリズムを用いても
3. (LP2) の許容解で，その目的関数値が (P2) の最適値
未満となるものを見つけよ．
復習問題 9.3 最小費用全域木問題に対する 01 整数計画問
題としての定式化として，次のものを考え，(P3) と呼ぶこ
とにする．
よい．)
minimize
2. 小問 1 で得られた定式化の線形計画緩和 (LP1) を書
∑
c(e)xe
e∈E
き下してみよ．
subject to
3. (LP1) の許容解で，その目的関数値が (P1) の最適値
∑
xe ≥ 1
(∀ S ⊆ V : S 6= ∅, S 6= V ),
e∈δ(S)
∑
未満となるものを見つけよ．
xe = |V | − 1,
e∈E
xe ∈ {0, 1}
復習問題 9.2 最小費用全域木問題に対する 01 整数計画問
題としての定式化として，次のものを考え，(P2) と呼ぶこ
(∀ e ∈ E)
次の図で表される入力を考える．
1
3
2
3
2
2
3
ただし，各辺の横に書かれている数がその辺の費用を表す
ものとする．
1. 上の図で表される入力に対して，定式化 (P3) によっ
て得られる 01 整数計画問題を具体的に書き下してみ
よ．その際，グラフの各辺には適当な名前を与えて，
区別できるようにせよ．また，最適解の 1 つと最適
値を答えよ．(ヒント：Kruskal のアルゴリズムなど，
最小費用全域木問題に対するアルゴリズムを用いても
よい．)
2. 小問 1 で得られた定式化の線形計画緩和 (LP3) を書
き下してみよ．
3. (LP3) の許容解で，その目的関数値が (P3) の最適値
未満となるものを見つけよ．
追加問題 9.4 問題 9.1 の設定において，その問において与
えられている入力とは違う入力で，(LP1) のある許容解の
目的関数値が (P1) の最適値未満となるものを見つけてみ
よ．特に，そのような入力の中で，頂点数が最小のものを
見つけてみよ．
2