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