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.
Mots clés : network flows, integer programming, superadditive functions
@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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro:2007023/
[1] , and, Network Flows. Prentice-Hall (1993). | MR
[2] and, Comparing Branch-and-price algorithms for the unsplittable multicommodity flow problem, in Proceedings of the International Network Optimization Conference INOC, Evry-Paris, France (2003) 7-12.
[3] ,, and, Path assignment for call routing: an application of Tabu search. Ann. Oper. Res. 41 (1993) 301-312. | Zbl
[4] , Experimental evaluation of approximation algorithms for the minimum cost multiple-source unsplittable flow problem. ICALP Workshop (2000) 111-122.
[5] and, On splittable and unsplittable flow capacitated network-design arc-set polyhedra. Math. Program. 92 (2002) 315-333. | Zbl
[6] , and, The k-splittable flow problem. Algorithmica 42 (2005) 231-248. | Zbl
[7] , and, Using branch-and-price to solve origin-destination integer multicommodity flow problems. Oper. Res. 48 (2000) 318-326.
[8] ,,, and, Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46 (1998) 316-329. | Zbl
[9] ,, and, Routing strategies for IP networks. In Telektronikk Magazine 2/3 (2001) 145-158.
[10] , and, Optimal dimensioning of a ring. in Proceeding of ITC17, Brazil (2001).
[11] and, A subadditive approach to solve linear integer programs. Ann. Discrete Math. 1 (1977) 117-144. | Zbl
[12] ,, and, Minimisation du nombre de chemins décomposant un flot, in Proceeding of Algotel (2004).
[13] and, Lightpath assignment for multifibers WDM networks with wavelength translators. Proceedings of the Global Telecommunications Conference (2002) 2686-2690.
[14] , and, Bundle-based relaxation methods for multicommodity capacitated fiwed charge network design. Discrete Appl. Math. 112 (2001) 73-99. | Zbl
[15] CPLEX Optimization, Inc. Using the CPLEX Callabe Library and CPLEX Mixed Integer Library, version 7.1. (2001).
[16] , and, Routing through virtual paths in layered telecommunication networks. Oper. Res. 47 (1999) 693-702. | Zbl
[17] , and, On the single-source unsplittable flow problem. Combinatorica 19 (1999) 1-25. | Zbl
[18] , A 0-1 model for singly routed traffic in telecommunications. Ann. Telecom. 56 (2001) 140-149.
[19] , and, Corner polyhedra and their connection with cutting planes. Math. Program. 96 (2003) 321-339. | Zbl
[20] , and, Cover inequalities for 0-1 linear programs: computation. INFORMS J. Comput. 10 (1998) 427-437. | Zbl
[21] , and, Cover inequalities for 0-1 linear programs: complexity. INFORMS J. Comput. 11 (1999) 117-123. | Zbl
[22] and, A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48 (2000) 461-481. | Zbl
[23] , On an extension of the maximum-flow minimum-cut theorem to multicommdity flows. J. Oper. Res. Soc. Japan 13 (1971) 129-135. | Zbl
[24] , Approximation algorithms for disjoint path problems. Ph.D. dissertation, M.I.T. (1996).
[25] and, Approximation algorithms for single-source unsplittable flow. SIAM J. Comp. 31 (2002) 919-946. | Zbl
[26] , A note on the greedy algorithm for the unsplittable flow problem. Information Processing Lett. 88 (2003) 101-105.
[27] and, Bandwidth packing: a tabu search approach. Manag. Sci. 39 (1993) 492-500. | Zbl
[28] ,, and, How good can IP routing be? DIMACS Technical Report 2001-17, May 2001.
[29] and, Selected Topics in Column Generation. Oper. Res. 53 (2005) 1007-1023.
[30] and, Integer and combinatorial optimization. Wiley & Sons (1988). | MR | Zbl
[31] and, On feasibility conditions of multicommodity flows in networks. IEEE Tran. Circuit Theory 4 (1971) 425-429.
[32] , and, An integer programming approach to the bandwidth packing problem. Manage. Sci. 42 (1996) 1277-1291. | Zbl
[33] , and, An Integer Programming Approach to the Path Selection Problems. Proceedings of the International Network Optimization Conference INOC, Evry-Paris, France (2003) 448-453.
[34] and, A column generation algorithm for bandwidth packing. Telecom. Syst. 2 (1993) 185-195.
[35] , and, The ring loading problem. SIAM J. Discrete Math. 11 (1998) 1-14. | Zbl
[36] , Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B 91 (2002) 493-514. | Zbl
[37] and, Explicit Routing Algorithms for Internet Traffic Engineering, in Proceedings of the International Conference on Computer Communication Networks, Boston, USA (1999).
[38] , A technical review of column generation in integer programming. Optim. Eng. 2 (2001) 159-200. | Zbl
[39] , Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res. 2 (1977) 66-77. | Zbl
Cité par Sources :
