| Issue |
RAIRO-Oper. Res.
Volume 41, Number 3, July-September 2007
Journées Polyèdres et Optimisation Combinatoire
|
|
|---|---|---|
| Page(s) | 253 - 273 | |
| DOI | https://doi.org/10.1051/ro:2007023 | |
| Published online | 21 August 2007 | |
On the minimum cost multiple-source unsplittable flow problem
GET/INT - CNRS UMR 5157, Institut National des Télécommunications 9, rue Charles Fourier, 91011, Evry, France; walid.benameur@int.evry.fr
Received:
1
December
2006
Accepted:
21
December
2006
The minimum cost multiple-source unsplittable flow problem is studied in this paper. A simple necessary condition to get a solution is proposed. It deals with capacities and demands and can be seen as a generalization of the well-known semi-metric condition for continuous multicommdity flows. A cutting plane algorithm is derived using a superadditive approach. The inequalities considered here are valid for single knapsack constraints. They are based on nondecreasing superadditive functions and can be used to strengthen the relaxation of any integer program with knapsack constraints. Some numerical experiments confirm the efficiency of the inequalities introduced in the paper.
Mathematics Subject Classification: 90C10 / 90B18
Key words: Network flows / integer programming / superadditive functions
© EDP Sciences, ROADEF, SMAI, 2007
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.