Design of survivable communication networks with high-connectivity constraints

Designing highly survivable interoffice telecommunication networks is considered. The problem is formulated as a minimum-cost network design problem with three node connectivity constraints. Three valid and facet-defining inequalities for the convex hull of the solutions are presented. A branch and cut algorithm is proposed based on the inequalities to obtain the optimal solution. With the lower bound by the cutting plane algorithm, a delete-link heuristic is proposed to obtain a good upper bound in the branch and bound procedure. The effectiveness of the branch and cut algorithm is demonstrated with computational results for a variety of problem sets: different lower bounds, two types of link costs and large number of links. The cutting plane procedure based on the three inequalities provides excellent lower bounds to the optimal solutions.