最小費用流問題(Cost Scaling)

最小費用流問題を Cost Scaling を用いて $O(V^2E \log{(VC)})$ で解く。

内容

最小費用流問題(Minimum Cost Flow Problem)とは以下のような問題です(ここでは、$d(v) > 0$ で supply とする)。
$$
\min \sum_{e \in E} f(e) \cdot \gamma(e) \\
\mathrm{s.t.}
\begin{cases}
\forall e \in E, b(e) \le f(e) \le c(e) \\
\forall v \in V, \sum\limits_{e_\mathrm{from}=v} f(e) - \sum\limits_{e_\mathrm{to}=v} f(e) = d(v)
\end{cases}
$$

この問題を解くアルゴリズムの 1 つに Cost Scaling というものがあり、Graph, Networks and Algorithms の 10.7 付近で扱われています。以下では、このアルゴリズムを、前処理に Dinic、主処理に Young-Tarjan-Orlin の Minimum Mean Cycle アルゴリズム + PushRelabel を用いて、$O(V^2 E \log{VC})$ ($C$: 最大コスト)で実装したものを載せています。

Young-Tarjan-Orlin の Minimum Mean Cycle については、

辺りに書かれています。

実行例

ソースコードが長いので、先に実行例を載せます。

問題には、Minimum-cost flow algorithms: An experimental evaluation に書かれている Dimacs 形式の問題を使用しています。例えば、MinCostFlowData – LEMON からダウンロードできます。

比較に使うのは、Lemon の CostScaling (http://lemon.cs.elte.hu/pub/doc/latest/a00102.html) [Partial Augment-Relabel] です。さすがに早い。

  • 実行時間の単位は秒。

問題名 $V$ $E$ 最適値 自分の実装 Lemon
goto_8_08a.min 256 2048 560870539 0.036 0.006
goto_8_10a.min 1024 8192 1861135786 0.302 0.037
goto_8_12a.min 4096 32768 6133066146 5.406 0.311
goto_8_14a.min 16384 131072 42104991210 123.1 2.323
goto_8_16a.min 65536 524288 205664925703 2446 20.3
goto_sr_12a.min 4096 262144 59460562987 34.6 2.32
gridgen_8_14a.min 16385 131080 1913362845 1.19 0.411
gridgen_8_16a.min 65537 524296 3391613068 6.79 2.42
netgen_8_14a.min 16384 131072 1772056888 1.18 0.455
netgen_8_16a.min 65536 524288 4023172764 9.11 2.57
netgen_sr_14a.min 16384 2097152 132201189 13.5 4.3
netgen_lo_8_14a.min 16384 131072 12166598 0.718 0.227
netgen_lo_8_16a.min 65536 524288 27302646 4.80 1.47
vision_inv_02_..._n6c100_a.min 491522 2877382 25108031 51.7 50.3
vision_prop_02_..._n6c100_a.min 491522 2877382 1250516158 85.0 66.0
vision_rnd_02_..._n6c100_a.min 491522 2877382 79362008 50.1 38.2

Google の or-tools の MinCostFlow も、自分の実行時間の 1/3〜1/2 ぐらいで計算できて早い(goto_8 系が Lemon より劣る感じ)。実装は、CostScaling + PushRelabel + 有名どころの heuristic に見える。

その他

  • PushRelabel の代わりに Dinic を使えるらしい (?)。多分、実装が相当軽くなる。(どうやら Solving minimum-cost flow problems by successive approximation を読めばいいみたい。)
  • [追記] 上の論文(か http://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf の 3.6)の通りに実装した感じでは、各 Refine 内での必要な BlockingFlow の回数は結構多く、Dinic 版は PushRelabel 版の数十倍ほど時間がかかってしまった。色々工夫が必要なのかもしれない。
  • Network Simplex と呼ばれるアルゴリズムも、小規模な問題に対しては早いらしい。

実装例

Young-Tarjan-Orlin が全体の半分ぐらい。

Cost Scaling (YTO + PushRelabel) の実装コード


Lemon の実験用のコード