ネットワークフロー問題

組み合わせ最適化において、ネットワークフロー問題は、入力がフローネットワーク（エッジに数値容量を持つグラフ）であり、目標が、容量制約を尊重し、特定の指定された終端を除くすべての頂点で流入フローと流出フローが等しくなるフロー、つまり各エッジ上の数値を構築する計算問題のクラスである。 ^{[ 1 ]}

ネットワークフローの問題には、以下のような具体的な種類があります。

• 最大フロー問題では、ソース端末からシンク端末への総フロー量を最大化することが目標となる^{[ 1 ]： 166-206}
• 最小費用フロー問題では、エッジには容量だけでなく費用も設定されており、目標は可能な限り最小の費用で所定のフロー量（または最大フロー）を達成することである^{[ 1 ]： 294-356}
• 多品目フロー問題では、総フロー量が容量^{[ 1 ] 649-694を満たすように、異なる品目について複数のフローを構築する必要がある。}
• ゼロでない流れとは、組み合わせ論で研究される流れの一種で、流れの量が有限個の非ゼロ値に限定されるものである。

最大フロー最小カット定理は、最大フローの値と最小カットの値（フローネットワークの頂点を分割し、分割の一方の側から他方の側へ交差するエッジの総容量を最小化する分割）を等しく定義する定理です。近似最大フロー最小カット定理は、この定理を多品目フロー問題に拡張したものです。無向フローネットワークのゴモリー・フー木は、異なる終端頂点のペア間のすべての最小カットを簡潔に表現します。

フローを構築するためのアルゴリズムには以下が含まれる

• ディニッチのアルゴリズム、最大フローのための強力な多項式アルゴリズム^{[ 1 ]： 221-223}
• エドモンズ・カープアルゴリズムは、最大フローのためのより高速な強多項式アルゴリズムである。
• フォード・ファルカーソンアルゴリズムは、一般に強多項式ではない最大フローのための貪欲アルゴリズムである。
• ネットワークシンプレックスアルゴリズムは、線形計画法に基づくがネットワークフローに特化した手法である^{[ 1 ]： 402-460}
• 最小費用フローのための非対称アルゴリズム^{[ 1 ]： 326-331}
• プッシュ・リラベル最大フローアルゴリズムは、最大フローを実現するための最も効率的な既知の手法の1つである。

そうでなければ、問題はより一般的な線形計画問題などとして定式化され、汎用最適化ソルバーを使用して解くことができる。