http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
Design of survivable networks with bounded rings
1 online resource (xix, 203 pages) : illustrations.
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.
1. Introduction -- 2. Survivable Network Design: A Survey. 2.1. Notation and definitions. 2.2. Low-connectivity constrained network design problems. 2.3. Structural properties and particular cases. 2.4. Heuristics. 2.5. Polyhedral studies and exact algorithms -- 3. Two-connected Networks with Bounded Rings: The Model. 3.1. Motivation. 3.2. Mathematical formulations -- 4. Polyhedral Study. 4.1. Associated polytopes and trivial inequalities. 4.2. Cut constraints. 4.3. Node-cut and subset inequalities. 4.4. Ring-cut inequalities. 4.5. Ring-cover inequalities. 4.6. Metric inequalities. 4.7. Node-partition inequalities. 4.8. Weighted partition inequalities -- 5. The Special Case of Rings with Bounded Cardinality.
Includes bibliographical references (pages 193-200) and index.
Network theory and applications ; volume 2