最小費用流問題(Minimum Cost Flow Problem)

$N$ を頂点の集合，$A$ を辺の集合，$c_{ij}$ を辺 $(i, j)$ の単位流量あたりのコスト，$x_{ij}$ を辺 $(i, j)$ の流量，$b_i$ を頂点 i の需要/供給量，$l$ を辺の下限容量，$u$ を辺の上限容量としたとき，最小費用流問題（以下 MCFP）は以下のように定式化されます．
1 つめの制約を流量保存則と呼び，第一項は頂点 i から出る流量，第二項は頂点 i に入る流量を表します． 2 つめの制約を容量制約と呼びます．

以下ではコスト，流量，需要/供給，下限容量，上限容量はすべて整数とします．また，$\sum_{i \in N} b_i = 0$，コストを非負，下限容量を 0 とします．

用語・定義

• pseudoflow

  • 容量制約を満たす flow を pseudoflow と呼びます．流量保存則には違反していてもかまいません．

• 残余容量

  • $r_{ij} = u_{ij} - x_{ij}$ を辺 (i, j) の残余容量と呼びます．

• imbalance

  • pseudoflow x に対し，頂点 i の imbalance を次のように定義します．
    $e(i) = b(i) + \sum_{j:(j, i) \in A} x_{ji} - \sum_{j:(i,j) \in A} x_{ij}$

• reduced cost

  • 各頂点のポテンシャル $\pi$ が与えられたとき，$c_{ij}^{\pi} = c_{ij} - \pi(i) + \pi(j)$ を辺 (i, j) の reduced cost と呼びます．

Reduced Cost 最適性

最小費用流問題の実行可能な flow $x$ が最適であるための必要十分条件は，残余ネットワークのすべての辺 (i, j) に対して$c^{\pi}_{ij} \ge 0$ となるポテンシャル $\pi$ が存在することです．

最短路繰り返し法(Successive Shortest Path Algorithm)

最短路繰り返し法は容量制約を満たすが流量保存則に違反する pseudoflow x から開始します．
アルゴリズムの各ステップでは reduced cost 最適性を維持しつつ，主問題の実行不能解 x を実行可能解に近づけます．
具体的には，残余ネットワーク上で$e(k) \gt 0$ である頂点 k から $e(l) \lt 0$ である頂点 l へ，最短路に沿って flow を流すことで実行可能性を高めていきます．
実行可能解が得られたときアルゴリズムは終了します．

最短路繰り返し法の流れは以下のようになります

• 初期解の構築
  • $x = 0$，$\pi = 0$ とする
• 実行可能解が得られるまで以下を繰り返す
  • reduced cost を距離とする残余ネットワーク上で，$e(k) \gt 0$ である頂点 k から各頂点への最短路を求める
    • $P$ を k から各頂点への最短路，$d$ を最短距離とする
  • ポテンシャルの更新
    • $\pi^{\prime} = \pi - d$
  • flow と imbalance の更新
    • $\delta = min[e(k), min(r_{ij} : (i,j) \in P)]$とし，$P$ に沿って辺の flow を $\delta$ 増加する
    • $e(k) = e(k) - \delta$，$e(l) = e(l) + \delta$ と更新する

次節からアルゴリズムの各ステップで常に reduced cost 最適性を維持することを確認していきます．

初期解の構築

初期解が容量制約と reduced cost 最適性を満たすことを確認します．
仮定より，下限容量は 0 のため $x = 0$ は容量制約を満たします．
$\pi = 0$ のため $c_{ij}^{\pi} = c_{ij}$ です．辺のコストはすべて非負を仮定しているため $c_{ij}^{\pi} \ge 0$ となり reduced cost 最適性を満たします．

ポテンシャルの更新

ある $x$ に対し $\pi$ が reduced cost 最適性を満たしているとき，ポテンシャルを $\pi^{\prime} = \pi - d$ と更新しても reduced cost 最適性を満たすことを示します¹．

$d$ は reduced cost を距離とした残余ネットワーク上での頂点 k から各頂点への最短距離であるため，各辺 (i, j) は $d(j) \le d(i) + c_{ij}^{\pi}$ を満たします．

上の式に $c_{ij}^{\pi} = c_{ij} - \pi(i) + \pi(j)$ を代入します．
$d(j) \le d(i) + c_{ij} - \pi(i) + \pi(j)$

$d(j)$を移項し，頂点ごとにまとめます．
$c_{ij} - (\pi(i) - d(i)) + (\pi(j) - d(j)) \ge 0$

ポテンシャルの更新の仕方から以下が成り立ちます．
$c_{ij} - \pi^{\prime}(i) + \pi^{\prime}(j) = c^{\pi_{ij}^{\prime}} \ge 0$

よって，ポテンシャルを $\pi^{\prime} = \pi - d$ と更新しても reduced cost 最適性を満たすことがわかりました．

flow の更新

最短路に沿って flow を更新したとき reduced cost 最適性を満たすことを確認します．

まず，ポテンシャルを $\pi^{\prime} = \pi - d$ と更新したとき，頂点 k から各頂点への最短路の辺の reduced cost が 0 となることを確認します．
頂点 k から頂点 l の最短路を考えます．最短路であるため，この経路の各辺は $d(j) = d(i) + c_{ij}^{\pi}$ を満たします．

上の式に $c_{ij}^{\pi} = c_{ij} - \pi(i) + \pi(j)$ を代入します．
$d(j) = d(i) + c_{ij} - \pi(i) + \pi(j)$

$d(j)$ を移項し，頂点ごとにまとめます．
$c_{ij} - (\pi(i) - d(i)) + (\pi(j) - d(j)) = 0$

ポテンシャルの更新の仕方から以下が成り立ちます．
$c_{ij} - \pi^{\prime}(i) + \pi^{\prime}(j) = c^{\pi_{ij}^{\prime}} = 0$

よって，頂点 k から各頂点への最短路の辺の reduced cost は 0 となることがわかりました．

次に，flow を更新したとき reduced cost 最適性を満たすことを確認します．
$\delta = min[e(s), min(r_{ij} : (i,j) \in P)]$ とし，最短路に沿って辺の flow を更新します．
$\delta$ 選び方から，このように flow を更新しても容量制約を満たします．また，reduced cost が 0 であるため，辺に flow を流すことで残余ネットワーク上に逆辺が生じたとしても reduced cost 最適性には違反しません．
よって，最短路に沿って flow を更新したとき reduced cost 最適性を満たすことがわかりました．

計算量

$U$ を最大の供給量，$C$ をコストの最大値とします．
アルゴリズムは各イテレーションで最短路問題を解き，供給量は厳密に減少します． よって，$nU$ 回のイテレーションでアルゴリズムは終了します．最短路問題に 2 分ヒープを使った dijkstra 法を使うとすると $O((m + n) \log n)$ となります．
よって，全体で $O(nU (m + n) \log n)$ となります．

補足：ポテンシャルの更新の改善

dijkstra 法で最短距離を求めているとします．
上記のアルゴリズムの説明では頂点 k からすべての頂点に対する最短路を求めましたが，$e(l) \lt 0$ のような頂点を見つけたとき探索を終了したとします．最短距離が確定した頂点を permanently labeled node，まだ確定していない頂点を temporarily labeled node と呼びます．
このとき，ポテンシャルは以下のように更新することができます．

また，すべてのポテンシャルに定数を加算しても reduced cost 最適性に影響はないため，全体に $d(l)$ を加算することで以下のように更新することもできます．

参考

• Network Flows: Pearson New International Edition