COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

Last modified 8 years ago

#417 closed enhancement (fixed)

Greatly improved implementation of CostScaling

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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

Attachments (3)

417-ca9d1dc77026--78d9eddfaf1a.patch (29.4 KB) - added by Peter Kovacs 9 years ago.
417-ca9d1dc77026--78d9eddfaf1a.bundle (5.5 KB) - added by Peter Kovacs 9 years ago.
417-bugfix-only-f112c18bc304.patch (930 bytes) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (11)

Changed 9 years ago by Peter Kovacs

Changed 9 years ago by Peter Kovacs

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

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)

comment:2 Changed 9 years ago by 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).

comment:3 Changed 9 years ago by 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.

comment:4 in reply to:  3 Changed 9 years ago by 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.

Changed 9 years ago by Peter Kovacs

comment:5 Changed 9 years ago by 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).

comment:6 Changed 9 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

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].

comment:7 Changed 9 years ago by Peter Kovacs

Thank you.

comment:8 Changed 8 years ago by Alpar Juttner

Type: defectenhancement
Note: See TracTickets for help on using tickets.