Multicommodity flow algorithms

[Peter Kovacs]

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.

[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/

[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 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.