COIN-OR::LEMON - Graph Library

Opened 14 years ago

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

Download all attachments as: .zip

Change History (7)

Changed 14 years ago by Peter Kovacs

comment:1 Changed 14 years ago by Alpar Juttner

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

comment:2 Changed 14 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 14 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 14 years ago by Peter Kovacs

comment:4 Changed 14 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 14 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed

[f3bc4e9b5f3a] went to the main branch.

Note: See TracTickets for help on using tickets.