An integer polyhedron related to the design of survivable communication networks.

Abstract

The linear programming cutting plane method has proven to be quite successful for solving certain "hard" combinatorial optimization problems, c.f. (1), (6), (12), (24), (26). A great deal of this success is due to the use of problem specific cutting planes which define facets of the underlying integer polyhedra. In this paper, we introduce a new class of valid inequalities for the polytope associated with the minimum cost 2-edge-connected subgraph problem, and give necessary and sufficient conditions for these inequalities to be facet inducing for this polytope. We believe it will be possible to use these inequalities efficiently in a cutting plane procedure for designing minimum cost survivable communication networks.