COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 8 years ago

#340 closed enhancement (done)

New heuristics in MCF algorithms

Reported by: kpeter Owned by: kpeter
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:


The attached patch contains implementation improvements and new heuristics for MCF algorithms.

Attachments (2)

340-mcf-new-heur-87ff083a3f6b.patch (27.6 KB) - added by kpeter 9 years ago.
340-mcf-heur-and-impr-f3bc4e9b5f3a.patch (31.9 KB) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (7)

Changed 9 years ago by kpeter

comment:1 follow-up: Changed 9 years ago by alpar

Does this patch matured enough to be included into lemon-1.2?

comment:2 Changed 9 years ago by alpar

I noticed that you replaced bool vectors to char at several placed, perhaps for performance reason. It's clear that you have carefully evaluated this change. However, I still have the feeling that the right choice here highly depends on the platform and also on the actual implementation of std::vector<>. Thus I suggest including comments at these places clarifying that these std::vector<char>s are actually bool ones, char is used only for the sake of performance.

comment:3 in reply to: ↑ 1 Changed 9 years ago by kpeter

  • Status changed from new to assigned

Replying to alpar:

Does this patch matured enough to be included into lemon-1.2?

Yes, it does. It was checked on almost all input files I have. However, I will most likely make further improvements in the CostScaling algorithm, because it does not give right solution for some very large instances (overflow problems?). This problem seems to be independent from the new heuristics.

This patch is not critical, but I wil need it for a paper soon, in which citing LEMON 1.2 would be better than an "upcomming release", wouldn't it?

Changed 8 years ago by kpeter

comment:4 Changed 8 years ago by kpeter

I attached a better version of the former patch, see [f3bc4e9b5f3a].
The two differences are the followings:

  • Better relabeling in CostScaling to improve numerical stability and to make the code slightly faster.
  • Notes are added to the classes about the usage of vector<char> instead of vector<bool> for efficiency reasons. (As Alpar suggested.)

This changeset is matured and tested enough to add to the main branch. Note that there are users how are interested in the performance of our cost scaling implementation (apart from my preferences about adding this changeset to release 1.2).

comment:5 Changed 8 years ago by kpeter

  • Resolution set to done
  • Status changed from assigned to closed

[f3bc4e9b5f3a] went to the main branch.

Note: See TracTickets for help on using tickets.