最小費用流問題(Cost Scaling)[2]

前回の Cost Scaling の実装を改善する。

改善

前回の実装では、高速化に繋がると思って毎回 Minimum Mean Cycle を求めていたのだけれども、実際は求めない方が大半の例で高速に動作した。400 行ぐらい減らせて、メモリ効率もよくなり、多くの例で 2〜3 倍程度速くなった。

問題名 $V$ $E$ 最適値 前回 今回 Lemon
goto_8_08a.min 256 2048 560870539 0.036 0.022 0.006
goto_8_10a.min 1024 8192 1861135786 0.302 0.257 0.037
goto_8_12a.min 4096 32768 6133066146 5.406 2.516 0.311
goto_8_14a.min 16384 131072 42104991210 123.1 76.4 2.323
goto_8_16a.min 65536 524288 205664925703 2446 1742 20.3
goto_sr_12a.min 4096 262144 59460562987 34.6 26.2 2.32
gridgen_8_14a.min 16385 131080 1913362845 1.19 0.496 0.365
gridgen_8_16a.min 65537 524296 3391613068 6.79 2.37 2.21
netgen_8_14a.min 16384 131072 1772056888 1.18 0.550 0.455
netgen_8_16a.min 65536 524288 4023172764 9.11 2.59 2.51
netgen_sr_14a.min 16384 2097152 132201189 13.5 3.74 4.15
netgen_lo_8_14a.min 16384 131072 12166598 0.718 0.208 0.227
netgen_lo_8_16a.min 65536 524288 27302646 4.80 1.07 1.51
vision_inv_02_..._n6c100_a.min 491522 2877382 25108031 51.7 77.4 51.6
vision_prop_02_..._n6c100_a.min 491522 2877382 1250516158 85.0 77.9 58.1
vision_rnd_02_..._n6c100_a.min 491522 2877382 79362008 50.1 41.7 39.0

Verify 用の問題

$s \to t$ への総流量が小さい場合はやはり SSP の方が有利で、使い分けた方が良さそう(H: キャッシュ戦略 - UTPC 2011 | AtCoder など)。

ソースコード

全体で 200 行程度で、内 Dinic が 70 行ぐらい。
relabel_in_advance 関数のみが heuristic で、1.5 倍ぐらいほど速くなる。

capacity 関数: $b(e), c(e)$(流量 $f(e)$ は $b(e) \le f(e) \le c(e)$ を満たす)と cost 関数: $\gamma(e)$ は負でも大丈夫。


更新履歴

  • 2018-2-18: Lemon の実装を ListDigraph から SmartDigraph に変更。入力によっては 10 % 程度改善されるが、実行時間に変化がないものも多い。StaticDigraph の実行時間はまだ見ていない。