An Integer Polytope Related to the Design of Survivable Communication Networks

The problem of designing communication networks that can survive the loss of any single link is studied. Such problems can be formulated as minimum cost 2-edge connected subgraph problems in a complete graph. The linear programming cutting plane approach has been used effectively for related problems in [Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, Anwendungsbezogene Optimierung and Steuerung, Report No. 188, 1989], where problem-specific cutting planes that define facets of the underlying integer polyhedra are used. This paper introduces a new class of valid inequalities for the polytope associated with the minimum cost 2-edge connected subgraph problem, and necessary and sufficient conditions for these inequalities to be facet-inducing for this polytope are given.