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

Abstract

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

How to cite

top

Belaidouni, 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
  1. R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice-Hall (1993).  
  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.  Zbl0775.90144
  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.  Zbl1094.90005
  6. G. Baier, E. Köhler and M. Skutella, The k-splittable flow problem. Algorithmica42 (2005) 231–248.  Zbl1086.90007
  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.  Zbl0979.90092
  9. W. Ben-Ameur, E. Gourdin, B. Liau and N. Michel, Routing strategies for IP networks. In Telektronikk Magazine2/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.  Zbl0371.90103
  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.  Zbl1026.90010
  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.  Zbl0976.90014
  17. Y. Dinitz, N. Garg and M.X. Goemans, On the single-source unsplittable flow problem. Combinatorica19 (1999) 1–25.  Zbl0947.90012
  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.  Zbl1082.90145
  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.  
  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.  Zbl1092.90527
  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.  Zbl1106.90381
  23. 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
  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.  Zbl1017.68058
  26. P. Kolman, A note on the greedy algorithm for the unsplittable flow problem. Information Processing Lett.88 (2003) 101–105.  Zbl1178.68683
  27. M. Laguna and F. Glover, Bandwidth packing: a tabu search approach. Manag. Sci.39 (1993) 492–500.  Zbl0774.90033
  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.  Zbl1165.90578
  30. G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization. Wiley & Sons (1988).  Zbl0652.90067
  31. K. Onaga and O. Kakusho, On feasibility conditions of multicommodity flows in networks. IEEE Tran. Circuit Theory4 (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.  Zbl0880.90043
  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.  Zbl0910.90135
  36. M. Skutella, Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B91 (2002) 493–514.  Zbl1030.90109
  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.  Zbl1035.90047
  39. L.A. Wolsey, Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res.2 (1977) 66–77.  Zbl0402.90066

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.