Hierarchical Approach for Survivable Network Design
A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. This research concerns the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. In this presentation I will demonstrate a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization and optimization. The approach decomposes the SND problem into two sub-problems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. On average, this hierarchical method generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods) and is robust for a variety of problems with different size and connectivity characteristics.