最小費用流問題

最小費用流問題（さいしょうひようりゅうもんだい、最小費用フロー問題、英: minimum-cost flow problem、略称：MCFP）とは、フローネットワークにおいてある与えられた量のフローを流すとき、最も費用がかからないものを求める最適化・決定問題である。最小費用流問題の主な応用例としては道路網に容量と費用が付随した中での工場から倉庫までの最適な配送経路を求める事例が挙げられる。多くのフローや循環に関する問題は最小費用流問題として定式化することができ、それをネットワーク単体法を用いて効率良く解くことができるため、最小費用流問題は最も基本的な問題の一つとして挙げられる。

定義

フローネットワークでは有向グラフ ${\displaystyle G=(V,A)}$ および始点となる頂点 ${\displaystyle s\in V}$ と、終点となる頂点 ${\displaystyle t\in V}$ が与えられる。ただし、各辺 ${\displaystyle (u,v)\in A}$ に対して正の値をとる容量 ${\displaystyle c(u,v)>0}$ とフロー量 ${\displaystyle f(u,v)}$、費用 ${\displaystyle a(u,v)}$ が定義され、最小費用流問題に対するアルゴリズムでは非負の費用であることが求められる。辺 ${\displaystyle (u,v)}$ にフローを流すときにかかる費用は ${\displaystyle f(u,v)\cdot a(u,v)}$ によって求まる。この問題は始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ へフロー ${\displaystyle d}$ を流すことを考える。

最小費用流問題で求めることはすべての辺においてフローを流すときにかかる費用の総和の最小化である。

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

これを達成するために、守らなければならない条件（制約条件）は:

容量制約:	${\displaystyle \,f(u,v)\leq c(u,v)}$
流量保存則:	${\displaystyle \,f(u,v)=-f(v,u)}$
始終点に関する制約:	${\displaystyle \,\sum _{w\in V}f(u,w)=0\quad \forall u\neq s,t}$
フロー需給量制約:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d}$

他の問題との関連性

最小費用流問題の類似問題としてはフローネットワークにおいて最大流を流すときに、その中で最も費用が掛からないものを求める問題が挙げれられる。これは最小費用最大流問題として知られ、最小費用の下で最大マッチングを求めるために利用されている。

最小費用最大流問題はいくつかの解法によって、多くの問題に対して効率よく最小費用最大流を求めることができる。そうでない場合は、二分探索によってある ${\displaystyle d}$ の下での最小費用流を解いていくことで、最小費用最大流を求めることができる。

以下の問題は最小費用流問題の特殊な問題として知られている^{[1][注釈 1]}:

• （単一の始点をもつ）最短経路問題: 始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ へ単一のフローを流すときにかかる費用が最小の解を求めることと等しい。なお、各辺の容量は無限であると仮定する。
• 最大流問題: 十分に大きな需要量 ${\displaystyle d}$ を与える（${\displaystyle d}$ は始点から出る辺の容量の総和を超すようなフロー量などフローネットワークでの最大流より十分に大きなものとする）。そして、各辺の費用をすべてゼロとする。また、始点から終点へ単位費用と ${\displaystyle d}$ の容量を持つ辺を新たに加える。
• 割当問題（英語版）: 二つに分けられた部分集合がそれぞれ ${\displaystyle n}$ 個の頂点を持っているとする。また、二つの部分集合を ${\displaystyle (X,Y)}$ と記述する。各 ${\displaystyle x\in X}$ では供給量 ${\displaystyle 1/n}$ を持ち、各 ${\displaystyle y\in Y}$ においては需要量 ${\displaystyle 1/n}$ を持つとする。各辺は単位容量を持つとする。

解法

最小費用流問題は線形で表される制約の下で線形関数の最適化を行うため、線形計画法により解くことができる。

これ以外にも多くの厳密解法が知られている^[1]。いくつかの解法は最大流問題に対する解法を一般化させたものではあるが、異なるアプローチにより提案された解法も存在している。

（変種も含めた）一般的に知られているアルゴリズムは以下が挙げられる:

• 負閉路消去法（Cycle canceling）^[2]: 一般的に知られている解法で主（プライマル）法に分類される^[3]。
• カット消去法（Cut canceling）^[4]: 双対法に分類される解法で、一般的に知られている^[5][6]。
• 最小平均閉路消去法（Minimum mean cycle canceling）^[7]: 単純な解法で強多項式時間（英語版）で実行できる^[8]。
• 逐次最短路法（最短路繰り返し法、Successive shortest path）・容量スケーリング法（capacity scaling）^[9]: 最大流問題に対するフォード・ファルカーソン法を一般化させた解法で、双対法に分類される^[10]。
• 費用スケーリング法（Cost scaling）^[11]: 最大流問題に対するプリフロープッシュ法を一般化させた解法であり、主双対法に分類される^[12]。
• ネットワーク単体法（ネットワークシンプレックス法、Network simplex algorithm）^[13]: 線形計画法に対する単体法を最小費用流問題に特化させた解法^[14]。
• アウトオブキルタ法（Out-of-kilter algorithm）^[15]: レイ・ファルカーソン（英語版）により提案された。