On the minimum cost multiple-source unsplittable flow problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 253-273.

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
Mots clés : 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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro:2007023/

[1] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice-Hall (1993). | MR

[2] F. Alvelos and J.M. Valério De Carvalho, 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] C.A. Anderson, F. Fraughnaugh, M. Parker and J. Ryan, Path assignment for call routing: an application of Tabu search. Ann. Oper. Res. 41 (1993) 301-312. | Zbl

[4] Y. Asano, Experimental evaluation of approximation algorithms for the minimum cost multiple-source unsplittable flow problem. ICALP Workshop (2000) 111-122.

[5] A. Atamtürk and D. Rajan, On splittable and unsplittable flow capacitated network-design arc-set polyhedra. Math. Program. 92 (2002) 315-333. | Zbl

[6] G. Baier, E. Köhler and M. Skutella, The k-splittable flow problem. Algorithmica 42 (2005) 231-248. | Zbl

[7] C. Barnhart, C.A. Hane and P.H. Vance, Using branch-and-price to solve origin-destination integer multicommodity flow problems. Oper. Res. 48 (2000) 318-326.

[8] C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsberg and P.H. Vance, Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46 (1998) 316-329. | Zbl

[9] W. Ben-Ameur, E. Gourdin, B. Liau and N. Michel, Routing strategies for IP networks. In Telektronikk Magazine 2/3 (2001) 145-158.

[10] W. Ben-Ameur, S. Besiktasliyan and B. Decocq, Optimal dimensioning of a ring. in Proceeding of ITC17, Brazil (2001).

[11] C.A. Burdet and E.L. Johnson, A subadditive approach to solve linear integer programs. Ann. Discrete Math. 1 (1977) 117-144. | Zbl

[12] F. Chauvet, P. Chrétienne, P. Mahey and B. Vatinlen, Minimisation du nombre de chemins décomposant un flot, in Proceeding of Algotel (2004).

[13] D. Coudert and H. Rivano, Lightpath assignment for multifibers WDM networks with wavelength translators. Proceedings of the Global Telecommunications Conference (2002) 2686-2690.

[14] T.G. Crainic, A. Frangioni and B. Gendron, 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] G. Dahl, A. Martin and M. Stoer, Routing through virtual paths in layered telecommunication networks. Oper. Res. 47 (1999) 693-702. | Zbl

[17] Y. Dinitz, N. Garg and M.X. Goemans, On the single-source unsplittable flow problem. Combinatorica 19 (1999) 1-25. | Zbl

[18] J. Geffard, A 0-1 model for singly routed traffic in telecommunications. Ann. Telecom. 56 (2001) 140-149.

[19] R.E. Gomory, E.L. Johnson and L. Evans, Corner polyhedra and their connection with cutting planes. Math. Program. 96 (2003) 321-339. | Zbl

[20] Z. Gu, G.L. Nemhauser and M.W.P. Savelsbergh, Cover inequalities for 0-1 linear programs: computation. INFORMS J. Comput. 10 (1998) 427-437. | Zbl

[21] Z. Gu, G.L. Nemhauser and M.W.P. Savelsbergh, Cover inequalities for 0-1 linear programs: complexity. INFORMS J. Comput. 11 (1999) 117-123. | Zbl

[22] K. Holmberg and D. Yuan, A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48 (2000) 461-481. | Zbl

[23] M. Iri, On an extension of the maximum-flow minimum-cut theorem to multicommdity flows. J. Oper. Res. Soc. Japan 13 (1971) 129-135. | Zbl

[24] J.M. Kleinberg, Approximation algorithms for disjoint path problems. Ph.D. dissertation, M.I.T. (1996).

[25] S.G. Kolliopoulos and C. Stein, Approximation algorithms for single-source unsplittable flow. SIAM J. Comp. 31 (2002) 919-946. | Zbl

[26] P. Kolman, A note on the greedy algorithm for the unsplittable flow problem. Information Processing Lett. 88 (2003) 101-105.

[27] M. Laguna and F. Glover, Bandwidth packing: a tabu search approach. Manag. Sci. 39 (1993) 492-500. | Zbl

[28] D. Lorenz, A. Orda, D. Raz and Y. Shavitt, How good can IP routing be? DIMACS Technical Report 2001-17, May 2001.

[29] M.E. Lübbecke and J. Desrosiers, Selected Topics in Column Generation. Oper. Res. 53 (2005) 1007-1023.

[30] G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization. Wiley & Sons (1988). | MR | Zbl

[31] K. Onaga and O. Kakusho, On feasibility conditions of multicommodity flows in networks. IEEE Tran. Circuit Theory 4 (1971) 425-429.

[32] K. Park, S. Kang and S. Park, An integer programming approach to the bandwidth packing problem. Manage. Sci. 42 (1996) 1277-1291. | Zbl

[33] S. Park, D. Kim and K. Lee, An Integer Programming Approach to the Path Selection Problems. Proceedings of the International Network Optimization Conference INOC, Evry-Paris, France (2003) 448-453.

[34] M. Parker and J.M. Ryan, A column generation algorithm for bandwidth packing. Telecom. Syst. 2 (1993) 185-195.

[35] A. Schriver, P. Seymour and P. Winkler, The ring loading problem. SIAM J. Discrete Math. 11 (1998) 1-14. | Zbl

[36] M. Skutella, Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B 91 (2002) 493-514. | Zbl

[37] Y. Wang and Z. Wang, Explicit Routing Algorithms for Internet Traffic Engineering, in Proceedings of the International Conference on Computer Communication Networks, Boston, USA (1999).

[38] W.E. Wilhelm, A technical review of column generation in integer programming. Optim. Eng. 2 (2001) 159-200. | Zbl

[39] L.A. Wolsey, Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res. 2 (1977) 66-77. | Zbl

Cité par Sources :