Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-24T11:08:56.112Z Has data issue: false hasContentIssue false
  • English
  • Français

On the minimum cost multiple-source unsplittable flow problem

Published online by Cambridge University Press:  21 August 2007

Meriema Belaidouni  and
Walid Ben-Ameur
Meriema Belaidouni
Affiliation:
GET/INT - CNRS UMR 5157, Institut National des Télécommunications 9, rue Charles Fourier, 91011, Evry, France; [email protected]
Walid Ben-Ameur
Affiliation:
GET/INT - CNRS UMR 5157, Institut National des Télécommunications 9, rue Charles Fourier, 91011, Evry, France; [email protected]
Get access

Abstract

The minimum cost multiple-source unsplittable flow problem isstudied in this paper. A simple necessary condition to get asolution is proposed. It deals with capacities and demands and canbe seen as a generalization of the well-known semi-metriccondition for continuous multicommdity flows. A cutting planealgorithm is derived using a superadditive approach. Theinequalities considered here are valid for single knapsackconstraints. They are based on nondecreasing superadditivefunctions and can be used to strengthen the relaxation of anyinteger program with knapsack constraints. Some numericalexperiments confirm the efficiency of the inequalities introducedin the paper.

Keywords

Network flowsinteger programmingsuperadditive functions
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 3: Journées Polyèdres et Optimisation Combinatoire , July 2007 , pp. 253 - 273
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice-Hall (1993).
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.
Anderson, C.A., Fraughnaugh, F., Parker, M. and Ryan, J., Path assignment for call routing: an application of Tabu search. Ann. Oper. Res. 41 (1993) 301–312. CrossRef
Y. Asano, Experimental evaluation of approximation algorithms for the minimum cost multiple-source unsplittable flow problem. ICALP Workshop (2000) 111–122.
Atamtürk, A. and Rajan, D., On splittable and unsplittable flow capacitated network-design arc-set polyhedra. Math. Program. 92 (2002) 315–333. CrossRef
Baier, G., Köhler, E. and Skutella, M., The k-splittable flow problem. Algorithmica 42 (2005) 231–248. CrossRef
Barnhart, C., Hane, C.A. and Vance, P.H., Using branch-and-price to solve origin-destination integer multicommodity flow problems. Oper. Res. 48 (2000) 318–326. CrossRef
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsberg, M.W.P. and Vance, P.H., Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46 (1998) 316–329. CrossRef
W. Ben-Ameur, E. Gourdin, B. Liau and N. Michel, Routing strategies for IP networks. In Telektronikk Magazine 2/3 (2001) 145–158.
W. Ben-Ameur, S. Besiktasliyan and B. Decocq, Optimal dimensioning of a ring. in Proceeding of ITC17, Brazil (2001).
Burdet, C.A. and Johnson, E.L., A subadditive approach to solve linear integer programs. Ann. Discrete Math. 1 (1977) 117–144. CrossRef
F. Chauvet, P. Chrétienne, P. Mahey and B. Vatinlen, Minimisation du nombre de chemins décomposant un flot, in Proceeding of Algotel (2004).
D. Coudert and H. Rivano, Lightpath assignment for multifibers WDM networks with wavelength translators. Proceedings of the Global Telecommunications Conference (2002) 2686–2690.
Crainic, T.G., Frangioni, A. and Gendron, B., Bundle-based relaxation methods for multicommodity capacitated fiwed charge network design. Discrete Appl. Math. 112 (2001) 73–99. CrossRef
CPLEX Optimization, Inc. Using the CPLEX Callabe Library and CPLEX Mixed Integer Library, version 7.1. (2001).
Dahl, G., Martin, A. and Stoer, M., Routing through virtual paths in layered telecommunication networks. Oper. Res. 47 (1999) 693–702. CrossRef
Dinitz, Y., Garg, N. and Goemans, M.X., On the single-source unsplittable flow problem. Combinatorica 19 (1999) 1–25. CrossRef
Geffard, J., A 0-1 model for singly routed traffic in telecommunications. Ann. Telecom. 56 (2001) 140–149.
Gomory, R.E., Johnson, E.L. and Evans, L., Corner polyhedra and their connection with cutting planes. Math. Program. 96 (2003) 321–339. CrossRef
Gu, Z., Nemhauser, G.L. and Savelsbergh, M.W.P., Cover inequalities for 0-1 linear programs: computation. INFORMS J. Comput. 10 (1998) 427–437. CrossRef
Gu, Z., Nemhauser, G.L. and Savelsbergh, M.W.P., Cover inequalities for 0-1 linear programs: complexity. INFORMS J. Comput. 11 (1999) 117–123. CrossRef
Holmberg, K. and Yuan, D., Lagrangian, A heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48 (2000) 461–481. CrossRef
Iri, M., On an extension of the maximum-flow minimum-cut theorem to multicommdity flows. J. Oper. Res. Soc. Japan 13 (1971) 129–135.
J.M. Kleinberg, Approximation algorithms for disjoint path problems. Ph.D. dissertation, M.I.T. (1996).
Kolliopoulos, S.G. and Stein, C., Approximation algorithms for single-source unsplittable flow. SIAM J. Comp. 31 (2002) 919–946. CrossRef
Kolman, P., A note on the greedy algorithm for the unsplittable flow problem. Information Processing Lett. 88 (2003) 101–105. CrossRef
Laguna, M. and Glover, F., Bandwidth packing: a tabu search approach. Manag. Sci. 39 (1993) 492–500. CrossRef
D. Lorenz, A. Orda, D. Raz and Y. Shavitt, How good can IP routing be? DIMACS Technical Report 2001-17, May 2001.
Lübbecke, M.E. and Desrosiers, J., Selected Topics in Column Generation. Oper. Res. 53 (2005) 1007–1023. CrossRef
G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization. Wiley & Sons (1988).
Onaga, K. and Kakusho, O., On feasibility conditions of multicommodity flows in networks. IEEE Tran. Circuit Theory 4 (1971) 425–429. CrossRef
Park, K., Kang, S. and Park, S., An integer programming approach to the bandwidth packing problem. Manage. Sci. 42 (1996) 1277–1291. CrossRef
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.
Parker, M. and Ryan, J.M., A column generation algorithm for bandwidth packing. Telecom. Syst. 2 (1993) 185–195. CrossRef
Schriver, A., Seymour, P. and Winkler, P., The ring loading problem. SIAM J. Discrete Math. 11 (1998) 1–14. CrossRef
Skutella, M., Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B 91 (2002) 493–514. CrossRef
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).
Wilhelm, W.E., A technical review of column generation in integer programming. Optim. Eng. 2 (2001) 159–200. CrossRef
Wolsey, L.A., Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res. 2 (1977) 66–77. CrossRef