A Cutting Plane Algorithm for Multicommodity Survivable Network Design Problems

We present a cutting plane algorithm for solving the following telecommunications network design problem: given point-to-point traffic demands in a network, specified survivability requirements and a discrete cost/capacity function for each link, find minimum cost capacity expansions satisfying the given demands. This algorithm is based on the polyhedral study described in [19]. In this paper we describe the underlying problem, the model and the main ingredients in our algorithm. This includes: initial formulation, feasibility test, separation for strong cutting planes and primal heuristics. Computational results for a set of real-world problems are reported. 1 Introduction The design of cost-e#cient telecommunications networks meeting requirements concerning tra#c, survivability etc. is a major challenge with great economic impact. In particular, it is important to establish networks that are robust with respect to accidents like cable cuts, electronic failures or power supply shut-d..