The problem of designing a cost-efficient network that survives the failure of one or more nodes or edges of the network is critical to modern telecommunications engineering. The method developed in this book is designed to solve such problems to optimality. In particular, a cutting plane approach is described, based on polyhedral combinatorics, that is ableto solve real-world problems of this type in short computation time. These results are of interest for practitioners in the area of communication network design. The book is addressed especially to the combinatorial optimization community, but also to those who want to learn polyhedral methods. In addition, interesting new research problemsare formulated.
Author(s): Mechthild Stoer (auth.)
Series: Lecture Notes in Mathematics 1531
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1992
Language: English
Pages: 204
City: Berlin; New York
Tags: Systems Theory, Control; Calculus of Variations and Optimal Control; Optimization; Math. Applications in Chemistry; Numerical and Computational Methods in Engineering; Communications Engineering, Networks
Motivation....Pages 5-6
Network survivability models using node types....Pages 7-18
Survivable network design under connectivity constraints — a survey....Pages 19-32
Decomposition....Pages 33-47
Basic inequalities....Pages 49-68
Lifting theorems....Pages 69-76
Partition inequalities....Pages 77-90
Node partition inequalities....Pages 91-99
Lifted r -cover inequalities....Pages 101-112
Comb inequalities....Pages 113-123
How to find valid inequalities....Pages 125-154
Implementation of the cutting plane algorithm....Pages 155-173
Computational results....Pages 175-194
