The design of survivable telecommunication networks

We address the problem of designing survivable data networks. These are a special class of capacitated minimum-cost survivable spanning networks. In the minimum-cost survivable network (MCSN) problem the goal is to decide where to place communication links to minimize cost subject to certain connectivity constraints. The connectivity constraint ensures that if there is a failure of any node or link, the network is still connected. This can be characterized as a network with two disjoint paths for every pair of nodes. Two paths are disjoint if they do not have any nodes or edges in common. It has been shown that the MCSN problem is NP-complete. The MCSN problem is formulated as an integer program. Different formulations are given. We develop a method for finding the lower bound for the uncapacitated problem, which is based on cutting planes. The heuristic is compared to the lower bound. The lower bound procedure is extended to find optimal solutions for small problems. A Lagrangean Relaxation method is derived for finding a lower bound for the capacitated MCSN. We develop heuristics to solve large-scale capacitated and uncapacitated survivable network design problems. The heuristics used are based on local search. We first find an initial feasible solution and continually make cost improving branch exchanges to find a locally optimal solution. Results show fast and accurate solutions for uncapacitated networks with 100 nodes and similar results for a restricted set of capacitated networks