Topology-Constrained Network Design

[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]

Publisher :

Springer Cham

Pages :

187-208

Peer reviewed :

Editorial reviewed

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85152285377&doi=10.1007%2f978-3-030-64018-7_7&partnerID=40&md5=27adb3209ac27b9e014a0079cea49293

Commentary :

cited By 0
Scopus

Available on ORBi :

since 15 May 2024

Statistics

Number of views

7 (0 by ULiège)

Number of downloads

13 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

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