ネットワークフロー問題

出典: ORWiki

【ねっとわーくふろーもんだい (network flow problem)】

概要

ネットワーク上のフローを扱う最適化問題の総称. 最大フロー問題, 最小費用フロー問題, 輸送問題, 多品種フロー問題, 利得/損失付きフロー問題(一般化フロー問題)などがある. 最短路問題, 割当問題, 最小カット問題もネットワークフロー問題として扱うこともある.

詳説

　ネットワーク上のモノの流れを扱う．モノは与えられた有向グラフ $G=(V, A)\,$ の各枝に沿って流れ，点で分岐や合流をする．ただし，各枝 $a\,$ の容量 $c(a)\,$ を超えず，各点 $v\,$ から出る正味の流量が，与えられた供給量 $d(v)\,$ と等しくなるようにする．枝aを流れる量を $\varphi(a)\,$ としたとき，

容量制約　 $0 \leq \varphi(a) \leq c(a) \; \; (a \in A)\,$

流量保存則　 ${\sum}_{a \in \delta^+v} \varphi(a)-{\sum}_{a \in \delta^-v} \varphi(a)=d(v) \; \; (v \in V)\,$

を満たす $\varphi\,$ をフローといい，フローを扱った最適化問題をネットワークフロー問題という [1] ．ただし， $\delta^+v (\delta^-v)\,$ は点 $v\,$ から出る (へ入る) 枝の全体を表す．　代表的なネットワークフロー問題に最大フロー問題がある．最大フロー問題とは，特別な点として入口 $s\,$ と出口 $t\,$ があり， $s, t\,$ 以外での供給量 $d(v)\,$ が0であるとき， $s\,$ から入る量 (フロー値) を最大にするようなフロー (最大フロー) を求める問題であり，以下のように定式化できる．

$\begin{array}{lll} \mbox{maximize} & {\sum}_{a \in \delta^+ s} \varphi(a)-{\sum}_{a \in \delta^- s}\varphi(a) \\ \mbox{subject to}& 0 \leq \varphi(a) \leq c(a) & (a \in A), \\ & {\sum}_{e \in \delta^+v} \varphi(a)-{\sum}_{e \in \delta^-v} \varphi(a)=0 & (v \in V \setminus\{s, t \}). \end{array}\,$

　点の部分集合 $X\,$ が $s\,$ を含み， $t\,$ を含まないとき， $X\,$ を $s-t\,$ カットという．始点が $X\,$ にあり終点が $X\,$ にない枝の容量の和を $X\,$ の容量といい，容量最小の $s-t\,$ カットを最小カットという．任意のフローのフロー値は任意の $s-t\,$ カットの容量よりも大きくなり得ない．この値が一致するようなフローと $s-t\,$ カットが存在することを示したのが，最大フロー最小カット定理 [2] である．実際，ある $s-t\,$ カットの容量に一致するフロー値をもつフローが以下の操作で得られる．

　まず，任意のフロー $\varphi\,$ に対し，補助ネットワーク ${\mathcal N}_\varphi=(G_\varphi=(V, A_\varphi), c_\varphi)\,$ を定義する． $G_\varphi\,$ は，与えられたグラフと同じ点集合 $V\,$ をもち，枝集合が $A_\varphi=\{a \mid a \in A, \varphi(a) < c(a) \}\cup \{\bar{a} \mid a \in A, \varphi(a)>0 \}\,$ のグラフとする．ただし， $\bar{a}\,$ は，枝 $a\,$ の向きを逆にした枝である． $c_\varphi\,$ は， $A_\varphi\,$ の枝に定義される残余容量であり，

$c_\varphi(a)=\left\{ \begin{array}{ll} c(a)-\varphi(a) & (a \in A) \\ \varphi(\bar{a}) & (\bar{a} \in A) \end{array} \right.\,$

で与えられる．補助ネットワーク上の $s\,$ から $t\,$ への有向道を増加道という．増加道に沿ってフローの更新を繰り返し，フロー値を増加させる方法を増加道法という．任意のフローから始め，以下の手順を繰り返す．

手順1: ${\mathcal N}_\varphi\,$ を作成し，増加道 $P\,$ をみつける．増加道がなければ終了．

手順2: $\varepsilon=\min\{c_\varphi(a) \mid a\,$ は $P\,$ 上の枝 $\}\,$ を求め， $P\,$ 上のすべての枝 $a\,$ に関して， $a \in A\,$ ならば， $\varphi(a)\,$ を $\varepsilon\,$ 増加し， $\bar{a} \in A\,$ ならば， $\varphi(a)\,$ を $\varepsilon\,$ 減少させる．

　増加道が存在しなくなったとき， ${\mathcal N}_\varphi\,$ 上で $s\,$ から到達可能な点集合を $X\,$ とすると， $X\,$ は $s-t\,$ カットであり，その容量はフロー値と一致する．よって，増加道法が終了したときのフローが最大フローであり， $X\,$ が最小カットである．

　増加道の選択を，枝数最小や， $\varepsilon\,$ 最大の基準で行うと，多項式時間の最大フローアルゴリズムとなる．一方，流量保存則を緩和したプリフローを用い，増加道が存在しないようなプリフローを維持しながら，最大フローを求めるプッシュ・再ラベル法も効率よい最大フローアルゴリズムである．

　最小費用フロー問題もネットワーク・フロー問題の一つである．各枝 $a\,$ のフロー1単位あたりの費用 $\gamma(a)\,$ が与えられているとき，総費用 $\textstyle {\sum}_{a \in A}\gamma(a)\varphi(a)\,$ を最小にするフローを求める問題である．特に，すべての点で供給量 $d(v)=0\,$ のとき，循環フローという．また，輸送問題も最小費用フロー問題の特殊ケースである．複数の供給地と需要地があり，各々の供給/需要量と，各供給地と需要地間の輸送費用がわかっているとき，供給/需要を満たし，輸送にかかる総費用を最小とする輸送方法とその輸送量を決定する輸送問題は，容量制約のない2部グラフ上の最小費用フロー問題である．　最小費用フローアルゴリズムも多数ある．補助ネットワーク ${\mathcal N}_\varphi\,$ 上の費用を

$\gamma_\varphi(a)=\left\{ \begin{array}{ll} \gamma(a) & (a \in A) \\ -\gamma(\bar{a}) & (\bar{a} \in A) \end{array} \right. \,$

で定義すると，フローが最小費用である必要十分条件は，その補助ネットワーク上に負の費用の閉路が存在しないことである．補助ネットワーク上の負の費用の閉路を繰り返し除去することによって最適フローを求めるのが負閉路消去法である．この他にも，点に対応する双対変数を与え，相補スラック条件を満たす枝からなるネットワーク上で最大フロー問題を繰り返し解く方法，最短路問題を繰り返し解く方法，単体法を用いたネットワーク単体法などがある．いずれの方法も強多項式時間アルゴリズムが存在する．

　最大フロー問題，最小費用フロー問題ともに，容量，供給量が整数で与えられているときには，整数値の最適フローが存在することが知られている．また，ネットワークの構造を用いた効率よいアルゴリズムがいくつか存在する．一方，１つのネットワーク上に複数品種を流す多品種フロー問題は，品種ごとに流量保存則が満たされており，かつすべての品種をあわせて容量制約が満たされている多品種フローを扱う．多くのアルゴリズムは線形計画法の手法に基づいている．整数値の多品種フローを求める問題はNP完全である．

参考文献

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

[2] L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.

[3] B. Korte and J. Vygen, Combinatorial Optimization, 4th ed., Springer, 2007. 浅野孝夫他訳, 『組合せ最適化』, シュプリンガー・フェアラーク東京，2005．

[4] アルゴリズムデータベース　http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF%E3%83%95%E3%83%AD%E3%83%BC%E5%95%8F%E9%A1%8C" より作成

カテゴリ: グラフ･ネットワーク | 組合せ最適化