COIN-OR::LEMON - Graph Library

Opened 14 years ago

Last modified 12 months 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)

ticket296.patch (52.6 KB) - added by David Torres Sanchez 12 months ago.

Download all attachments as: .zip

Change History (5)

comment:1 Changed 14 years ago by Peter Kovacs

I'm working on approximation algorithms for the following (fractional) problems according to Garg, Könemann and Fleischer.

  • maximum multicommodity flow,
  • weighted maximum multicommodity flow,
  • maximum concurrent flow,
  • min. cost maximum concurrent flow.

The working repository of these algorithms can be found here:
http://lime.cs.elte.hu/~kpeter/hgwebdir.cgi/lemon-multicommodity/

comment:2 Changed 13 years ago by Peter Kovacs

Milestone: LEMON 1.2 release
Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:3 Changed 13 years ago by Peter Kovacs

Type: enhancementtask

Changed 12 months ago by David Torres Sanchez

Attachment: ticket296.patch added

comment:4 Changed 12 months ago by David Torres Sanchez

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:

  1. Max (by refactoring Peter Kovacs' work),
  2. Max Concurrent,
  3. 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.

Last edited 12 months ago by David Torres Sanchez (previous) (diff)
Note: See TracTickets for help on using tickets.