Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
Authors:
- Martin GrötschelMGMartin Grötschel
- Clyde L. MonmaCMClyde L. Monma
- Mechthild StoerMSMechthild Stoer
- 1 August 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 2 (3) , 474-504
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.Keywords
This publication has 10 references indexed in Scilit:
- Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity ConstraintsOperations Research, 1992
- Design of Survivable Networks1992
- Implementing the Simplex Method: The Initial Basis1991
- Integer Polyhedra Arising from Certain Network Design Problems with Connectivity ConstraintsSIAM Journal on Discrete Mathematics, 1990
- Minimum-weight two-connected spanning networksMathematical Programming, 1990
- Computer-aided design procedures for survivable fiber optic networksIEEE Journal on Selected Areas in Communications, 1989
- Methods for Designing Communications Networks with Certain Two-Connected Survivability ConstraintsOperations Research, 1989
- The traveling salesman problem on a graph and some related integer polyhedraMathematical Programming, 1985
- Edmonds polytopes and a hierarchy of combinatorial problemsDiscrete Mathematics, 1973
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965