最大流(Dinic vs HI-PR)

最大流のアルゴリズムの Dinic と Highest Label Push Relabel (HI-PR) を比較する。

  • [2017-08-25] : Push Relabel の無意味な命令を除き、Gap Relabeling を Doubly Linked List で行うように変更。実用問題が数十倍程度速くなった。

条件

比較的軽めの実装の Dinic と Push Relabel を用いて比較する。Push Relabel は Gap Relabeling と Global Relabeling を合わせて使う。

実行結果

グラフの構築の時間は除く。(簡単な問題の場合、この処理がボトルネックの事が多いのだけれども。)

問題

  • ak.c: http://dimacs.rutgers.edu/pub/netflow/generators/network/ にある。
  • KZ2-venus7.max など: http://vision.csd.uwo.ca/maxflow-data にある。
  • worst2: Mi_Sawa さんの(http://topcoder.g.hatena.ne.jp/Mi_Sawa/20140311/1394730338#seemore)のワースト 2 を使う。
  • random: 各辺は自己ループを除いて一様ランダム。重みは $[1, 10^9]$ で一様ランダム。
  • complete: 自己ループを除いた全ての辺。重みは $[1, 10^9]$ で一様ランダム。
  • bimatchL: 二部グラフのマッチング。$L, R$ を頂点集合とし、$|L| = 50000, |R| = 20000$ として、各辺は $L$ から $R$ に一様ランダムに生成する。その後、$s \to L$, $R \to t$ に辺を追加した後のグラフ。元の問題の辺数は $150000$。番号は $L$, $R$, $s$, $t$ の順で付ける。
  • bimatchR: 上の問題で、$|L| = 20000, |R| = 50000$ としたもの。
  • bimatch: 上の問題で、$|L| = |R| = 50000$ としたもの。
  • bimatch2: 上の問題で、$|L| = |R| = 1000000$, $|E| = 3000000$ としたもの。

結果

時間の単位は 秒。複数種類用いるものは () で回数を示し、平均時間を計算した。-- は未実験。

Instance $V$ $E$ HI-PR (both) HI-PR (gl) HI-PR (gap) Dinic Dinic (R)
ak.c 20006 30007 1.428 1.437 1.657 5.000 3.583
ak.c 40006 60007 5.842 5.819 6.944 22.779 16.042
KZ2-venus7.max 321509 2213815 2.137 DNF 1.164 21.431 14.651
BL06-gargoyle-sml.max 1105922 5604568 2.933 DNF 0.854 11.539 12.644
worst2 598 30396 0.025 0.026 0.024 2.809 2.879
worst2 1198 120796 0.212 0.235 0.225 56.864 50.056
worst2 1798 271196 1.055 1.051 1.018 316.997 303.09
random (50) 50000 1000000 0.0202 0.0279 0.111 0.142 0.0744
complete (--) 3000 8997000 -- -- -- -- --
bimatchL (50) 70002 220000 0.081 1.11 0.085 0.040 0.037
bimatchR (50) 70002 220000 0.017 0.018 0.011 0.022 0.032
bimatch (50) 100002 250000 0.123 0.634 0.127 0.850 0.647
bimatch2 (10) 2000002 5000000 5.02 84.7 7.00 43.1 34.7

  • HI-PR (both) は両 heuristic あり、HI-PR (gl) は global のみ、HI-PR (gap) は gap のみ。
  • Dinic (R) は $s$ からの最短距離を測った後、$t \to s$ に流すタイプ。

まとめ

Push Relabel は普通に早かった。2 種の heuristic はどちらも強力で、片方あるだけで強い。ただし、片方はないと random 系などの問題は短時間では解けない。実験例が少ないけど、gap を含めるとロバストになる感じがする。