Design of Survivable Networks with Bounded Rings

This book studies the problem of designing, at minimal cost, a two-connected network such that each edge belongs to a cycle of bounded length. This problem arises in the long-term planning of telecommunications networks. The book provides an in-depth study of the underlying polyhedron, proposing several classes of facet-defining inequalities that are used in a branch-and-cut algorithm. Several heuristics are also proposed in order to solve real-world instances of the problem, and extensive numerical results are reported. The polyhedral analysis is done in the best mathematical programming tradition. Results obtained here demonstrate how to use polyhedral theory for practical network design problems, and are therefore of interest for mathematical programming practitioners as an application of classical theoretical concepts. Moreover, telecommunications specialists can find practical solutions to real-world problems, as several heuristics are proposed that can be easily extended to related problems. Audience: Operations research and mathematical programming researchers, and telecommunications specialists.