COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#340 closed enhancement (done)

New heuristics in MCF algorithms

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

Description

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 Peter Kovacs 9 years ago.
340-mcf-heur-and-impr-f3bc4e9b5f3a.patch (31.9 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (7)

Changed 9 years ago by Peter Kovacs

comment:1 Changed 9 years ago by Alpar Juttner

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

comment:2 Changed 9 years ago by Alpar Juttner

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 Peter Kovacs

Status: newassigned

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 9 years ago by Peter Kovacs

comment:4 Changed 9 years ago by Peter Kovacs

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 9 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed

[f3bc4e9b5f3a] went to the main branch.

Note: See TracTickets for help on using tickets.