# On the minimum cost multiple-source unsplittable flow problem

Meriema Belaidouni; Walid Ben-Ameur

RAIRO - Operations Research (2007)

- Volume: 41, Issue: 3, page 253-273
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBelaidouni, Meriema, and Ben-Ameur, Walid. "On the minimum cost multiple-source unsplittable flow problem." RAIRO - Operations Research 41.3 (2007): 253-273. <http://eudml.org/doc/250124>.

@article{Belaidouni2007,

abstract = {
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.
},

author = {Belaidouni, Meriema, Ben-Ameur, Walid},

journal = {RAIRO - Operations Research},

keywords = {Network flows; integer programming; superadditive functions; network flows},

language = {eng},

month = {8},

number = {3},

pages = {253-273},

publisher = {EDP Sciences},

title = {On the minimum cost multiple-source unsplittable flow problem},

url = {http://eudml.org/doc/250124},

volume = {41},

year = {2007},

}

TY - JOUR

AU - Belaidouni, Meriema

AU - Ben-Ameur, Walid

TI - On the minimum cost multiple-source unsplittable flow problem

JO - RAIRO - Operations Research

DA - 2007/8//

PB - EDP Sciences

VL - 41

IS - 3

SP - 253

EP - 273

AB -
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.

LA - eng

KW - Network flows; integer programming; superadditive functions; network flows

UR - http://eudml.org/doc/250124

ER -

## References

top- 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.
- 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. Zbl0775.90144
- Y. Asano, Experimental evaluation of approximation algorithms for the minimum cost multiple-source unsplittable flow problem. ICALP Workshop (2000) 111–122.
- A. Atamtürk and D. Rajan, On splittable and unsplittable flow capacitated network-design arc-set polyhedra. Math. Program.92 (2002) 315–333. Zbl1094.90005
- G. Baier, E. Köhler and M. Skutella, The k-splittable flow problem. Algorithmica42 (2005) 231–248. Zbl1086.90007
- 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.
- 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. Zbl0979.90092
- W. Ben-Ameur, E. Gourdin, B. Liau and N. Michel, Routing strategies for IP networks. In Telektronikk Magazine2/3 (2001) 145–158.
- W. Ben-Ameur, S. Besiktasliyan and B. Decocq, Optimal dimensioning of a ring. in Proceeding of ITC17, Brazil (2001).
- C.A. Burdet and E.L. Johnson, A subadditive approach to solve linear integer programs. Ann. Discrete Math.1 (1977) 117–144. Zbl0371.90103
- 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.
- 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. Zbl1026.90010
- CPLEX Optimization, Inc. Using the CPLEX Callabe Library and CPLEX Mixed Integer Library, version 7.1. (2001).
- G. Dahl, A. Martin and M. Stoer, Routing through virtual paths in layered telecommunication networks. Oper. Res.47 (1999) 693–702. Zbl0976.90014
- Y. Dinitz, N. Garg and M.X. Goemans, On the single-source unsplittable flow problem. Combinatorica19 (1999) 1–25. Zbl0947.90012
- J. Geffard, A 0-1 model for singly routed traffic in telecommunications. Ann. Telecom.56 (2001) 140–149.
- R.E. Gomory, E.L. Johnson and L. Evans, Corner polyhedra and their connection with cutting planes. Math. Program.96 (2003) 321–339. Zbl1082.90145
- 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.
- 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. Zbl1092.90527
- 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. Zbl1106.90381
- M. Iri, On an extension of the maximum-flow minimum-cut theorem to multicommdity flows. J. Oper. Res. Soc. Japan13 (1971) 129–135. Zbl0223.90010
- J.M. Kleinberg, Approximation algorithms for disjoint path problems. Ph.D. dissertation, M.I.T. (1996).
- S.G. Kolliopoulos and C. Stein, Approximation algorithms for single-source unsplittable flow. SIAM J. Comp.31 (2002) 919–946. Zbl1017.68058
- P. Kolman, A note on the greedy algorithm for the unsplittable flow problem. Information Processing Lett.88 (2003) 101–105. Zbl1178.68683
- M. Laguna and F. Glover, Bandwidth packing: a tabu search approach. Manag. Sci.39 (1993) 492–500. Zbl0774.90033
- D. Lorenz, A. Orda, D. Raz and Y. Shavitt, How good can IP routing be? DIMACS Technical Report 2001-17, May 2001.
- M.E. Lübbecke and J. Desrosiers, Selected Topics in Column Generation. Oper. Res.53 (2005) 1007–1023. Zbl1165.90578
- G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization. Wiley & Sons (1988). Zbl0652.90067
- K. Onaga and O. Kakusho, On feasibility conditions of multicommodity flows in networks. IEEE Tran. Circuit Theory4 (1971) 425–429.
- K. Park, S. Kang and S. Park, An integer programming approach to the bandwidth packing problem. Manage. Sci.42 (1996) 1277–1291. Zbl0880.90043
- 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.
- M. Parker and J.M. Ryan, A column generation algorithm for bandwidth packing. Telecom. Syst.2 (1993) 185–195.
- A. Schriver, P. Seymour and P. Winkler, The ring loading problem. SIAM J. Discrete Math.11 (1998) 1–14. Zbl0910.90135
- M. Skutella, Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B91 (2002) 493–514. Zbl1030.90109
- 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).
- W.E. Wilhelm, A technical review of column generation in integer programming. Optim. Eng.2 (2001) 159–200. Zbl1035.90047
- L.A. Wolsey, Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res.2 (1977) 66–77. Zbl0402.90066

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.