[en] This chapter studies models and techniques for long-term planning of networks for which clients demands are not known in advance. It this case, the objective is to build a network at minimum cost, considering only the fixed cost associated with opening a link. Capacity and routing costs are therefore ignored. Nevertheless, the network is subject to topological constraints to ensure its connectivity and survivability. We cover the design of connected networks (and in particular the minimum spanning tree problem), followed by the design of networks requiring a higher level of survivability in terms of number of available node-disjoints paths, to allow re-routing in case of failures. To avoid delays in the networks, we also consider models where the length of paths is bounded, by introducing hop constraints or covering of the links by cycles of bounded lengths.
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
Language :
English
Title :
Topology-Constrained Network Design
Publication date :
2021
Main work title :
Network design with applications to transportation and logistics
Author, co-author :
Crainic, Teodor Gabriel; UQAM - Université du Québec à Montréal [CA]
Gendreau, Michel; Polytechnique Montréal
Gendron, Bernard; UdeM - Université de Montréal [CA]
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
Balakrishnan, A., & Altinkemer, K. (1992). Using a hop-constrained model to generate alternative communication network design. ORSA Journal on Computing, 4, 192–205
Barahona, F. (1992). Separating from the dominant of the spanning tree polytope. Operations Research Letters, 12, 201–203
Bendali, F., Diarrassouba, I., Mahjoub, A., & Mailfert, J. (2010). The edge-disjoint 3-hop-constrained paths polytope. Discrete Optimization, 7(4), 222–233
Bley, A. (2003). On the complexity of vertex-disjoint length-restricted path problems. Computational Complexity, 12(3–4), 131–149
Bley, A., & Neto, J. (2010). Approximability of 3- and 4-hop bounded disjoint paths problems. In Proceedings of IPCO 2010, Lausanne. Lecture notes in computer science (vol. 6080, pp 205–218). Berlin: Springer
Botton, Q., Fortz, B., & Gouveia, L. (2015). On the hop-constrained survivable network design problem with reliable edges. Computers & Operations Research, 64, 159–167
Botton, Q., Fortz, B., & Gouveia, L. (2018). The 2 edge-disjoint 3-paths polyhedron. Annals of Telecommunications, 73(1), 29–36
Botton, Q., Fortz, B., Gouveia, L., & Poss, M. (2013). Benders decomposition for the hop-constrained survivable network design problem. INFORMS Journal on Computing, 25(1), 13–26
Carroll, P., Fortz, B., Labbé, M., & McGarraghy, S. (2013). A branch-and-cut algorithm for the ring spur assignment problem. Networks, 61(2), 89–103
Cornuéjols, G., Fonlupt, F., & Naddef, D. (1985). The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming, 33, 1–27
Cunningham, W. (1985). Optimal attack and reinforcement of a network. Journal of ACM, 32, 549–561
Dahl, G. (1999). Notes on polyhedra associated with hop-constrained walk polytopes. Operations Research Letters, 25, 97–100
Dahl, G., & Johannessen, B. (2004). The 2-path network problem. Networks, 43, 190–199
Dahl, G., Foldnes, N., & Gouveia, L. (2004). A note on hop-constrained walk polytopes. Operations Research Letters, 32(4), 345–349
De Boeck, J., & Fortz, B. (2018). Extended formulation for hop constrained distribution network configuration problems. European Journal of Operational Research, 265(2), 488–502
Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1(1), 127–136
Eswaran, K., & Tarjan, R. (1976). Augmentation problems. SIAM Journal on Computing, 5, 653–665
Fischetti, M., Leitner, M., Ljubic, I., Luipersbeck, M., Monaci, M., Resch, M., et al. (2017). Thinning out steiner trees: a node-based model for uniform edge costs. Mathematical Programming Computation, 9(2), 203–229
Fortz, B. (2000). Design of survivable networks with bounded rings, network theory and applications (vol 2). Dordrecht: Kluwer Academic Publishers
Fortz, B., & Labbé, M. (2002). Polyhedral results for two-connected networks with bounded rings. Mathematical Programming, 93(1), 27–54
Fortz, B., & Labbé, M. (2004). Two-connected networks with rings of bounded cardinality. Computational Optimization and Applications, 27(2), 123–148
Fortz, B., Labbé, M., & Maffioli, F. (2000). Solving the two-connected network with bounded meshes problem. Operations Research, 48(6), 866–877
Fortz, B., Mahjoub, A., Mc Cormick, S., & Pesneau, P. (2006). Two-edge connected subgraphs with bounded rings: polyhedral results and branch-and-cut. Mathematical Programming, 105, 85–111
Goldschmidt, O., Laugier, A., & Olinick, E. V. (2003). SONET/SDH ring assignment with capacity constraints. Discrete Applied Mathematics, 129, 99–128
Gouveia, L. (1998). Using variable redefinition for computing lower bounds for minimum spanning and steiner trees with hop constraints. INFORMS Journal on Computing, 10, 180–188
Gouveia, L., Joyce-Moniz, M., & Leitner, M. (2018). Branch-and-cut methods for the network design problem with vulnerability constraints. Computers & Operations Research, 91, 190–208
Gouveia, L., & Leitner, M. (2017). Design of survivable networks with vulnerability constraints. European Journal of Operational Research, 258(1), 89–103
Gouveia, L., Leitner, M., & Ruthmair, M. (2019). Layered graph approaches for combinatorial optimization problems. Computers & Operations Research, 102, 22–38
Gouveia, L., & Magnanti, T. L. (2003). Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks, 41(3), 159–173
Gouveia, L., Patrício, P., & Sousa, A. (2006). Compact models for hop-constrained node survivable network design. In Telecommunications planning: Innovations in pricing. Network design and management (pp. 167–180). New York: Springer
Gouveia, L., Patrício, P., & Sousa, A. (2008). Hop-contrained node survivable network design: An application to MPLS over WDM. Networks and Spatial Economics, 8(1), 3–21
Gouveia, L. E., Patrício, P., de Sousa, A., & Valadas, R. (2003). MPLS over WDM network design with packet level QoS constraints based on ILP Models. In Proceedings of IEEE INFOCOM (pp. 576–586)
Grötschel, M., & Monma, C. (1990). Integer polyhedra arising from certain design problems with connectivity constraints. SIAM Journal on Discrete Mathematics, 3, 502–523
Grötschel, M., Monma, C., & Stoer, M. (1995a). Design of survivable networks. Handbooks in OR/MS, vol 7 on Network models (chap 10, pp. 617–672). Amsterdam: North-Holland
Grötschel, M., Monma, C., & Stoer, M. (1995b). Polyhedral and computational investigations for designing communication networks with high survivability requirements. Operations Research, 43(6), 1012–1024
Huygens, D., Labbé, M., Mahjoub, A. R., & Pesneau, P. (2007). The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut. Networks, 49(1), 116–133
Huygens, D., & Mahjoub, A. R. (2007). Integer programming formulations for the two 4-hop-constrained paths problem. Networks, 49(2), 135–144
Huygens, D., Mahjoub, A, & Pesneau, P. (2004). Two edge-disjoint hop-constrained paths and polyhedra. SIAM Journal on Discrete Mathematics, 18(2), 287–312
Itaí, A., Perl, Y., & Shiloach, Y. (1982). The complexity of finding maximum disjoint paths with length constraints. Networks, 2, 277–286
Kerivin, H., & Mahjoub, A. R. (2005). Design of survivable networks: A survey. Networks, 46(1), 1–21
Kruskal, J. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7, 48–50
Lawler, E. (1976). Combinatorial optimization: Networks and matroids. New-York: Holt, Rinehart and Wilson
Magnanti, T. L., & Raghavan, S. (2005). Strong formulations for network design problems with connectivity requirements. Networks, 45(2), 61–79
Magnanti, T. L., & Wolsey, L. A. (1995). Optimal trees. Handbooks in Operations Research and Management Science, 7, 503–615
Mahjoub, A. (1994). Two-edge connected spanning subgraphs and polyhedra. Mathematical Programming, 64, 199–208
Martin, R. K. (1991). Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters, 10(3), 119–128
Menger, K. (1927). Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10, 96–115
Monma, C., & Shallcross, D. (1989). Methods for designing communications networks with certain two-connected survivability constraints. Operations Research, 37(4), 531–541
Pirkul, H., & Soni, S. (2003). New formulations and solution procedures for the hop constrained network design problem. European Journal of Operational Research, 148, 126–140
Stoer, M. (1992). Design of survivable networks. Lecture Notes in Mathematics (vol. 1531). Berlin: Springer
Winter, P. (1987). Steiner problems in networks: A survey. Networks, 17, 129–167
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.
