離散最適化基礎論 (9) 2014 年 12 月 12 日 演習問題 岡本 吉央

離散最適化基礎論 (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