Geodesic
On the minimum cost multiple-source unsplittable flow problem
Belaidouni, Meriema  ; Ben-Ameur, Walid1
1 GET/INT - CNRS UMR 5157, Institut National des Télécommunications 9, rue Charles Fourier, 91011, Evry, France
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 253-273

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ro:2007023
Classification : 90C10, 90B18
Keywords: network flows, integer programming, superadditive functions

Belaidouni, Meriema  ; Ben-Ameur, Walid 1

1 GET/INT - CNRS UMR 5157, Institut National des Télécommunications 9, rue Charles Fourier, 91011, Evry, France 
@article{RO_2007__41_3_253_0,
     author = {Belaidouni, Meriema and Ben-Ameur, Walid},
     title = {On the minimum cost multiple-source unsplittable flow problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {253--273},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ro:2007023},
     mrnumber = {2348001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2007023/}
}
TY  - JOUR
AU  - Belaidouni, Meriema
AU  - Ben-Ameur, Walid
TI  - On the minimum cost multiple-source unsplittable flow problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2007
SP  - 253
EP  - 273
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2007023/
DO  - 10.1051/ro:2007023
LA  - en
ID  - RO_2007__41_3_253_0
ER  - 
%0 Journal Article
%A Belaidouni, Meriema
%A Ben-Ameur, Walid
%T On the minimum cost multiple-source unsplittable flow problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 253-273
%V 41
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2007023/
%R 10.1051/ro:2007023
%G en
%F RO_2007__41_3_253_0
Belaidouni, Meriema; Ben-Ameur, Walid. On the minimum cost multiple-source unsplittable flow problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 253-273. doi: 10.1051/ro:2007023

Cité par Sources :