今日の目標 今日の目標 離散最適化基礎論 第 9 回 完全双対整数性：全域木 (1) 最小費用全域木問題の持つ完全双対整数性を理解する 今日は準備 次回に証明 岡本 吉央 [email protected] 電気通信大学 2014 年 12 月 12 日 最終更新：2014 年 12 月 13 日 岡本 吉央 (電通大) 08:37 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 1 / 30 最小費用全域木問題の定式化：復習 離散最適化基礎論 (9) 2014 年 12 月 12 日 2 / 30 2014 年 12 月 12 日 4 / 30 最小費用全域木問題の定式化：復習 目次 木 無向グラフ G = (V , E ) 木とは？ 1 最小費用全域木問題の定式化：復習 G が木であるとは，次の 2 つの条件を満たすこと G は連結である G は閉路を部分グラフとして含まない 2 最小費用全域木問題と完全双対整数性 e b a 3 f d 今日のまとめ c i j l k h g 「連結である」ことの定義は次のスライドで 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 3 / 30 最小費用全域木問題の定式化：復習 離散最適化基礎論 (9) 最小費用全域木問題の定式化：復習 グラフの連結性 木の辺数 無向グラフ G = (V , E ) 木の辺数 グラフが連結であるとは？ 任意の木 G = (V , E ) に対して G が連結であるとは， 任意の 2 頂点 u, v ∈ V に対して，u から v へ至る道が存在すること |E | = |V | − 1 連結ではないグラフは非連結と呼ばれる e b a f e b a d c i j l k f c c i j l k 非連結グラフ i j l k h h g f d d h g e b a g |V | = 12, |E | = 11 連結グラフ 注： 「グラフが連結する」とは言わない 岡本 吉央 (電通大) 証明は『数理解析』又は『グラフとネットワーク』を参照 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 5 / 30 最小費用全域木問題の定式化：復習 離散最適化基礎論 (9) 2014 年 12 月 12 日 6 / 30 最小費用全域木問題の定式化：復習 グラフの全域木 最小費用全域木問題 無向グラフ G = (V , E ) 最小費用全域木問題とは？ 全域木とは？ 入力：無向グラフ G = (V , E )，非負辺費用関数 c : E → R G の全域木とは，G の部分グラフで次を満たすもの 出力：G の全域木で，費用が最小のもの 木である 頂点集合が V である v2 全張木，生成木とも呼ぶことがある 4 f i j l k 2 2 v8 5 3 1 v7 事実 h 岡本 吉央 (電通大) v6 1 v5 v3 c g 2 1 d 4 v4 5 v1 e b a 3 2 最小費用全域木問題は効率よく解くことができる (Kruskal ’56, Prim ’57) 離散最適化基礎論 (9) G が非連結であるとき，G の全域木は存在しない 効率よく = |V | と |E | に関する多項式時間で 2014 年 12 月 12 日 7 / 30 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 8 / 30 最小費用全域木問題の定式化：復習 最小費用全域木問題の定式化：復習 最小費用全域木問題：定式化 1 最小費用全域木問題：定式化 1 の例 記法：δ(S) = S に一方の端点，V − S にもう一方の端点を持つ 辺全体の集合 Variables xa 最小費用全域木問題：01 整数計画問題としての定式化 1 x∈ RE 1 xb は変数 xc xe 2 minimize 1 Costs 2 xd ∑ 3 xa , xb , xc , xd , xe ∈ R は変数 c(e)xe e∈E ∑ subject to xe ≤ |C | − 1 minimize (∀ C : G の閉路), subject to e∈C ∑ xe ≥ 1 2xa + xb + 3xc + 2xd + xe xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3, xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1, (∀ S ⊆ V : S = ∅, S = V ), xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1, e∈δ(S) xe ∈ {0, 1} (∀ e ∈ E ) xa , xb , xc , xd , xe ∈ {0, 1} これは正しい定式化 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 9 / 30 最小費用全域木問題の定式化：復習 離散最適化基礎論 (9) 2014 年 12 月 12 日 最小費用全域木問題の定式化：復習 全域木の性質 最小費用全域木問題：定式化 2 木であるための必要十分条件 最小費用全域木問題：01 整数計画問題としての定式化 2 無向グラフ G = (V , E ) に対して，次の 3 つは同値 x ∈ RE は変数 1 G は閉路を含まない，かつ，G は連結である (つまり，G は木である) 2 G は閉路を含まない，かつ，|E | = |V | − 1 である 3 minimize 1 に基づいている 定式化 2 は 2 に基づいて行う 定式化 3 は 3 に基づいて行う ∑ c(e)xe e∈E G は連結である，かつ，|E | = |V | − 1 である 定式化 1 は 10 / 30 subject to ∑ xe ≤ |C | − 1 (∀ C : G の閉路), e∈C ∑ xe = |V | − 1, e∈E xe ∈ {0, 1} (∀ e ∈ E ) これも正しい定式化 証明は『数理解析』又は『グラフとネットワーク』を参照 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 11 / 30 最小費用全域木問題の定式化：復習 離散最適化基礎論 (9) 最小費用全域木問題：定式化のまとめ 最小費用全域木問題：01 整数計画問題としての定式化 3 定式化 1 minimize ∑ c(e)xe ∑ 14 / 30 閉路に対する制約 と 辺数に対する等式制約 xe ≥ 1 定式化 3 (∀ S ⊆ V : S = ∅, S = V ), カットに対する制約 と 辺数に対する等式制約 e∈δ(S) ∑ 2014 年 12 月 12 日 閉路に対する制約 と カットに対する制約 定式化 2 e∈E subject to 12 / 30 最小費用全域木問題の定式化：復習 最小費用全域木問題：定式化 3 x ∈ RE は変数 2014 年 12 月 12 日 xe = |V | − 1, 疑問 e∈E xe ∈ {0, 1} どの定式化が完全双対整数性を持つのだろうか？ (∀ e ∈ E ) これも正しい定式化 注意 同じ組合せ最適化問題を様々な方法で定式化できる 「よい定式化」と「悪い定式化」がある 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 13 / 30 岡本 吉央 (電通大) 最小費用全域木問題と完全双対整数性 離散最適化基礎論 (9) 最小費用全域木問題と完全双対整数性 目次 最小費用全域木問題：定式化 1 の例 1 xb 1 最小費用全域木問題の定式化：復習 Variables xa xc xe 2 Costs xa , xb , xc , xd , xe ∈ R は変数 最小費用全域木問題と完全双対整数性 minimize subject to 3 1 2 xd 2 3 今日のまとめ 2xa + xb + 3xc + 2xd + xe xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3, xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1, xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1, xa , xb , xc , xd , xe ∈ {0, 1} (xa , xb , xc , xd , xe ) = (1, 1, 0, 0, 1) は最適解で，最適値は 4 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 15 / 30 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 16 / 30 最小費用全域木問題と完全双対整数性 最小費用全域木問題と完全双対整数性 最小費用全域木問題：定式化 1 の例 — 線形計画緩和 定式化 1 1 xb Variables xa 最小費用全域木問題：定式化のまとめ 閉路に対する制約 と カットに対する制約 xe xc 2 1 3 Costs 閉路に対する制約 と 辺数に対する等式制約 2 xd →持たない 定式化 2 定式化 3 xa , xb , xc , xd , xe ∈ R は変数 minimize subject to カットに対する制約 と 辺数に対する等式制約 2xa + xb + 3xc + 2xd + xe 疑問 xa + xb + xc ≤ 2, xc + xd + xe ≤ 2, xa + xb + xe + xd ≤ 3, どの定式化が完全双対整数性を持つのだろうか？ xa + xb ≥ 1, xb + xc + xe ≥ 1, xd + xe ≥ 1, xa + xc + xd ≥ 1, xb + xc + xd ≥ 1, xa + xc + xe ≥ 1, xa + xb + xd + xe ≥ 1, 0 ≤ xa , xb , xc , xd , xe ≤ 1 (xa , xb , xc , xd , xe ) = (1/2, 1/2, 0, 1/2, 1/2) は許容解で，目的関数値は 3 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 17 / 30 最小費用全域木問題と完全双対整数性 1 minimize 1 1 1 1 3 xg 1 Costs Variables xa xa + xb + xc + xd + xe + xf + 3xg minimize xa + xb + xf ≤ 2, xb + xc + xe ≤ 2, xc + xd + xf ≤ 2, subject to 1 xb 3 xg xc xe xf xd 1 xc 1 1 1 1 Costs xa + xb + xc + xd + xe + xf + 3xg xa + xb + xf ≤ 2, xb + xc + xe ≤ 2, xc + xd + xf ≤ 2, subject to xa + xd + xe ≤ 2, xa + xb + xc + xd ≤ 3, xa + xd + xe ≤ 2, xa + xb + xc + xd ≤ 3, xa + xc + xe + xf ≤ 3, xb + xd + xe + xf ≤ 3, xa + xc + xe + xf ≤ 3, xb + xd + xe + xf ≤ 3, xa + xb + xc + xd + xe + xf + xg = 4, xa + xb + xc + xd + xe + xf + xg = 4, xa , xb , xc , xd , xe , xf , xg ∈ {0, 1} 0 ≤ xa , xb , xc , xd , xe , xf , xg ≤ 1 (xa , xb , xc , xd , xe , xf , xg ) = (1, 1, 1, 0, 0, 0, 1) は最適解で，最適値は 6 岡本 吉央 (電通大) 18 / 30 最小費用全域木問題：定式化 2 の例 — 線形計画緩和 xb Variables xa 2014 年 12 月 12 日 最小費用全域木問題と完全双対整数性 最小費用全域木問題：定式化 2 の例 xe xf xd 離散最適化基礎論 (9) 離散最適化基礎論 (9) 2014 年 12 月 12 日 (xa , xb , xc , xd , xe , xf , xg ) = (1, 1/2, 1, 1/2, 1/2, 1/2, 0) は最適解で， 最適値は 4 岡本 吉央 (電通大) 19 / 30 最小費用全域木問題と完全双対整数性 離散最適化基礎論 (9) 2014 年 12 月 12 日 20 / 30 最小費用全域木問題と完全双対整数性 最小費用全域木問題：定式化のまとめ 最小費用全域木問題：定式化 3 の例 3 xb 定式化 1 2 xc 閉路に対する制約 と カットに対する制約 Variables xa →持たない 3 xf xd 定式化 2 xe 閉路に対する制約 と 辺数に対する等式制約 →持たない 定式化 3 minimize Costs 2 3 3xa + 3xb + 2xc + 2xd + 3xe + 2xf xa + xb ≥ 1, xb + xc + xf ≥ 1, xc + xd ≥ 1, subject to カットに対する制約 と 辺数に対する等式制約 2 xd + xe + xf ≥ 1, xa + xe ≥ 1, xa + xc + xf ≥ 1, 疑問 xa + xb + xc + xd ≥ 1, xa + xb + xd + xe + xf ≥ 1, どの定式化が完全双対整数性を持つのだろうか？ xb + xe ≥ 1, xb + xd + xf ≥ 1, xb + xc + xd + xe ≥ 1, xa + xb + xc + xe + xf ≥ 1, xc + xe + xf ≥ 1, xa + xc + xf ≥ 1, xa + xd + xf ≥ 1, xa + xb + xc + xd + xe + xf = 4, xa , xb , xc , xd , xe , xf ∈ {0, 1} (xa , xb , xc , xd , xe , xf ) = (1, 1, 1, 1, 0, 0) は最適解で，最適値は 10 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 岡本 吉央 (電通大) 21 / 30 最小費用全域木問題と完全双対整数性 最小費用全域木問題：定式化のまとめ 3 xf 定式化 1 2 xc xd xe subject to 22 / 30 3 xb minimize 2014 年 12 月 12 日 最小費用全域木問題と完全双対整数性 最小費用全域木問題：定式化 3 の例 — 線形計画緩和 Variables xa 離散最適化基礎論 (9) 2 Costs 閉路に対する制約 と カットに対する制約 2 →持たない 定式化 2 3 閉路に対する制約 と 辺数に対する等式制約 3xa + 3xb + 2xc + 2xd + 3xe + 2xf →持たない 定式化 3 xa + xb ≥ 1, xb + xc + xf ≥ 1, xc + xd ≥ 1, カットに対する制約 と 辺数に対する等式制約 xd + xe + xf ≥ 1, xa + xe ≥ 1, xa + xc + xf ≥ 1, xa + xb + xc + xd ≥ 1, xa + xb + xd + xe + xf ≥ 1, 疑問 xb + xe ≥ 1, xb + xd + xf ≥ 1, xb + xc + xd + xe ≥ 1, どの定式化が完全双対整数性を持つのだろうか？ xa + xb + xc + xe + xf ≥ 1, xc + xe + xf ≥ 1, →持たない 解答：どれも持たない xa + xc + xf ≥ 1, xa + xd + xf ≥ 1, xa + xb + xc + xd + xe + xf = 4, 0 ≤ xa , xb , xc , xd , xe , xf ≤ 1 (xa , xb , xc , xd , xe , xf ) = (1/2, 1/2, 1, 1, 1/2, 1/2) は許容解で，最適値は 9.5 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 23 / 30 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 24 / 30 最小費用全域木問題と完全双対整数性 今日のまとめ 最小費用全域木問題：次回予告 目次 次回予告 完全双対整数性を持つ最小費用全域木問題の定式化 1 最小費用全域木問題の定式化：復習 2 最小費用全域木問題と完全双対整数性 3 今日のまとめ それは，ここで考えた 3 つの定式化とは違う 証明には Kruskal のアルゴリズムを用いる 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 25 / 30 岡本 吉央 (電通大) 離散最適化基礎論 (9) 今日のまとめ 2014 年 12 月 12 日 26 / 30 今日のまとめ 今日の目標 この講義のねらい：流れ 今日の目標 solution 最小費用全域木問題の持つ完全双対整数性を理解する combinatorial optimization problem 今日は準備 次回に証明 3 3 5 4 6 8 6 4 2 8 1 3 2 7 integer program 1 x2 2 2 1 good linear program+ structure x1 −2x2 =−2 −2x1 −3x2 =−6 1 x2 2 2 1 x1 −2x2 =−2 −2x1 −3x2 =−6 x1 O formulation x1 O 3 3 relaxation ■ 組合せ最適化問題を整数計画問題として定式化 ■ 整数計画問題を線形計画問題として緩和 ■ 線形計画問題の「よい」構造を観察 ■ 線形計画問題を用いて組合せ最適化問題の解決 ←次回もココ 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 27 / 30 岡本 吉央 (電通大) 離散最適化基礎論 (9) 2014 年 12 月 12 日 28 / 30
© Copyright 2024 ExpyDoc
