Opened 15 years ago
Last modified 3 years ago
#296 assigned task
Multicommodity flow algorithms
Reported by: | Peter Kovacs | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
It would be important to implement various multicommodity flow algorithms in LEMON. Approximation (and maybe exact) solution methods for fractional, integral and unsplittable multicommodity flow problems.
Attachments (1)
Change History (5)
comment:1 Changed 15 years ago by
comment:2 Changed 15 years ago by
Milestone: | LEMON 1.2 release |
---|---|
Owner: | changed from Alpar Juttner to Peter Kovacs |
Status: | new → assigned |
comment:3 Changed 15 years ago by
Type: | enhancement → task |
---|
Changed 3 years ago by
Attachment: | ticket296.patch added |
---|
comment:4 Changed 3 years ago by
I cloned the lime repo linked above and worked from there. The patch attached ticket296.patch is with respect to the lemon/multicommodity_flow.h
file in the lime repo.
Also, note that the patch is compatible with the current version of the lemon main repo (as I've developed it in there).
Here's where I've gotten so far. Please bear in mind that it is pretty rough, tried to adhere to the style of the other algorithms and it's not completely finished yet (unnecessary comments lying around). However, I never find the time to finish it properly, so I think this is good for now. Also I can benefit from a review to see if its not completely unusable.
In the patch attached, you can find three algorithms from the Fleischer paper:
- Max (by refactoring Peter Kovacs' work),
- Max Concurrent,
- Min cost (using binary search and the Max concurrent algorithm).
As well an randomised rounding heuristic (for the max concurrent and in case the flow can be routing through a single path) and some preprocessing checks.
I'm working on approximation algorithms for the following (fractional) problems according to Garg, Könemann and Fleischer.
The working repository of these algorithms can be found here:
http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-multicommodity/