A bootstrap heuristic for designing minimum cost survivable networks

This paper provides a systematic approach based on heuristics for designing Minimum Cost Survivable Networks (MCSN). The Design System has two components; a heuristic for obtaining survivable network topologies, and a set of heuristics for improving the cost of the initial networks. Each cost reducing heuristic is exercised in turn to improve the network progressively. The feasibility (i.e. survivability) heuristic is based on bootstrapping a lower bounding procedure to obtain good feasible solutions. This lower bounding method is also extended to obtain the optimal solution for small networks. The Design System proposed in this paper can solve 200 node network problems within 4 min on a Sun SPARCstation 2, and can get to within 4% of the lower bound.