複数商品フロー問題

マルチ商品フロー問題は、異なるソース ノードとシンク ノード間に複数の商品 (フロー需要) がある ネットワーク フロー問題です。

フロー ネットワーク が与えられます。ここで、エッジの容量は です。によって定義される商品があり、ここで、 と は商品 のソースとシンクであり、 はその需要です。 変数 は、エッジ に沿ったフローの割合を定義します。ここで、フローを複数のパスに分割できる場合は 、そうでない場合は (つまり、「単一パス ルーティング」) となります。次の 4 つの制約を満たすすべてのフロー変数の割り当てを見つけます。 ${\displaystyle \,G(V,E)}$${\displaystyle (u,v)\in E}$${\displaystyle \,c(u,v)}$${\displaystyle \,k}$${\displaystyle K_{1},K_{2},\dots ,K_{k}}$${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$${\displaystyle \,s_{i}}$${\displaystyle \,t_{i}}$${\displaystyle \,i}$${\displaystyle \,d_{i}}$${\displaystyle \,f_{i}(u,v)}$${\displaystyle \,i}$${\displaystyle \,(u,v)}$${\displaystyle \,f_{i}(u,v)\in [0,1]}$${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$

（１）リンク容量：リンクを介してルーティングされるすべてのフローの合計がその容量を超えない。

${\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}$

（２）中継ノードにおけるフロー保存：中間ノードに入るフローの量は、そのノードから出るフローの量と同じである。 ${\displaystyle u}$

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}$

（３）ソースにおけるフロー保存：フローはソースノードから完全に出なければならない。

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}$

（４）目的地でのフロー保存：フローはシンクノードに完全に入らなければならない。

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}$

負荷分散とは、すべてのリンクの利用率が均等になるようにフローをルーティングする試みであり、 ${\displaystyle U(u,v)}$${\displaystyle (u,v)\in E}$

${\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}$

この問題は、例えば を最小化することで解決できます。この問題の一般的な線形化は、最大利用率 の最小化です。ここで、 ${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$${\displaystyle U_{max}}$

${\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}$

最小費用多品目フロー問題では、フローを に送信するのに費用がかかります。次に、最小化する必要があります。 ${\displaystyle a(u,v)\cdot f(u,v)}$${\displaystyle \,(u,v)}$

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}$

最大多品目フロー問題では、各商品の需要は固定されておらず、すべての需要の合計を最大化することで総スループットが最大化される。${\displaystyle \sum _{i=1}^{k}d_{i}}$

多品目フロー問題の最小費用変種は、最小費用フロー問題（ソースとシンクが1つだけの場合）の一般化です。循環問題の変種は、すべてのフロー問題の一般化です。つまり、あらゆるフロー問題は、特定の循環問題として見ることができます。^[1]${\displaystyle s}$${\displaystyle t}$

光ネットワークの光バーストスイッチングにおけるルーティングと波長割り当て(RWA) は、ネットワークが各ノードで波長変換を備えている場合、マルチコモディティフロー式を介してアプローチされます。

レジスタ割り当ては、整数最小コストのマルチコモディティフロー問題としてモデル化できます。命令によって生成される値はソースノード、命令によって消費される値はシンクノード、レジスタとスタックスロットはエッジです。^[2]

問題の決定バージョンでは、すべての需要を満たす整数フローを生成する問題は、たとえ2つの商品と単位容量だけであってもNP完全である^[3] （この場合、 問題は強くNP完全となる）。

分数フローが許される場合、この問題は線形計画法[ ^4]または（通常より高速な）完全多項式時間近似法^[5]によって多項式時間で解くことができる。

マルチコモディティフローはコンテンツ配信におけるオーバーレイルーティングに適用される。^[6]

• この問題に関する Clifford Stein の論文: http://www.columbia.edu/~cs2035/papers/#mcf
• 問題を解決するソフトウェア: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

追加: Jean-Patrice Netter、「Flow Augmenting Meshings: マルチ商品ネットワークにおける最大整数フローへの基本的なアプローチ」、博士論文、ジョンズ ホプキンス大学、1971 年