TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing Decisions N2 - 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. T3 - ZIB-Report - 03-09 KW - survivable network design KW - link and path restoration KW - hardware configuration KW - branch-and-cut algorithm KW - routing Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7316 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - The Effect of Hop Limits on Optimal Cost in Survivable Network Design N2 - We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible. T3 - ZIB-Report - 04-23 KW - survivable network design KW - hop limits KW - routing KW - restoration KW - branch-and-cut algorithm KW - mixed-integer programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7980 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Pióro, Michal T1 - On the complexity of column generation in survivable network design with path-based survivability mechanisms N2 - This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures. T3 - ZIB-Report - 08-51 KW - Netzplanung KW - Dimensionierung KW - Spaltengenerierung KW - Mehrfachausfälle KW - survivable network design KW - routing KW - column generation KW - pricing KW - complexity Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11058 SN - 1438-0064 ER -