最小費用流問題(Minimum Cost Flow Problem)
$N$ を頂点の集合，$A$ を辺の集合，$c_{ij}$ を辺 $(i, j)$ の単位流量あたりのコスト，$x_{ij}$ を辺 $(i, j)$ の流量，$l$ を辺の下限容量，$u$ を辺の上限容量とします．
また，$b_i$ を頂点 $i$ の需給量とし，正なら供給，負なら需要を表します．
最小費用流問題は以下のように定式化されます．
$$ \begin{aligned} &\text{minimize} && \sum_{(i, j) \in A} c_{ij} x_{ij} \\ &\text{subject to} && \sum_{j:(i, j) \in A} x_{ij} - \sum_{j:(j,i) \in A} x_{ji} = b_i && \forall i \in N \\ & && l_{ij} \le x_{ij} \leq u_{ij} && \forall (i, j) \in A \end{aligned} $$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 $\bold x$ に対し，頂点 $i$ の imbalance を次のように定義します．
第 2 項は $i$ に入ってくる流量の合計，第 3 項は $i$ から出ていく流量の合計です．
- pseudoflow $\bold x$ に対し，頂点 $i$ の imbalance を次のように定義します．
- reduced cost
- 各頂点のポテンシャル $\bold \pi$ が与えられたとき，$c_{ij}^{\pi} = c_{ij} - \pi_i + \pi_j$ を辺 $(i, j)$ の reduced cost と呼びます．
Reduced Cost 最適性
最小費用流問題の実行可能な flow $\bold x$ が最適であるための必要十分条件は，残余ネットワークのすべての辺 $(i, j)$ に対して$c^{\pi}_{ij} \ge 0$ となるポテンシャル $\bold \pi$ が存在することです．
つまり，flow $\bold x$ とポテンシャル $\bold \pi$ が与えられた時，残余ネットワーク上のすべての辺について $c_{ij}^{\pi}$ が非負であれば $x$ が最適解であるとわかります．
最短路繰り返し法(Successive Shortest Path Algorithm)
最短路繰り返し法は，容量制約を満たすが流量保存則に違反する pseudoflow $\bold x$ から開始します．
アルゴリズムの各ステップでは reduced cost 最適性を維持しつつ，実行不能解 $\bold x$ を実行可能解に近づけます．
具体的には，残余ネットワーク上で $e(k) \gt 0$ である頂点 $k$ から $e(l) \lt 0$ である頂点 $l$ へ，最短路に沿って flow を流すことで実行可能性を高めていきます．
アルゴリズムは常に reduced cost 最適性を維持しているため，実行可能解が得られたときそれが最適解であることが保証されます．
最短路繰り返し法の流れは以下のようになります．
- 初期解の構築
- $\bold x = \bold 0$，$\bold \pi = \bold 0$ とします
- 実行可能解が得られるまで以下を繰り返します
- $e(k) \gt 0$ である頂点 $k$ を選びます．各辺の reduced cost を距離とする残余ネットワーク上で，$k$ から各頂点への最短路を求めます．reduced cost は非負に保たれるため，Dijkstra 法などを使うことができます．
$e(l) \lt 0$ であるような頂点 $l$ を選び，$\bold P$ を頂点 $k$ から $l$ への最短路，$\bold d$ を頂点 $k$ からすべての頂点への最短距離とします1 - ポテンシャルの更新
- $\bold \pi^{\prime} = \bold \pi - \bold d$
- flow の更新
- $\delta = \min[e(k), -e(l), \min(r_{ij} : (i,j) \in P)]$とし，$\bold P$ に沿って辺の flow を $\delta$ 増加します
- imbalance の更新
- $e(k) = e(k) - \delta$，$e(l) = e(l) + \delta$ と更新します
- $e(k) \gt 0$ である頂点 $k$ を選びます．各辺の reduced cost を距離とする残余ネットワーク上で，$k$ から各頂点への最短路を求めます．reduced cost は非負に保たれるため，Dijkstra 法などを使うことができます．
次節からアルゴリズムの各ステップで常に reduced cost 最適性を維持することを確認していきます．
初期解の構築
初期解が容量制約と reduced cost 最適性を満たすことを確認します．
仮定より，下限容量は $0$ のため $\bold x = \bold 0$ は容量制約を満たします．
$\bold \pi = \bold 0$ のため $c_{ij}^{\pi} = c_{ij}$ です．辺のコストはすべて非負を仮定しているため $c_{ij}^{\pi} \ge 0$ となり reduced cost 最適性を満たします．
ポテンシャルの更新
ある $\bold x$ に対し $\bold \pi$ が reduced cost 最適性を満たしているとき，ポテンシャルを $\bold \pi^{\prime} = \bold \pi - \bold d$ と更新しても reduced cost 最適性を満たすことを示します1．
$\bold 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_i^{\prime} + \pi_j^{\prime} = c_{ij}^{\pi^{\prime}} \ge 0$
よって，ポテンシャルを $\bold \pi^{\prime} = \bold \pi - \bold d$ と更新しても reduced cost 最適性を満たすことがわかりました．
flow の更新
最短路に沿って flow を更新したとき reduced cost 最適性を満たすことを確認します．
まず，ポテンシャルを $\bold \pi^{\prime} = \bold \pi - \bold 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_i^{\prime} + \pi_j^{\prime} = c_{ij}^{\pi^{\prime}} = 0 $$よって，頂点 $k$ から各頂点への最短路の辺の reduced cost は $0$ となることがわかりました．
次に，flow を更新したとき reduced cost 最適性を満たすことを確認します．
$\delta = \min[e(k), -e(l), \min(r_{ij} : (i,j) \in P)]$ とし，最短路に沿って辺の flow を更新します．
$\delta$ の選び方から，このように flow を更新しても容量制約を満たします．また，reduced cost が $0$ であるため，辺に flow を流すことで残余ネットワーク上に逆辺が生じたとしても reduced cost 最適性には違反しません．
よって，最短路に沿って flow を更新したとき reduced cost 最適性を満たすことがわかりました．
計算量
$U$ を最大の供給量，$n$ を頂点数，$m$ を辺数とします．
アルゴリズムは各イテレーションで最短路問題を解き，正の imbalance の合計 $\sum_i \max(e(i), 0)$ は厳密に減少します．
$\sum_i \max(e(i), 0)$ は高々 $nU$ なので，高々 $nU$ 回のイテレーションでアルゴリズムは終了します．
二分ヒープを使った Dijkstra 法で最短路問題を解くと，計算量は $O((m + n) \log n)$ となります．
よって，全体の計算量は $O(nU (m + n) \log n)$ となります．
補足：ポテンシャルの更新の改善
上記のアルゴリズムの説明では頂点 $k$ からすべての頂点に対する最短路を求めましたが，$e(l) \lt 0$ のような頂点への最短路を 1 つ見つけたとき探索を終了できます．
Dijkstra 法で最短距離を求めているとします．最短距離が確定した頂点を permanently labeled node，まだ確定していない頂点を temporarily labeled node と呼びます．
このとき，ポテンシャルは以下のように更新できます．
証明
$S$ を permanently labeled node の集合，$\bar{S}$ を temporarily labeled node の集合とします． 頂点 $i$ と頂点 $j$ が $S$ と $\bar S$ のどちらに属するかの 4 つの場合について，ポテンシャルが $\bold \pi$ から $\bold \pi^{\prime}$ に変更されたときを考えます．1. $i \in S, j \in S$ の場合
「ポテンシャルの更新」の節と同じです．
2. $i \in S, j \in \bar{S}$ の場合
$c_{ij}^{\pi^{\prime}} = c_{ij}^{\pi} + d_i - d_l$ と更新されます．
頂点 $j$ は最短距離が確定していないため，$d_l \le d_j$ です．
また，頂点 $i$ は最短距離が確定しているため，Dijkstra 法のアルゴリズムから $d_j \le d_i + c_{ij}^{\pi}$ が成り立ちます．
よって，$d_l \le d_i + c_{ij}^{\pi}$ であるため $c_{ij}^{\pi^{\prime}} \ge 0$ を満たします．
3. $i \in \bar{S}, j \in S$ の場合
$c_{ij}^{\pi^{\prime}} = c_{ij}^{\pi} + d_l - d_j$ と更新されます．
頂点 $j$ は最短距離が確定しているため，$d_j \le d_l$ です．
よって，$c_{ij}^{\pi^{\prime}} \ge 0$ を満たします．
4. $i \in \bar{S}, j \in \bar{S}$ の場合
$c_{ij}^{\pi^{\prime}} = c_{ij}^{\pi} + d_l - d_l$ と更新されます．
よって，$c_{ij}^{\pi^{\prime}} \ge 0$ を満たします．
また，すべてのポテンシャルに定数を加算しても reduced cost 最適性に影響はないため，全体に $d_l$ を加算することで以下のように更新することもできます．
$$ \pi_{i}^{\prime} = \left\{ \begin{array}{ll} \pi_{i} - d_{i} + d_{l} & \text{node i is permanently labeled}\\ \pi_{i} & \text{node i is temporarily labeled} \end{array} \right. $$よって，最短距離が確定した頂点のみポテンシャルの更新を行えば十分です．