Greatly improved implementation of CostScaling

[Peter Kovacs]

The attached changesets greatly improve the efficiency of CostScaling algorithm. Moreover, a bug fix is also included.

[Peter Kovacs]

I attached 5 changesets (both in a patch file and in a bundle file):

• [ca9d1dc77026] Minor improvements in CostScaling (#417)
• [4866b640dba9] Fix and improve refine methods in CostScaling (#417). The old implementation could run into infinite loop using the AUGMENT method.
• [f88191cb740f] Implement the scaling Price Refinement heuristic in CostScaling (#417) instead of Early Termination. These two heuristics are similar, but the newer one is faster and not only makes it possible to skip some epsilon phases, but it can improve the performance of the other phases, as well.
• [482ff194df93] Faster computation of the dual solution in CostScaling (#417)
• [78d9eddfaf1a] Change the default scaling factor in CostScaling (#417)

[Peter Kovacs]

These changes all together improve the overall performance of CostScaling by a factor of 1.5 on average (according to thorough benchmark tests).

[Alpar Juttner]

The improvement is really impressive. Is there an up-to-date comparison of the min-cost flow algs in LEMON (an perhaps some comparison to other graph libs).

Also, shouldn't we backport the bugfix to version 1.2? Unfortunately I can't easily separate it from the other changes.

[Peter Kovacs]

Replying to alpar:

The improvement is really impressive. Is there an up-to-date comparison of the min-cost flow algs in LEMON (an perhaps some comparison to other graph libs).

I will create such comparisons soon. And I'd like to write a paper about our implementations and these comparisons (in a few months).

Also, shouldn't we backport the bugfix to version 1.2? Unfortunately I can't easily separate it from the other changes.

I can easily create a simple patch that only fixes the bug. I will attach it soon, but these changesets could be kept for the main branch.

[Peter Kovacs]

I attached the simple bug fix [f112c18bc304]. This bug fix can be merged into branch 1.2, and maybe to the main branch, as well. But note that the previous changesets also contain these modifications along with other improvements (see [4866b640dba9]) that fixes the issue independently (and makes the algorithm faster in AUGMENT mode).

[Alpar Juttner]

The bug fix [f112c18bc304] has been merged into branches 1.2 and the main. All the remaining changes has been merged into the main branch as [fe283caf6414], [6ea176638264], [ddd3c0d3d9bf], [1226290a9b7d] and [a07b6b27fe69].

[Peter Kovacs]

Thank you.