最小費用フロー問題

最小コストフロー問題( MCFP ) は、フローネットワークを通じて一定量のフローを送る最も安価な方法を見つけるための最適化および決定問題です。この問題の典型的な応用例は、道路ネットワークに一定の容量とコストが関連している工場から倉庫への最適な配送ルートを見つけることです。最小コストフロー問題は、すべてのフローおよび循環問題の中で最も基本的な問題の 1 つです。これは、他のほとんどの同様の問題が最小コストフロー問題として表すことができ、ネットワーク単体アルゴリズムを使用して効率的に解決できるためです。

フロー ネットワークは、ソース頂点とシンク頂点を持つ有向グラフ です。各エッジには容量、フロー、コスト があり、ほとんどの最小コスト フロー アルゴリズムは負のコストを持つエッジをサポートしています。このフローをエッジに沿って送信するコストはです。この問題では、ソースからシンクに送信されるフローの量が必要です。 ${\displaystyle G=(V,E)}$${\displaystyle s\in V}$${\displaystyle t\in V}$${\displaystyle (u,v)\in E}$${\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 d}$${\displaystyle s}$${\displaystyle t}$

問題の定義は、すべてのエッジ上のフローの 総コストを最小化することです。

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

制約のある

この問題のバリエーションは、最大フロー ソリューションの中で最大でありながらコストが最も低いフローを見つけることです。これは最小コスト最大フロー問題と呼ばれ、最小コスト最大マッチングを見つけるのに役立ちます。

いくつかのソリューションでは、最小コストの最大フローを簡単に見つけることができます。そうでない場合は、バイナリ検索を実行して最大フローを見つけることができます。 ${\displaystyle d}$

関連する問題として、最小コスト循環問題があり、これは最小コストフローの解決に使用できます。最小コスト循環問題にはソースとシンクがありません。代わりに、各エッジにコストと下限と上限があり、各頂点でのフローのバランスを取り、コストとフローのエッジ全体の合計を最小化する、指定された境界内でのフロー量を求めます。すべてのエッジの下限を 0 に設定し、シンクからソース への追加のエッジ(容量、下限 ) を作成して、 から への合計フローもになるようにすることで、任意の最小コストフローインスタンスを最小コスト循環インスタンスに変換できます。 ${\displaystyle t}$${\displaystyle s}$${\displaystyle c(t,s)=d}$${\displaystyle l(t,s)=d}$${\displaystyle s}$${\displaystyle t}$${\displaystyle d}$

以下の問題は最小費用フロー問題の特殊なケースである（適用可能な各削減について順に簡単な概要を示す）：^[1]

• 最短経路問題(単一ソース)。最小コストフロー問題の実行可能なソリューションは、指定されたソースから指定されたシンクに1 単位のフローを送信することを要求します。すべてのエッジに無限の容量を与えます。${\displaystyle s}$${\displaystyle t}$
• 最大フロー問題。大きな需要（最大フローを超えるほどの大きさ、たとえば、ソース頂点からの容量の合計）を選択します。最大フローインスタンス内のすべてのエッジのコストをゼロに設定し、ソースからシンクへのユニットコストと容量を持つ新しいエッジを導入します。${\displaystyle d}$${\displaystyle d}$
• 割り当て問題。二分割の各部分集合に頂点があり、二分割を で表すものとします。各供給を、各需要をとします。各辺は単位容量を持ちます。${\displaystyle n}$${\displaystyle (X,Y)}$${\displaystyle x\in X}$${\displaystyle 1/n}$${\displaystyle y\in Y}$${\displaystyle 1/n}$

最小コストフロー問題は線形関数を最適化し、すべての制約が線形であるため、 線形計画法によって解決できます。

それ以外にも、多くの組み合わせアルゴリズムが存在します。^[1]そのうちのいくつかは最大フローアルゴリズムの一般化であり、他のものは完全に異なるアプローチを使用します。

よく知られている基本的なアルゴリズム（多くのバリエーションがあります）：

• サイクルキャンセル：一般的な原始的方法。^[2]
• カットキャンセル：一般的なデュアルメソッド。^{[3] [4]}
• 最小平均サイクルキャンセル：単純な強多項式アルゴリズム。^[5]
• 連続最短経路と容量スケーリング：フォード・フルカーソンアルゴリズムの一般化と見ることができるデュアルメソッド。^[6]
• コストスケーリング：プッシュ・リラベルアルゴリズムの一般化として見ることができるプライマル・デュアルアプローチ。^[7]
• ネットワークシンプレックスアルゴリズム：線形計画 シンプレックス法の特殊版。 ^[8]
• DR フルカーソンによる不均衡なアルゴリズム

二部グラフ G = ( A ∪ B , E )が与えられた場合、目標はG内でコストが最小となる最大濃度のマッチングを見つけることです。w : E → R をEのエッジの重み関数とします。最小重み二部マッチング問題または割り当て問題は、合計重みが最小となる完全マッチングM ⊆ E を見つけることです。この問題をネットワークフロー問題に縮小するという考え方です。

G′ = ( V′ = A ∪ B , E′ = E )とします。E ′のすべての辺の容量を1 に割り当てます。ソース頂点s を追加してA′のすべての頂点に接続し、シンク頂点t を追加してグループB′内のすべての頂点をこの頂点に接続します。すべての新しい辺の容量は 1 で、コストは 0 です。G ′に最小コストフローがある場合に限り、Gに最小重量の完全二部マッチングが存在することが証明されています。^[1]

• LEMON (C++ ライブラリ)
• GNU 線形計画法キット
• ネットワークフローの問題

• 最大フローおよび最小コスト循環アルゴリズムを備えた LEMON C++ ライブラリ
• 最小コストフローと最短経路アルゴリズムを備えたMCFClass C++プロジェクトライブラリ