Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints

Authors:
  • MGMartin Grötschel
    Martin Grötschel
  • CMClyde L. Monma
    Clyde L. Monma
  • MSMechthild Stoer
    Mechthild Stoer

Abstract
This paper addresses the important practical problem of designing survivable fiber optic communication networks. This problem can be formulated as a minimum-cost network design problem with certain low-connectivity constraints. Previous work presented structural properties of optimal solutions and heuristic methods for obtaining “near-optimal” network designs. Some facet-inducing inequalities for the convex hull of the solutions to this problem are given. A companion paper describes computational results on real-world telephone network design problems with a cutting plane method based on this work. These computational results are summarized in the last section of this paper.

This publication has 10 references indexed in Scilit: