1300 187 187
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.
'In summary, this is a good book to see how integer programming is used in real-life applications.' Mathematical Reviews, 2001
| List of Figures | |
| List of Tables | |
| List of Algorithms | |
| Acknowledgments | |
| Introduction | p. 1 |
| Survivable Network Design: A Survey | p. 5 |
| Notation and definitions | p. 6 |
| Low-connectivity constrained network design problems | p. 8 |
| Structural properties and particular cases | p. 12 |
| Heuristics | p. 17 |
| Polyhedral studies and exact algorithms | p. 21 |
| Two-connected Networks with Bounded Rings: The Model | p. 25 |
| Motivation | p. 26 |
| Mathematical formulations | p. 27 |
| Polyhedral Study | p. 35 |
| Associated polytopes and trivial inequalities | p. 36 |
| Cut constraints | p. 40 |
| Node-cut and subset inequalities | p. 46 |
| Ring-cut inequalities | p. 51 |
| Ring-cover inequalities | p. 58 |
| Metric inequalities | p. 59 |
| Node-partition inequalities | p. 63 |
| Weighted partition inequalities | p. 65 |
| The Special Case of Rings with Bounded Cardinality | p. 69 |
| A lower bound on the number of edges | p. 70 |
| Complexity | p. 77 |
| Cyclomatic inequalities | p. 81 |
| Triangular rings | p. 88 |
| A Branch-and-Cut Algorithm | p. 91 |
| Checking feasibility | p. 92 |
| Separation of cut constraints | p. 95 |
| Separation of metric inequalities | p. 95 |
| Separation of subset inequalities | p. 100 |
| Separation of ring-cut inequalities | p. 102 |
| Separation of node-partition inequalities | p. 106 |
| Separation of weighted partition inequalities | p. 106 |
| Separation of cyclomatic inequalities | p. 107 |
| Implementation of the Branch-and-Cut algorithm | p. 107 |
| Summary of polyhedral results | p. 113 |
| Heuristics | p. 115 |
| Ear-inserting method | p. 116 |
| Cutting cycles in two equal parts | p. 116 |
| Path-following method | p. 117 |
| Stingy method | p. 119 |
| Tabu Search | p. 119 |
| Computational Results | p. 125 |
| Branch-and-Cut for Euclidean edge lengths | p. 127 |
| Branch-and-Cut for unit edge lengths | p. 133 |
| Heuristics for Euclidean edge lengths | p. 138 |
| Heuristics for unit edge lengths | p. 143 |
| Conclusion | p. 147 |
| App. A - Detailed Computational Results | p. 149 |
| References | p. 193 |
| Index | p. 201 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
ISBN: 9780792364146
ISBN-10: 0792364147
Series: Network Theory and Applications
Audience:
Professional
Format:
Hardcover
Language:
English
Number Of Pages: 224
Published: December 2009
Dimensions (cm): 23.4 x 15.6
x 1.4
Weight (kg): 1.1
9am - 4pm AEST, Monday - Friday
