×

Survivability in hierarchical telecommunications networks. (English) Zbl 1241.90023

Summary: The survivable hierarchical telecommunications network design problem consists of locating concentrators, assigning user nodes to concentrators, and linking concentrators in a reliable backbone network. In this article, we study this problem when the backbone is 2-edge connected and when user nodes are linked to concentrators by a point-to-point access network. We formulate this problem as an integer linear program and present a facial study of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. We investigate the computational complexity of the corresponding separation problems. We propose some reduction operations to speed up the separation procedures. Finally, we devise a branch-and-cut algorithm based on these results and present the outcome of a computational study.

MSC:

90B18 Communication networks in operations research
90C05 Linear programming

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Balas, Set partitioning: A survey, SIAM Rev 18 pp 710– (1976) · Zbl 0347.90064 · doi:10.1137/1018115
[2] Barahona, On two-connected subgraph polytopes, Discrete Math 147 pp 19– (1995) · Zbl 0838.05085 · doi:10.1016/0012-365X(94)00255-H
[3] Bendali, A branch-and-cut algorithm for the k -edge connected subgraph problem, Networks 55 pp 13– (2010) · Zbl 1207.05192 · doi:10.1002/net.20310
[4] Chardaire, Upper and lower bounds for the two-level simple plant location problem, Ann of Oper Res 86 pp 117– (1999) · Zbl 0918.90095 · doi:10.1023/A:1018942415824
[5] Current, The hierarchical network design problem with transshipment facilities, Euro J Oper Res 52 pp 338– (1991) · Zbl 0738.90080 · doi:10.1016/0377-2217(91)90309-J
[6] Dahl, On the k edge-disjoint 2-hop-constrained paths polytope, Oper Res Lett 34 pp 577– (2006) · Zbl 1152.90661 · doi:10.1016/j.orl.2005.09.001
[7] Fonlupt, Critical extreme points of the 2-edge connected spanning subraph problem, Math Program B 105 pp 289– (2006) · Zbl 1085.90008 · doi:10.1007/s10107-005-0654-8
[8] Fortz, Polyhedral results for two-connected networks with bounded rings, Math Program 93 pp 27– (2002) · Zbl 1007.90011 · doi:10.1007/s10107-002-0299-9
[9] Fortz, Solving the two-connected network with bounded meshes problem, Oper Res 58 pp 866– (2000) · Zbl 1106.90312 · doi:10.1287/opre.48.6.866.12390
[10] Fortz, Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut, Math Program 105 pp 85– (2006) · Zbl 1085.90009 · doi:10.1007/s10107-005-0576-5
[11] Gavish, Topological design of centralized computer networks: Formulations and algorithms, Networks 12 pp 355– (1982) · Zbl 0493.94021 · doi:10.1002/net.3230120402
[12] Gourdin, Facility location: Applications and theory, Chapter 9 pp 275– (2001)
[13] Goldberg, A new approach to the maximum flow problem, J Assoc Comput Mach 35 pp 931– (1988) · Zbl 0661.90031 · doi:10.1145/48014.61051
[14] Grötschel, Handbooks in operations research and management Science 7 pp 617– (1995)
[15] Hao, A faster algorithm for finding the minimum cut in a directed graph, J Algorithms 17 pp 424– (1994) · Zbl 0819.68087 · doi:10.1006/jagm.1994.1043
[16] Huygens, Two edge-disjoint hop-constrained paths and polyhedra, SIAM J Disc Math 18 pp 287– (2004) · Zbl 1077.90010 · doi:10.1137/S0895480102419445
[17] Kerivin, Design of survivable networks: A review, Networks 46 pp 1– (2005) · Zbl 1072.90003 · doi:10.1002/net.20072
[18] Kerivin, On survivable network polyhedra, Disc Math 290 pp 183– (2005) · Zbl 1079.90022 · doi:10.1016/j.disc.2004.08.017
[19] Kerivin, The sharpest-cut, Chapter 9 pp 121– (2004) · doi:10.1137/1.9780898718805.ch9
[20] Klincewicz, Hub location in backbone/tributary network design: A review, Location Science 6 pp 307– (1998) · doi:10.1016/S0966-8349(98)00042-4
[21] Labbé, The ring star problem: Polyhedral analysis and exact algorithm, Networks 43 pp 177– (2004) · Zbl 1053.90021 · doi:10.1002/net.10114
[22] Labbé, Solving the hub location problem in a star-star network, Networks 51 pp 19– (2008) · Zbl 1146.90035 · doi:10.1002/net.20193
[23] Labbé, A branch and cut algorithm for hub location problems with single assignment, Math Program 102 pp 371– (2005) · Zbl 1079.90080 · doi:10.1007/s10107-004-0531-x
[24] Lee, A hub location problem in designing digital data service networks: Lagrangian relaxation approach, Location Science 4 pp 185– (1996) · Zbl 0929.90050 · doi:10.1016/S0966-8349(96)00009-5
[25] Mahjoub, Two-edge connected spanning subgraphs and polyhedra, Math Program 64 pp 199– (1994) · Zbl 0820.90117 · doi:10.1007/BF01582572
[26] Mahjoub, On perfectly two-edge connected graphs, Disc Math 170 pp 153– (1997) · Zbl 0882.90125 · doi:10.1016/S0012-365X(96)00004-0
[27] Nemhauser, Integer and combinatorial optimization (1998)
[28] Pirkul, Locating concentrators in centralized computer networks, Ann Oper Res 36 pp 247– (1992) · Zbl 0825.90376 · doi:10.1007/BF02094332
[29] Reinelt, TSPLIB-a traveling salesman problem library, ORSA J Comp 3 pp 376– (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[30] Stoer, Lecture notes in mathematics 1531 (1992)
[31] Vandenbussche, The 2-edge-connected subgraph polyhedron, J Comb Opt 9 pp 357– (2005) · Zbl 1093.90051 · doi:10.1007/s10878-005-1777-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.