【しっかり学ぶ数理最適化】4.5.3~4.5.6

2025年度後期輪読会 #12 (2026/1/8) 数理最適化4.5.3~4.5.6 (近似解法) 京都大学 理学部数理科学系 3回 千葉 一世 0

アジェンダ ◼ 最大カット問題 ◼ 巡回セールスマン問題 ◼ 頂点被覆問題 ◼ ナップサック問題 1

アジェンダ ◼ 最大カット問題 ◼ 巡回セールスマン問題 ◼ 頂点被覆問題 ◼ ナップサック問題 2

最大カット問題 最大カット問題：無向グラフ 𝐺 = 𝑉, 𝐸 と重み 𝑐𝑒 に対して、カット重み 𝑐 𝑆 を最大化させる 頂点集合 𝑆 を求める問題 最小カット問題では多項式アルゴリズムが知られるが、最大カット問題はNP困難である。 1 2 乱択法：各頂点を の確率でSに加えるというランダム性を用いた単純な手法 乱択法では近似比率の期待値で 1 を達成する。 2 ∵ 𝑂𝑃𝑇(𝐼)で最大カット問題の最適値を表すとして 3

最大カット問題 (貪欲法) 1 乱択法では近似保証はないため脱乱択化をして、 -近似解法の貪欲法を考える。 2 ランダムに選ぶだけでは偏りが出来てしまうため、偏らないように入れるか入れないかを決める。 𝑣 ∈ 𝑉を𝑆と𝑆に割り振っていき、 𝑆に入れた時の重み増加量 Σ𝑒∈𝛿(𝑣,𝑆) 𝑐𝑒 と、 𝑆に入れた時の重み増加量 Σ𝑒∈𝛿 𝑣,𝑆 𝑐𝑒 の大きい方に入れる 計算量は全点と全辺分計算し、𝑂( 𝑉 + |𝐸|) 最大カット問題の貪欲法 Step1: S = ∅, 𝑆 = ∅ とする。 Step2: S ∪ 𝑆 = 𝑉 なら終了。 Step3: 頂点𝑣 ∈ 𝑉 ∖ (S ∪ 𝑆)を取り、Σ𝑒∈𝛿(𝑣,𝑆) 𝑐𝑒 ≥ Σ𝑒∈𝛿 𝑣,𝑆 𝑐𝑒 なら、𝑆 ← 𝑆 ∪ 𝑣 とし、 そうでなければ、 𝑆 ← 𝑆 ∪ 𝑣 とする。 Step2に戻る。 近似比率は、全点について、追加する際の Σ𝑒∈𝛿(𝑣,𝑆) 𝑐𝑒 ≥ Σ𝑒∈𝛿 𝑣,𝑆 𝑐𝑒 の総和を取って、 1 1 𝐴 𝐼 ≥ Σ𝑒∈𝐸 𝑐𝑒 − 𝐴 𝐼 ∴ 𝐴 𝐼 ≥ Σ𝑒∈𝐸 𝑐𝑒 ≥ 𝑂𝑃𝑇(𝐼) 2 2 4

最大カット問題 (局所探索法) 1 最大カット問題に対する -近似解法の局所探索法 2 初期の頂点集合を決め、点を除く or 追加する操作を重みが増加する限り続ける手法 最終的に、全ての点について除外・追加で重みが増加し無くなれば終了する。 最大カット問題の局所探索法 Step1: Sを取り、𝐿 = 𝑉とする。 Step2: 頂点𝑣 ∈ 𝐿を取り、𝐿 ← 𝐿 ∖ 𝑣 とする。 Step3: 𝑣 ∈ 𝑆 かつ 𝑐 𝑆 ∖ 𝑣 > 𝑐 𝑆 なら、𝑆 ← 𝑆 ∖ 𝑣 , 𝐿 = 𝑉 ∖ {𝑣}としてStep2に戻る。 Step4: 𝑣 ∈ 𝑉 ∖ 𝑆 かつ 𝑐 𝑆 ∪ 𝑣 > 𝑐 𝑆 なら、𝑆 ← 𝑆 ∪ 𝑣 , 𝐿 = 𝑉 ∖ {𝑣}としてStep2に戻る。 Step5: 𝐿 = ∅ならば終了。そうでなければStep2に戻る。 最悪計算量は指数オーダーになり、多項式アルゴリズムではない 近似比率は、終了時点で ∀ 𝑣 ∈ 𝑆, 𝑐 𝑆 ∖ {𝑣 ) ≤ 𝑐(𝑆), 重みの変化量の不等式を任意の𝑣で総和して、 ∀ 𝑣 ∈ 𝑉 ∖ 𝑆, 𝑐(𝑆 ∪ 𝑣 ) ≤ 𝑐(𝑆) が成り立つ。 𝐴 𝐼 ≥ Σ𝑒∈𝐸 𝑐𝑒 − 𝐴 𝐼 1 1 ∴ 𝐴 𝐼 ≥ Σ𝑒∈𝐸 𝑐𝑒 ≥ 𝑂𝑃𝑇(𝐼) 2 2 5

最大カット問題 Goemans-Williamsアルゴリズム 近似比率 0.878で、未解決問題が成立するの仮定の下で最高の近似比率のアルゴリズム 超概略 1. 入れるか入れないかの二値変数を{-1,1}と考えて、単位ベクトルに緩和 2. 凸最適問題に帰着し、解を求める。 3. ランダムな超平面による分離を利用して単位ベクトルを丸める。 確率的な丸めを行うため、近似比率は期待値の意味だが、丸めの計算量は軽く反復可能 6

アジェンダ ◼ 最大カット問題 ◼ 巡回セールスマン問題 ◼ 頂点被覆問題 ◼ ナップサック問題 7

巡回セールスマン問題 近似であっても多項式アルゴリズムが存在しない事もある。 巡回セールスマン問題には、𝑃 ≠ 𝑁𝑃という仮定の下で近似比率が有限となるような 多項式アルゴリズムが存在しない。 Proof 𝑃 ≠ 𝑁𝑃であれば、ハミルトン閉路問題がNP完全問題である事を用いて、 巡回セールス問題の有限近似比率多項式アルゴリズムから、ハミルトン閉路問題の 多項式アルゴリズムを構成し矛盾を導く。 近似比率𝑟であるとして、無向グラフ𝐺 = (𝑉, 𝐸)に完全有向グラフを次のように構成 • 𝑢, 𝑣 ∈ 𝐸なら、𝑑𝑢𝑣 = 1 • 𝑢, 𝑣 ∉ 𝐸なら、𝑑𝑢𝑣 = 𝑟 𝑉 このグラフの巡回セールスマン問題の最適値は、 Gにハミルトン閉路が存在するなら、 𝑉 存在しないのであれば、𝑟 𝑉 + 1 以上となる。 従って、近似比率rの多項式アルゴリズムで得られた値が、𝑟|𝑉|以下かどうかで 無向グラフ𝐺のハミルトン閉路の存在が判定できてしまい、NP完全に矛盾. 8

巡回セールスマン問題 (木二重化法) 現実の巡回セールスマン問題では、2地点間の距離などを用いることが多く 任意の三点に対して重みの三角不等式が成り立つことが多い。 そのような重み付きグラフに限ったメトリック巡回セールスマン問題の近似解法を見る 木二重化法 最小全域木・オイラー閉路を利用した手法 計算量は 𝑂 𝐸 + 𝑉 log 𝑉 近似比率 2 巡回セールスマン問題の木二重化法 Step1: Step2: Step3: Step4: 最小全域木 T を求める。 T の辺を2本に置き換えた二重木 𝑇 ′ を取る。 𝑇 ′ からオイラー閉路を取る。 始点を決めてオイラー閉路をたどり、一度通ったことがある点は飛ばしながら 移動する巡回路を構成する。 オイラー閉路：全ての辺を一度だけ通る閉路 いわゆる一筆書き 存在するための必要十分条件は全て頂点が偶数次数 9

巡回セールスマン問題 (木二重化法) 計算量 最小全域木はプリム法で求め、𝑂 𝐸 + 𝑉 log 2 𝑉 オイラー閉路を求める・オイラー閉路から巡回路を構成は、𝑂 𝑉 で出来るので、 全体として、 𝑂 𝐸 + 𝑉 log 2 𝑉 近似比率 最適な巡回路は、一本の辺を除いて木となり、それより最小全域木の方が小さくなる。 ２倍化した最小全域木からショートカットするが、 三角不等式の条件より短くなっている。 改良版 近似比率は、オイラー閉路を求める際の二倍化に依り、 次数を偶数にするためには二倍化する必要はないため 3 2 奇数の物だけに注目した改良で近似比率 にできる。 10

巡回セールスマン問題 (最近追加法) 最小全域木のプリム法を修正した最近追加法・最近挿入法・最安挿入法を見る。 部分巡回路に順に点を追加していく手法で、追加する点と辺の修正法でバリエーションがある。 最近追加法 現在の巡回路の点集合のカットの中で最小のものを選び、達成する巡回路の頂点の隣と繋げる。 巡回セールスマン問題の最近追加法 Step1: 𝑣0 ∈ 𝑉を取り、min 𝑑𝑣0𝑢 𝑢 ∈ 𝑉 ∖ 𝑣0 } となる𝑣1 ∈ 𝑉 ∖ {𝑣0 }を求める。 𝑆 = 𝑣0 , 𝑣1 , 𝐻 = 𝑣0 , 𝑣1 , {𝑣0 , 𝑣1 } とする。 Step2: 𝑆 = 𝑉なら終了 Step3: min 𝑑𝑢𝑣 {𝑢, 𝑣} ∈ 𝛿(𝑆)} となる 𝑢∗ ∈ 𝑆, 𝑣 ∗ ∈ 𝑉 ∖ 𝑆を求める。 𝐻で𝑢∗ と隣接する𝑤を一つ選び、𝑆 ← 𝑆 ∪ 𝑣 ∗ , 𝐻 ← 𝐻 ∖ 𝑢∗ , 𝑤 ∪ 𝑢∗ , 𝑣 ∗ , 𝑣 ∗ , 𝑤 Step2に戻る。 11

巡回セールスマン問題 (最近挿入法) 最近挿入法 追加する点は最近追加法と同じく現在の巡回路の点集合のカットの中で最小のものを選び、 巡回路への追加は、単純な隣ではなく全ての追加の仕方を比較して小さいものを選ぶ 巡回セールスマン問題の最近挿入法 Step1: 𝑣0 ∈ 𝑉を取り、min 𝑑𝑣0𝑢 𝑢 ∈ 𝑉 ∖ 𝑣0 } となる𝑣1 ∈ 𝑉 ∖ {𝑣0 }を求める。 𝑆 = 𝑣0 , 𝑣1 , 𝐻 = 𝑣0 , 𝑣1 , {𝑣0 , 𝑣1 } とする。 Step2: 𝑆 = 𝑉なら終了 Step3: min 𝑑𝑢𝑣 {𝑢, 𝑣} ∈ 𝛿(𝑆)} となる 𝑢∗ ∈ 𝑆, 𝑣 ∗ ∈ 𝑉 ∖ 𝑆を求める。 e = u, w ∈ 𝐻で、増加コスト𝑑𝑢𝑣 ∗ + 𝑑𝑣 ∗𝑤 − 𝑑𝑢𝑤 が最小となる{𝑢, 𝑤}を求め、 𝑆 ← 𝑆 ∪ 𝑣 ∗ , 𝐻 ← 𝐻 ∖ 𝑢, 𝑤 ∪ 𝑢, 𝑣 ∗ , 𝑣 ∗ , 𝑤 とする。 Step2に戻る。 12

巡回セールスマン問題 (最安挿入法) 最安挿入法 追加の仕方だけでなく、追加する点と追加の仕方の両方について探索し最小となる組合せを選ぶ。 巡回セールスマン問題の最安挿入法 Step1: Step2: Step3: 𝑣0 ∈ 𝑉を取り、min 𝑑𝑣0𝑢 𝑢 ∈ 𝑉 ∖ 𝑣0 } となる𝑣1 ∈ 𝑉 ∖ {𝑣0 }を求める。 𝑆 = 𝑣0 , 𝑣1 , 𝐻 = 𝑣0 , 𝑣1 , {𝑣0 , 𝑣1 } とする。 𝑆 = 𝑉なら終了 𝑣 ∗ ∈ 𝑉 ∖ 𝑆と、e = u, w ∈ 𝐻で、増加コスト𝑑𝑢𝑣 ∗ + 𝑑𝑣 ∗𝑤 − 𝑑𝑢𝑤 が最小となる 𝑣 ∗ , 𝑢, 𝑤 を求め、 𝑆 ← 𝑆 ∪ 𝑣 ∗ , 𝐻 ← 𝐻 ∖ 𝑢, 𝑤 ∪ 𝑢, 𝑣 ∗ , 𝑣 ∗ , 𝑤 とする。 Step2に戻る。 13

巡回セールスマン問題 最悪な場合で測ると、計算量𝑂 𝑛2 , 近似比率２ で同じだが、平均的な性能では 計算量 ： 最近追加法 < 最近挿入法 < 最安挿入法 近似性能 ： 最近追加法 < 最近挿入法 < 最安挿入法 となり、性能と計算量にトレードオフがある。 14

アジェンダ ◼ 最大カット問題 ◼ 巡回セールスマン問題 ◼ 頂点被覆問題 ◼ ナップサック問題 15

頂点被覆問題 無向グラフ𝐺 = (𝑉, 𝐸)と、部分集合 𝑆 ⊂ 𝑉 に対して、 ∀ Sが頂点被覆 ⇔ 𝑒 ∈ 𝐸 について端点のどちらかが 𝑆 の元となる 頂点被覆問題：頂点𝑣 ∈ 𝑉に対して重み𝑐𝑣 が与えられた際に、重み最小の頂点被覆を求める問題 NP困難であることが知られている。 貪欲法 被覆集合になるまで、頂点を追加していく手法 追加する際には、各点の費用効果が一番少ないものを選ぶ。 費用効果は、頂点を追加した際に追加される一本当たりのコスト増加量 𝑐𝑣 𝛿 𝑣 ∖ 𝐸′ を表す。 頂点被覆問題の貪欲法 Step1: Step2: S = ∅, 𝐸 ′ = ∅とする。 𝐸 = 𝐸 ′ なら終了 Step3: 𝑣 ∗ = 𝑎𝑟𝑔𝑚𝑖𝑛 𝑆←𝑆∪ 𝑐𝑣 | 𝑣 ∈ 𝑉 ∖ 𝑆 を求め、 𝛿 𝑣 ∖𝐸 ′ 𝑣 ∗ , E′ ← 𝐸 ′ ∪ 𝛿(𝑣 ∗ )としてStep2に戻る。 16

頂点被覆問題 (貪欲法) 貪欲法は(V, E)に対して近似比率は 𝐻 𝐸 1 2 1 3 (𝐻𝑘 = 1 + + + ⋯ + 1 𝑘 ∶ 調和級数の部分和) 辺数に依存し、調和級数は発散するため近似比率は有限ではない。 proof 辺集合𝐸を貪欲法で追加した順に並べ、𝑒1 , 𝑒2 , … , 𝑒 𝐸 とする。 𝑐𝑣 𝐸 σ 𝑒 ∈ 𝐸を追加した際の費用効果を 𝑝𝑒 = として、𝐴 𝐼 = ′ 𝑘=1 𝑝𝑒𝑘 𝛿 𝑣 ∖𝐸 最適解を𝑆 ∗ として、𝑒𝑘 が選ばれる前の段階で𝑆 ∗ ∖ 𝑆 ≠ ∅によって、(残りの辺)≥ 𝐸 − 𝑘 + 1 本を 𝑂𝑃𝑇(𝐼)以下のコストで被覆できるはずで、費用効果が 𝑂𝑃𝑇 𝐼 𝑂𝑃𝑇 𝐼 以下の頂点が存在し、𝑝𝑒 𝑘 ≤ 𝐸 −𝑘+1 𝐸 −𝑘+1 ∴ 17

頂点被覆問題 (主双対法) 主双対法：線形計画緩和問題の双対問題を解くことにより求める手法 頂点ではなく辺を選んで、端点のコストが小さい方を追加していく 頂点被覆問題の主双対法 Step1: Step2: Step3: 𝐸 ′ = ∅, 𝑆 = ∅, 𝑐ഥ𝑣 = 𝑐𝑣 𝑣 ∈ 𝑉 , 𝑦𝑒 = 0 (𝑒 ∈ 𝐸)とする。 𝐸 ′ = 𝐸 ならば終了。 𝑒 = 𝑢, 𝑣 ∈ 𝐸 ∖ 𝐸 ′ を選ぶ。(𝑐𝑢 ≥ 𝑐𝑣 とする。) 𝑦𝑒 ← 𝑦𝑒 + 𝑐ഥ𝑣 , 𝑐𝑢 ← 𝑐𝑢 − 𝑐ഥ𝑣 , 𝑐ഥ𝑣 ← 0, 𝑆 ← 𝑆 ∪ 𝑣 , 𝐸 ′ ← 𝐸 ′ ∪ 𝛿(𝑣)として、Step2に戻る。 • 計算量は、辺を選んで更新するだけなので 𝑂 𝐸 • 近似比率は 2 18

頂点被覆問題 (主双対法) 変数𝑥𝑣 を、頂点𝑣 ∈ 𝑉を選ぶかの二値変数として、次のように定式化できる。 整数条件を 𝑥𝑣 ≥ 0と緩和する。最小化より最適解は𝑥𝑣 ≤ 1となる。 その双対問題を考える。 19

頂点被覆問題 (主双対法) 線形計画緩和問題と双対問題の実行可能解 (𝑥, 𝑦)について、最適である必要十分条件は、 次の相補性条件を満たすことである。 相補性条件により、𝑐ഥ𝑣 𝑦 = 𝑐𝑣 − σ𝑒∈𝛿(𝑣) 𝑦𝑒 として、 定理4.15 𝑦を双対問題の極大解として、頂点集合 ത 𝑆 = 𝑣 ∈ 𝑉 𝑐ഥ𝑣 𝑦ത = 0} は頂点被覆問題の実行解となる。 proof 𝑆が実行可能解でないとすると、被覆されない𝑒′ = 𝑢, 𝑣 ∈ 𝐸が存在する。 定め方より、 𝜀 = min{𝑐𝑢 𝑦ത , 𝑐ഥ𝑣 𝑦ത } > 0 となり、 𝑦ത𝑒′ + 𝜀 𝑦′ = ቊ 𝑦ഥ𝑒 (𝑒 ∈ 𝐸 ∖ {𝑒′}) として、𝑦′は実行可能解で、 𝑦の極大性に矛盾 ത 20

頂点被覆問題 (主双対法) 𝑦を双対問題の極大解として、 ത 𝑆 = 𝑣 ∈ 𝑉 𝑐ഥ𝑣 𝑦ത = 0}, 𝑥𝑣 = 1 (𝑣 ∈ 𝑆)とすると、 ≤ 𝑶𝑷𝑻(𝑰) 従って、任意の極大解から近似コスト2の解が求まる。 求めるのは極大解で十分なので、単純に辺を選んで可能な限り重みをつけていくだけで求まる。 21

頂点被覆問題 (丸め法) 双対問題を考えず、線形計画緩和問題だけから考える方法も存在する。 丸め法 線型計画緩和問題の最適解 𝑥ҧ に対し、 とする。 これによって選ばれた頂点集合は頂点被覆となる。 • 近似比率は2となる。 𝑥𝑢 + 𝑥𝑣 ≥ 1より、どちらか一方は0.5以上で、必ず全ての辺が被覆される。 𝑂𝑃𝑇 𝐼 ≥ 22

アジェンダ ◼ 最大カット問題 ◼ 巡回セールスマン問題 ◼ 頂点被覆問題 ◼ ナップサック問題 23

ナップサック問題 ナップザック問題では、動的計画法や分枝限定法などで解くことが出来るが、 計算量が容量・価値の値に依存する擬多項式であり、場合によっては計算できない。 ∀ 𝜀 > 0に対し、近似比率 1 − 𝜀 の近似解法を考え、誤差で計算量を減らす。 一般に、 近似スキーム： 𝜀 > 0に対して、近似比率 1 − 𝜀, 1 + 𝜀 の近似解法を与える方法 𝜀を固定した時の近似解法が多項式時間アルゴリズムの時、多項式時間近似スキームと言い、 1 𝜀 更に、 に対しても多項式となる物を完全多項式時間近似スキームと言う。 ナップザック問題には、完全多項式時間近似スキームが存在する。 24

ナップサック問題 (近似スキーム) 動的計画法によるアルゴリズムで、計算量が価値の総和によるものがあり、擬多項式であるが 価値を定数倍して小さくするだけで最適解を変化させずに計算量を減らすことが出来る。 実際には、整数でないと適用できないので、整数に丸めるために誤差が発生する。 1 − 𝜀近似解法 𝑀= 𝜀𝑝𝑚𝑎𝑥 として、𝑝෥𝑗 = 𝑛 𝑝𝑗 𝑀 と重みを変え、この重みについて動的計画法を適用する。 計算量 動的計画法によるアルゴリズムの計算量は、 O(𝑛𝑃) (𝑃: 最適解の上界) より、 𝑝 𝑛 𝑚𝑎𝑥 が上界より、計算量は 𝑀 𝑂 𝑛3 𝜀 25

ナップサック問題 (近似スキーム) 近似比率1 − 𝜀 𝑝෥𝑗 = 𝑝𝑗 𝑀 より、𝑝෥𝑗 ≤ ∴ 𝑝𝑗 𝑀 ≤ 𝑝෥𝑗 + 1であり、実行可能解𝑥に対して、 𝑥 ′ ∶ 丸めた後の最適解 𝑥 ∗ ∶ 元の最適解 26