Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing Decisions
Please always quote using this URN: urn:nbn:de:0297-zib-7316
- We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results.
Author: | Sebastian Orlowski, Roland Wessäly |
---|---|
Document Type: | ZIB-Report |
Tag: | branch-and-cut algorithm; hardware configuration; link and path restoration; routing; survivable network design |
MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Mxx Computer system organization / 68M10 Network design and communication [See also 68R10, 90B18] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
Date of first Publication: | 2003/04/16 |
Series (Serial Number): | ZIB-Report (03-09) |
ZIB-Reportnumber: | 03-09 |
Published in: | Appeared in: Journal of Network and Systems Management 13 (2005) 99-118 |