Large Scale Linear Programs and Heuristics for the Design of Survivable Telecommunication Networks

摘要

We consider the problem of providing a minimum cost multi-service network subject to one link failure scenarios. We assume our network is fully meshed and demand is satisfied by using direct or two hop-paths. We provide a large scale linear programming formulation and propose and test two effective heuristics.