Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A branch-and-cut algorithm for two-level survivable network design problems
AU - Rodriguez-Martin, Inmaculada
AU - Salazar-Gonzalez, Juan-Jose
AU - Yaman, Hande
PY - 2016/3
Y1 - 2016/3
N2 - This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem. (C) 2015 Elsevier Ltd. All rights reserved.
AB - This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem. (C) 2015 Elsevier Ltd. All rights reserved.
KW - Network design
KW - Survivability
KW - Hierarchical networks
KW - Valid inequalities
KW - Branch-and-cut
KW - TELECOMMUNICATIONS NETWORKS
KW - LOCATION
KW - RINGS
KW - REQUIREMENTS
KW - SUBGRAPHS
KW - POLYHEDRA
U2 - 10.1016/j.cor.2015.09.008
DO - 10.1016/j.cor.2015.09.008
M3 - Journal article
VL - 67
SP - 102
EP - 112
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
ER -