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.  
  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.  
  6. G. Baier, E. Köhler and M. Skutella, The k-splittable flow problem. Algorithmica42 (2005) 231–248.  
  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.  
  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.  
  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.  
  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.  
  17. Y. Dinitz, N. Garg and M.X. Goemans, On the single-source unsplittable flow problem. Combinatorica19 (1999) 1–25.  
  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.  
  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.  
  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.  
  23. M. Iri, On an extension of the maximum-flow minimum-cut theorem to multicommdity flows. J. Oper. Res. Soc. Japan13 (1971) 129–135.  
  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.  
  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.  
  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).  
  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.  
  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.  
  36. M. Skutella, Approximating the single-source unsplittable min-cost flow problem. Math. Program. Ser. B91 (2002) 493–514.  
  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.  
  39. L.A. Wolsey, Valid inequalities and superadditivity for 0-1 integer programs. Math. Oper. Res.2 (1977) 66–77.  

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.