[en] Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput.10(2) 180–188], we present a formulation for the problem valid for any K, L ≥ 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L ≥ 5. Whereas some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real-based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Botton, Q.
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
Gouveia, L.
Poss, M.
Language :
English
Title :
Benders decomposition for the hop-constrained survivable network design problem
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.
Achterberg, T., C. Raack. 2010. The MCF-separator - Detecting and exploiting multi-commodity flows in MIPs. Math. Programming C 2(2) 125-165.
Bai, L., P. A. Rubin. 2009. Combinatorial Benders cuts for the minimum toll booth problem. Oper. Res. 57(6) 1510-1522.
Balakrishnan, A., K. Altinkemer. 1992. Using a hop-constrained model to generate alternative communication network design. ORSA J. Comput. 4(2) 192-205.
Benders, J. 1962. Partitioning procedures for solving mixedvariables programming problems. Numerische Mathematik 4 238-252.
Birge, J. R., F. Louveaux. 2008. Introduction to Stochastic Programming, 2nd ed. Springer-Verlag, New York.
Bley, A. 1997. Node-disjoint length-restricted paths. Master's thesis, Technische Universität Berlin, Berlin.
Bley, A., J. Neto. 2010. Approximability of 3- and 4-hop bounded disjoint paths problems. F. Eisenbrand, F. B. Shepherd, eds. Proc. Integer Programming Combinat. Optim. (IPCO 2010). Lecture Notes in Computer Science, Vol. 6080. Springer, Berlin, 205-218.
Carøe, C. C., J. Tind. 1998. L-shaped decomposition of two-stage stochastic programs with integer recourse. Math. Programming 83(1-3) 451-464. (Pubitemid 128431424)
Codato, G., M. Fischetti. 2006. Combinatorial Benders' cuts for mixed-integer linear programming. Oper. Res. 54(4) 756-766. (Pubitemid 44521585)
Costa, A. M. 2005. A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6) 1429-1450.
Dahl, G. 1999. Notes on polyhedra associated with hop-constrained walk polytopes. Oper. Res. Lett. 25(2) 97-100.
Dahl, G., L. Gouveia. 2004. On the directed hop-constrained shortest path problem. Oper. Res. Lett. 32(1) 15-22.
Dahl, G., B. Johannessen. 2004. The 2-path network problem. Networks 43(3) 190-199. (Pubitemid 38700756)
Dahl, G., M. Stoer. 1998. A cutting plane algorithm for multicommodity survivable network design problems. INFORMS J. Comput. 10(1) 1-11. (Pubitemid 128666513)
Dahl, G., N. Foldnes, L. Gouveia. 2004. A note on hop-constrained walk polytopes. Oper. Res. Lett. 32(4) 345-349.
Dahl, G., D. Huygens, A. R. Mahjoub, P. Pesneau. 2006. On the k edge-disjoint 2-hop-constrained paths polytope. Oper. Res. Lett. 34(5) 577-582. (Pubitemid 43851078)
Diarrassouba, I. 2009. Survivable network design problems with high survivability requirements. Ph.D. thesis, Université Blaise Pascal - Clermond-Ferrand II, Auvergne, France.
Dolan, E. D., J. J. Moré. 2002. Benchmarking optimization software with performance profiles. Math. Programming Ser. A 91(2) 201-213. (Pubitemid 44744777)
Fischetti, M., D. Salvagnin, A. Zanette. 2010. A note on the selection of Benders' cuts. Math. Programming 124(1-2) 175-182.
Fortz, B. 2000. Design of Survivable Networks with Bounded Rings. Network Theory and Applications, Vol. 2. Kluwer Academic Publishers, Dordrecht, The Netherlands.
Fortz, B., M. Labbé. 2002. Polyhedral results for two-connected networks with bounded rings. Math. Programming 93(1) 27-54. (Pubitemid 44744752)
Fortz, B., M. Labbé. 2004. Two-connected networks with rings of bounded cardinality. Comput. Optim. Appl. 27(2) 123-148.
Fortz, B., M. Poss. 2009. An improved Benders decomposition applied to a multi-layer network design problem. Oper. Res. Lett. 37(5) 359-364.
Fortz, B., A. R. Mahjoub, S. T. McCormick, P. Pesneau. 2006. Twoedge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut. Math. Programming 105(1) 85-111. (Pubitemid 41705519)
Gouveia, L. 1996. Multicommodity flow models for spanning trees with hop constraints. Eur. J. Oper. Res. 95(1) 178-190. (Pubitemid 126391980)
Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2) 180-188. (Pubitemid 128669126)
Gouveia, L., T. L. Magnanti. 2003. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41(3) 159-173.
Gouveia, L., P. F. Patrício, A. F. Sousa. 2006. Telecommunications planning: Innovations in pricing, network design and management. Compact Models for Hop-Constrained Node Survivable Network Design. Springer, New York, 167-180.
Gouveia, L., P. F. Patrício, A. F. Sousa. 2008. Hop-contrained node survivable network design: An application to MPLS over WDM. Networks Spatial Econom. 8(1) 3-21.
Gouveia, L. E., P. F. Patrício, A. F. de Sousa, R. Valadas. 2003. MPLS over WDM network design with packet level QoS constraints based on ILP models. Proc. IEEE INFOCOM, Vol. 1. IEEE, Piscataway, NJ, 576-586.
Grötschel, M., C. L. Monma, M. Stoer. 1992. Facets for polyhedra arising in the design of communication networks with lowconnectivity constraints. SIAM J. Optim. 2(3) 274-504.
Hooker, J. N. 2000. Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley-Interscience, New York.
Huygens, D., A. R. Mahjoub. 2007. Integer programming formulations for the two 4-hop-constrained paths problem. Networks 49(2) 135-144. (Pubitemid 46931770)
Huygens, D., A. R. Mahjoub, P. Pesneau. 2004. Two edge-disjoint hop-constrained paths and polyhedra. SIAM J. Discrete Math. 18(2) 287-312. (Pubitemid 40672769)
Huygens, D., M. Labbé, A. R. Mahjoub, P. Pesneau. 2007. The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut. Networks 49(1) 116-133. (Pubitemid 46485352)
Itaí, A., Y. Perl, Y. Shiloach. 1982. The complexity of finding maximum disjoint paths with length constraints. Networks 12(3) 277-286. (Pubitemid 13491782)
Kerivin, H., A. R. Mahjoub. 2005. Design of survivable networks: A survey. Networks 46(1) 1-21. (Pubitemid 41092973)
Ljubic, I., P. Putz, J. J. Salazar. 2009. Exact approaches to the singlesource network loading problem. Technical Report 2009-05, University of Vienna, Vienna.
Magnanti, T. L., S. Raghavan. 2005. Strong formulations for network design problems with connectivity requirements. Networks 45(2) 61-79. (Pubitemid 40304384)
Nemhauser, G. L., L. A. Wolsey. 1988. Integer and Combinatorial Optimization. Wiley-Interscience, New York.
Orlowski, S., M. Pióro, A. Tomaszewski, R. Wessäly. 2010. SNDlib 1.0 - Survivable network design library. Networks 55(3) 276-286.
Pirkul, H., S. Soni. 2003. New formulations and solution procedures for the hop constrained network design problem. Eur. J. Oper. Res. 148(1) 126-140.
Raghavan, S. 1995. Strong formuations for network design problems with connectivity requirements. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge.
Stoer, M., ed. 1992. Design of Survivable Networks. Lecture Notes in Mathematics, Vol. 1531. Springer, Berlin.
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.