【しっかり学ぶ数理最適化】4.3.3

2025 年後期輪読会 #10 (12/25) しっかり学ぶ数理最適化 4.3.3 ネットワークフロー 京都大学 工学部 情報学科 宮前明生 0

アジェンダ ◼ 最大流問題 ◼ 最小費用流問題 1

アジェンダ ◼ 最大流問題 ◼ 最小費用流問題 2

最大流問題：最大流問題とは 前提 • 入口となる頂点𝑠と出口となる頂点𝑡が存在する • 辺には流量𝑥𝑒 と容量𝑢𝑒 が定義される（整数） • 入口から出口に流れるフローの総量𝑓を最大化する問題 条件 1. 入口𝑠について、流出する総量から流入する総量を引くとフローの総量𝑓 2. 入口𝑠と出口𝑡を除いた頂点𝑣について、流出する総量と流入する総量は等しい 3. 出口𝑡について、流出する総量から流入する総量を引くとフローの総量−𝑓 3

最大流問題：増加路法 残余ネットワークは以下の容量を持つ有向グラフ • • 頂点𝑢から頂点𝑣に流せるフローの残り容量𝑢𝑒 − 𝑥𝑒 、これは頂点𝑢から頂点𝑣の方向 頂点𝑣から頂点𝑢に押し戻せるフローの残り容量𝑥𝑒 、これは頂点𝑣から頂点𝑢の方向 増加路とは、残余ネットワークで入口から出口までの方向に流れる経路 増加路法 1. 残余ネットワークの増加路があるか探す（なければ終了） 2. 見つけた増加路上で可能な限りフローを増加させる 4

最大流問題：増加路法の実行例 5

最大流問題：増加路法の計算量と最小カット問題 増加路法の計算量 流量𝑥𝑒 と容量𝑢𝑒 が整数なので、1回の反復で少なくとも流量は1増える 容量𝑢𝑒 の最大値を𝑈とすると、頂点𝑠から出る辺の数は高々|𝑉| − 1、フローの最大量は(|𝑉| − 1)𝑈、 反復回数の上限も(|𝑉| − 1)𝑈回 • 深さ優先探索や幅優先探索を用いれば、増加路は𝑂(|𝑉| + |𝐸|)で求められる。計算量は𝑂(|𝑉||𝐸|𝑈) 最小カット問題 • • • 頂点集合𝑉を𝑆と𝑇に分割し、 𝑆から𝑇への容量を最小化する問題 最大フロー最小カット定理 ・最大フローの量と最小カットの容量は等しい 6

最大流問題：最大流問題の応用①2部グラフのマッチング問題 2部グラフのマッチング問題 • 2部グラフの頂点間で、頂点を重複させずに最大何本の辺（ペア）を結べるか 2部グラフのマッチング問題から最大流問題へ • 2部グラフに入口𝑠と出口𝑡を追加し、 𝑠から全ての𝑉1 への辺と全ての𝑉2 から𝑡への辺を追加 • 辺の容量は全て1とすると、最大流問題とみなせる 2部グラフのマッチング問題の計算量 • 入口𝑠から出口𝑡へのフローの総量はマッチングの本数と同じ（高々min{|𝑉1 |, |𝑉2 |}） • 深さ優先探索や幅優先探索を用いれば、増加路は𝑂(|𝑉| + |𝐸|)で求められる。計算量は𝑂(|𝑉||𝐸|) 7

最大流問題：最大流問題の応用②画像分割 画像分割問題 • 画像を解析したい対象𝐹と ത それ以外の背景𝐹に分割する問題(𝐹, 𝐹ത ⊂ 𝑉) 画像分割問題から最小カット問題へ ത • 対象𝐹に属する尤度をℓ𝑣 、背景𝐹に属する尤度を ℓ𝑣 、 隣接する画素の組{𝑢, 𝑣}について分離ペナルティを 𝑝𝑢𝑣 とする • 𝐿 = σ𝑣𝜖𝑉(ℓ𝑣 + ℓ𝑣 )、𝜑(𝜎𝑢 , 𝜎𝑣 )は𝑢と𝑣が異なる領域で あれば1, 同じ領域であれば0 max: σ𝑣𝜖𝐹 ℓ𝑣 + σ𝑣𝜖 𝐹ത ℓ𝑣 − σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 ) max: 𝐿 − σ𝑣𝜖𝐹 ℓ𝑣 − σ𝑣𝜖 𝐹ത ℓ𝑣 − σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 ) min: σ𝑣𝜖𝐹 ℓ𝑣 + σ𝑣𝜖 𝐹ത ℓ𝑣 + σ{𝑢,𝑣}𝜖 𝐸 𝑝𝑢𝑣 𝜑(𝜎𝑢 , 𝜎𝑣 ) ത • これは𝐹と𝐹の最小カット問題とみなせる 8

アジェンダ ◼ 最大流問題 ◼ 最小費用流問題 9

最小費用流問題：最小費用流問題とは 最小費用流問題 • 入口となる頂点𝑠と出口となる頂点𝑡が存在しない代わりに、 頂点𝑣から流出するフローの量𝑏𝑣 が与えられる（ 𝑏𝑣 ∈ ℝ、σ𝑣𝜖𝑉 𝑏𝑣 = 0） • 辺には流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が定義される（整数） • フローの総費用を最小化する問題 10

最小費用流問題：負閉路消去法 残余ネットワーク • 頂点𝑢から頂点𝑣に流せるフローの残り容量𝑢𝑒 − 𝑥𝑒 、これは頂点𝑢から頂点𝑣の方向、費用は𝑐𝑒 • 頂点𝑣から頂点𝑢に押し戻せるフローの残り容量𝑥𝑒 、これは頂点𝑣から頂点𝑢の方向、費用は−𝑐𝑒 負閉路とは、経路に沿ってフローを流せば総費用を減らせる経路 負閉路消去法 1. 実行可能なフローを求める（右の図のような 𝑏𝑠 = 0、辺の費用は全て∞の頂点𝑠 を導入） 2. 残余ネットワークの負閉路があるか探す（なければ終了） 3. 見つけた負閉路上で可能な限りフローを減少させる 11

最小費用流問題：負閉路消去法の実行例 12

最小費用流問題：負閉路消去法の計算量と最短路繰り返し法のための双対問題 負閉路消去問題の計算量 • 流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が整数なので、1回の反復で少なくとも経路費は1減る • 容量𝑢𝑒 の最大値を𝑈、費用𝑐𝑒 の最大値を𝐶とすると、辺の数は|𝐸|、反復回数の上限も|𝐸|𝐶𝑈回 • ベルマン・フォード法を用いれば、負閉路は𝑂(|𝑉||𝐸|)で求められる。計算量は𝑂 𝑉 𝐸 2 𝐶𝑈 各制約条件に対応する重み係数𝑧𝑒 , 𝑦𝑣 を導入して、ラグランジュの緩和問題を考えると 𝑚𝑖𝑛: ෍ 𝑐𝑒 𝑥𝑒 + ෍ 𝑧𝑒 𝑥𝑒 − 𝑢𝑒 + ෍ 𝑦𝑣 𝑒∈𝐸 𝑒∈𝐸 𝑒∈𝛿 + 𝑣 𝑣∈𝑉 𝑚𝑖𝑛: − ෍ 𝑏𝑣 𝑦𝑣 − ෍ 𝑢𝑒 𝑧𝑒 + 𝑣∈𝑉 𝑒∈𝐸 ෍ 𝑥𝑒 − ෍ 𝑥𝑒 − 𝑏𝑣 ෍ 𝑠. 𝑡. 𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸 𝑒∈𝛿 − 𝑣 𝑥𝑒 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 + 𝑧𝑒 𝑠. 𝑡. 𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸 𝑒= 𝑢,𝑣 ∈𝐸 𝑚𝑖𝑛: − ෍ 𝑏𝑣 𝑦𝑣 − ෍ 𝑢𝑒 𝑧𝑒 𝑠. 𝑡. −𝑦𝑢 + 𝑦𝑣 − 𝑧𝑒 ≤ 𝑐𝑒 , 𝑒 = 𝑢, 𝑣 ∈ 𝐸, 𝑣∈𝑉 𝑥𝑒 ≥ 0, 𝑒 ∈ 𝐸 𝑒∈𝐸 • 変数𝑦𝑣 を頂点𝑣のポテンシャルと呼ぶ • 𝑐ഥ𝑒 (𝒚) = 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 を被約費用と定義する ෪𝑣 (𝒙) = 𝑏𝑣 − σ + 𝑥𝑒 + σ𝑒∈𝛿 − 𝑣 𝑥𝑒 を流量保存制約の違反量と定義する • 𝑏 𝑒∈𝛿 𝑣 13

最小費用流問題：最短路繰り返し法 相補性定理から以下のような性質が導かれる 性質 最小費用流問題の実行可能なフロー𝒙* が最適である必要十分条件は、残余ネットワークの全ての 辺𝑒 = 𝑢, 𝑣 ∈ 𝐸に対して、 𝑐ഥ𝑒 (𝒚) = 𝑐𝑒 + 𝑦𝑢 − 𝑦𝑣 ≥ 0となるポテンシャル𝒚∗ が存在することである 最短路繰り返し法 1. 𝑐𝑒 ≥ 0ならば𝑥𝑒 = 0、 𝑐𝑒 < 0ならば𝑥𝑒 = 𝑢𝑒 、 𝑦𝑣 = 0とする ∗ 2. 𝑏෪ 𝒗∗ (𝒙) > 0となる頂点𝑣 を選ぶ（なければ終了） 3. 辺の長さを被約費用𝑐ഥ𝑒 (𝒚)として、頂点𝑣 ∗ から各頂点𝑣への最短路の長さ𝑓𝑣 ∗𝑣 を求める 4. 各頂点𝑣のポテンシャルを𝑦𝑣 = 𝑦𝑣 + 𝑓𝑣 ∗𝑣 と更新する ∗ 5. 𝑏෪ 𝒗∗ (𝒙) < 0となる頂点𝑣を選び、頂点𝑣 から頂点𝑣への最短路で可能な限りフローを増加させる 14

最小費用流問題：最短路繰り返し法の実行例 15

最小費用流問題：最短路繰り返し法の計算量 最短路繰り返し法の計算量 ෪𝑣 , 0}は1 • 流量𝑥𝑒 と容量𝑢𝑒 と費用𝑐𝑒 が整数なので、1回の反復で少なくとも超過の総量σ𝑣∈𝑉 max{𝑏 減る ෪𝑣 , 0} ≤ (|𝑉| + |𝐸|)𝑈より反復回数の上限は𝑂(|𝐸|𝑈) • 容量𝑢𝑒 の最大値を𝑈とすれば、 σ𝑣∈𝑉 max{𝑏 • ダイクストラ法を用いれば、最短路は𝑂(|𝐸| + |𝑉|log|𝑉|)で求められる。 • 計算量は𝑂((|𝐸| + |𝑉|log|𝑉|)|𝐸|𝑈) 16

最小費用流問題：最小費用流問題の応用①割当問題 割当問題 • 学生集合𝑉1 とクラス集合𝑉2 のような2部グラフを考える • 学生𝑖からクラス𝑗への満足度𝑝𝑖𝑗 を辺の重みと考える 割当問題から最小費用流問題へ • 入口𝑠 (𝑏𝑠 = 𝑚)と出口𝑡 (𝑏𝑠 = −𝑚)を導入する(𝑚 = |𝑉1 |) • 𝑠から各𝑉1 への容量は1、費用は0、 𝑉1 から𝑉2 への容量は1、費用は−𝑝𝑖𝑗 各𝑉2 から𝑡への容量は𝑢𝑗 、費用は0の最小費用流問題とみなせる（ 𝑢𝑗 はクラス𝑗の上限人数） 17