Networks; OR in telecommunications; Unsplittable flows; Integer programming; Combinatorial optimization
Abstract :
[en] In this paper, we consider multicommodity flow problems, with unsplittable flows and piecewise linear routing costs. We first focus on the case where the piecewise linear routing costs are convex. We show that this problem is
-hard for the general case, but polynomially solvable when there is only one commodity. We then propose a strengthened mixed-integer programming formulation for the problem. We show that the linear relaxation of this formulation always gives the optimal solution of the problem for the single commodity case. We present a wide array of computational experiments, showing this formulation also produces very tight linear programming bounds for the multi-commodity case. Finally, we also adapt our formulation for the non-convex case. Our experimental results imply that the linear programming bounds for this case, are only slightly weaker than the ones of state-of-the-art models for the splittable flow version of the problem.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Gouveia, L.
Joyce-Moniz, M.
Language :
English
Title :
Models for the piecewise linear unsplittable multicommodity flow problems
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Alvelos, F., de Carvalho, J.V., Comparing branch-and-price algorithms for the unsplittable multicommodity flow problem. Proceedings of the International Network Optimization Conference, 2003, 7–12.
Atamtürk, A., Rajan, D., On splittable and unsplittable flow capacitated network design arc–set polyhedra. Mathematical Programming 92:2 (2002), 315–333.
Balakrishnan, A., Graves, S.C., A composite algorithm for a concave-cost network flow problem. Networks 19:2 (1989), 175–202.
Balon, S., Skivée, F., Leduc, G., How well do traffic engineering objective functions meet the requirements?. Proceedings of the International Conference on Research in Networking, 2006, 75–86.
Barnhart, C., Hane, C.A., Vance, P.H., Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research 48:2 (2000), 318–326.
Belaidouni, M., Ben-Ameur, W., On the minimum cost multiple-source unsplittable flow problem. RAIRO-Operations Research 41:3 (2007), 253–273.
Benhamiche, A., Mahjoub, A.R., Perrot, N., Uchoa, E., Unsplittable non-additive capacitated network design using set functions polyhedra. Computers & Operations Research 66 (2016), 105–115.
Cox, L.A., Davis, L., Qiu, Y., Dynamic anticipatory routing in circuit-switched telecommunications networks. Handbook of Genetic Algorithms 11 (1991), 229–340.
Croxton, K.L., Gendron, B., Magnanti, T.L., A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Management Science 49:9 (2003), 1268–1273.
Croxton, K.L., Gendron, B., Magnanti, T.L., Variable disaggregation in network flow problems with piecewise linear costs. Operations research 55:1 (2007), 146–157.
Fortz, B., Gorgone, E., Papadimitriou, D., A Lagrangian heuristic algorithm for the time-dependent combined network design and routing problem. Networks 69:1 (2017), 110–123.
Fortz, B., Gouveia, L., Joyce-Moniz, M., On the convex piecewise linear unsplittable multicommodity flow problem. Proceedings of the 12th international conference on the design of reliable communication networks, 2016, 9–13.
Fortz, B., Gouveia, L., Joyce-Moniz, M., Optimal design of switched ethernet networks implementing the multiple spanning tree protocol. Discrete Applied Mathematics, 2017 (in press). http://dx.doi.org/10.1016/j.dam.2016.07.015.
Fortz, B., Thorup, M., Internet traffic engineering by optimizing OSPF weights. Proceedings of the nineteenth annual joint conference of the IEEE sieties, 2, 2000, 519–528.
Fortz, B., Thorup, M., Increasing internet capacity using local search. Computational Optimization and Applications 29:1 (2004), 13–48.
Geffard, J., A solving method for singly routing traffic demand in telecommunication networks. Annales des télécommunications 56 (2001), 140–149.
Gendron, B., Gouveia, L., Reformulations by discretization for piecewise linear integer multicommodity network flow problems. Transportation Science, 2017 (in press). http://dx.doi.org/10.1287/trsc.2015.0634.
Gourdin, E., Klopfenstein, O., Comparison of different QoS-oriented objectives for multicommodity flow routing optimization. Proceedings of the international conference on telecommunications, 2006.
Ho, T.-V., Deville, Y., Bonaventure, O., Francois, P., Traffic engineering for multiple spanning tree protocol in large data centers. Proceedings of the 23rd IEEE international teletraffic congress, 2011, 23–30.
Joyce-Moniz, M., Models and methods for traffic engineering problems with single-path routing, 2016, Université Libre de Bruxelles, Belgium Ph.d. thesis.
Karp, R.M., Reducibility among combinatorial problems. 1972, Springer, New York.
Kleinberg, J.M., Single-source unsplittable flow. Proceedings of the 37th annual symposium on foundations of computer science, 1996, 68–77.
Kleinrock, L., Communication nets: stochastic message flow and delay. 1964, Courier Corporation, New York.
Lemaréchal, C., Ouorou, A., Petrou, G., A bundle-type algorithm for routing in telecommunication data networks. Computational Optimization and Applications 44:3 (2007), 385–409.
Liu, X., Mohanraj, S., Pióro, M., Medhi, D., Multipath routing from a traffic engineering perspective: How beneficial is it?. Proceedings of the 22nd IEEE international conference on network protocols, 2014, 143–154.
Orlowski, S., Wessäly, R., Pióro, M., Tomaszewski, A., SNDlib 1.0 survivable network design library. Networks 55:3 (2010), 276–286.
Papadimitriou, D., Fortz, B., Methods for time-dependent combined network design and routing optimization. Proceedings of the IEEE global communications conference, 2014, 1303–1309.
Papadimitriou, D., Fortz, B., Time-dependent combined network design and routing optimization. Proceedings of the IEEE international conference on communications, 2014, 1124–1130.
Park, K., Kang, S., Park, S., An integer programming approach to the bandwidth packing problem. Management Science 42:9 (1996), 1277–1291.
Parker, M., Ryan, J., A column generation algorithm for bandwidth packing. Telecommunication Systems 2:1 (1993), 185–195.
Pióro, M., Medhi, D., Routing, flow, and capacity design in communication and computer networks. 2004, Elsevier, San Francisco.
Salman, F.S., Ravi, R., Hooker, J.N., Solving the capacitated local access network design problem. INFORMS Journal on Computing 20:2 (2008), 243–254.
Santos, D., De Sousa, A., Alvelos, F., A hybrid column generation with grasp and path relinking for the network load balancing problem. Computers & Operations Research 40:12 (2013), 3147–3158.
Santos, D., de Sousa, A., Alvelos, F., Dzida, M., Pióro, M., Optimization of link load balancing in multiple spanning tree routing networks. Telecommunication Systems 48:1–2 (2010), 109–124.
Santos, D., de Sousa, A., Alvelos, F., Pióro, M., Optimizing network load balancing: an hybridization approach of metaheuristics with column generation. Telecommunication Systems 52:2 (2013), 959–968.
Vielma, J.P., Ahmed, S., Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Operations research 58:2 (2010), 303–315.
Wolsey, L.A., Integer programming. Series in discrete mathematics and optimization, 1998, Wiley-Interscience, New York.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
