TY - GEN A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Availability and Cost Based Evaluation of Demand-wise Shared Protection N2 - In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection. T3 - ZIB-Report - 06-15 KW - demand-wise shared protection KW - network availability KW - network optimization Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9080 ER - TY - GEN A1 - Gruber, Claus G. A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - A new model and a computational study for Demand-wise Shared Protection N2 - This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection. T3 - ZIB-Report - 05-55 KW - demand-wise shared protection KW - resilience KW - network design KW - integer linear programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8880 ER - TY - JOUR A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - On cut-based inequalities for capacitated network design polyhedra JF - Networks Y1 - 2011 UR - http://onlinelibrary.wiley.com/doi/10.1002/net.20395/abstract VL - 57 IS - 2 SP - 141 EP - 156 ER - TY - GEN A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings N2 - We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure. T3 - ZIB-Report - 10-07 KW - network design KW - energy efficiency KW - power consumption KW - multi-layer KW - multi-hour KW - multi-period Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11692 SN - 1438-0064 ER - TY - CHAP A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios T2 - Proceedings of the 14th conference on Optical network design and modeling Y1 - 2010 UR - http://portal.acm.org/citation.cfm?id=1834075.1834085 SP - 42 EP - 47 PB - IEEE Press CY - Piscataway, NJ, USA ER - TY - JOUR A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Dynamic routing at different layers in IP-over-WDM networks – Maximizing energy savings JF - Optical Switching and Networking, Special Issue on Green Communications Y1 - 2011 UR - http://opus.kobv.de/zib/volltexte/2010/1230/ ER - 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 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Capacitated network design using general flow-cutset inequalities N2 - This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities. T3 - ZIB-Report - 07-14 KW - general flow-cutset inequalities KW - capacitated network design KW - mixed integer rounding KW - SNDlib Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9576 ER - TY - THES A1 - Orlowski, Sebastian T1 - Optimal Design of Survivable Multi-layer Telecommunication Networks N2 - Telecommunication transport networks consist of a stack of technologically different subnetworks, so-called layers, which are strongly interdependent. For example, one layer may correspond to an Internet (IP) backbone network whose links are realized by lightpath connections in an underlying optical fiber layer. To ensure that the network can fulfill its task of routing all communication requests, the inter-layer dependencies have to be taken into account already in the planning phase of the network. This is particularly important with survivability constraints, where connections in one layer have to be protected against cable cuts or equipment failures in another layer. The traditional sequential planning approach where one layer is optimized after the other cannot properly take care of the inter-layer dependencies; this can only be achieved with an integrated planning of several network layers at the same time. This thesis provides mathematical models and algorithmic techniques for the integrated optimization of two network layers with survivability constraints. We describe a multi-layer network design problem which occurs in various technologies, and model it mathematically using mixed-integer programming (MIP) formulations. The presented models cover many important practical side constraints from different technological contexts. In contrast to previous models from the literature, they can be used to design large two-layer networks with survivability requirements. We discuss modeling alternatives for various aspects of a multi-layer network and compare different routing formulations under multi-layer survivability constraints. We solve our models using a branch-and-cut-and-price approach with various problemspecific enhancements. This includes a presolving technique based on linear programming to reduce the problem size, combinatorial and sub-MIP-based primal heuristics to compute feasible network configurations, cutting planes which take the multi-layer survivability constraints into account to improve the lower bound on the optimal network cost, and column generation to generate flow variables dynamically during the algorithm. We develop techniques to speed up computations in a Benders decomposition approach and compare this approach to the standard formulation with a single MIP. We use the developed techniques to design large survivable two-layer networks by means of linear and integer programming methods. On realistic test instances with up to 67 network nodes and survivability constraints, we investigate the algorithmic impact of our techniques and show how to use them to compute good network configurations with quality guarantees. Most of the smaller test instances with up to 17 nodes can be solved to near-optimality. Moreover, we can compute feasible solutions and dual bounds even for large networks with survivability constraints, which has not been possible before. KW - Telekommunikationsnetze KW - Multi-layer-Netzen Ausfallsicherheit KW - gemischt-ganzzahlige Optimierung KW - Branch-and-cut-and-price KW - telecommunication networks KW - survivable multi-layer network design KW - mixed-integer programming KW - branch-and-cut-and-price Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11876 ER - TY - CHAP A1 - Orlowski, Sebastian A1 - Koster, Arie M.C.A. A1 - Raack, Christian A1 - Wessäly, Roland T1 - Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics T2 - Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-06-47 Y1 - 2007 UR - http://www.zib.de/Publications/abstracts/ZR-06-47 PB - International Network Optimization Conference CY - Spa, Belgium ER - TY - CHAP A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Capacitated network design using general flow-cutset inequalities T2 - Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-07-14 Y1 - 2007 UR - http://www.zib.de/Publications/abstracts/ZR-07-14 PB - International Network Optimization Conference CY - Spa, Belgium ER - TY - CHAP A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Baier, Georg A1 - Engel, Thomas T1 - Single-layer Cuts for Multi-Layer Network Design Problems T2 - Telecommunications Modeling Policy and Technology, also ZIB Report ZR-07-21 Y1 - 2008 UR - http://dx.doi.org/10.1007/978-0-387-77780-1_1 SP - 1 EP - 23 PB - Springer CY - College Park, MD, U.S.A. ER - TY - CHAP A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Baier, Georg A1 - Engel, Thomas A1 - Belotti, Pietro T1 - Branch-and-cut techniques for solving realistic two-layer network design problems T2 - Graphs and Algorithms in Communication Networks Y1 - 2009 UR - http://www.springerlink.com/content/g3rt54x5w4110240 SP - 95 EP - 118 PB - Springer Berlin Heidelberg ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Bayer, Georg A1 - Engel, Thomas T1 - Single-layer Cuts for Multi-layer Network Design Problems N2 - We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps. T3 - ZIB-Report - 07-21 KW - telecommunication network KW - multi-layer network design KW - mixed-integer programming KW - cutting planes Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9641 SN - 1438-0064 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Pioro, Michal A1 - Tomaszewski, Artur A1 - Wessäly, Roland T1 - SNDlib 1.0--Survivable Network Design Library N2 - We provide information on the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design that can be accessed at http://sndlib.zib.de. In version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network planning problem instances. In this paper, we provide a mathematical model for each planning problem considered in the library and describe the data concepts of the SNDlib. Furthermore, we provide statistical information and details about the origin of the data sets. T3 - ZIB-Report - 07-15 KW - telecommunication network design KW - data library KW - optimization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9582 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Werner, Axel A1 - Wessäly, Roland T1 - Estimating trenching costs in FTTx network planning N2 - In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ". T3 - ZIB-Report - 11-49 KW - Optical access networks KW - Optimization KW - Steiner trees Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14884 SN - 1438-0064 ER - TY - CHAP A1 - Bentz, Winfried A1 - Eckel, Klaus A1 - Louchet, Hadrien A1 - Orlowski, Sebastian A1 - Patzak, Erwin A1 - Seibel, Julia A1 - Werner, Axel A1 - Wessäly, Roland T1 - Schätze heben bei der Planung von FTTx-Netzen T2 - Breitbandversorgung in Deutschland Y1 - 2011 VL - 227 PB - VDE-Verlag ER - TY - CHAP A1 - Orlowski, Sebastian A1 - Werner, Axel A1 - Wessäly, Roland ED - Klatte, Diethart ED - Lüthi, Hans-Jakob ED - Schmedders, Karl T1 - Estimating trenching costs in FTTx network planning T2 - Operations Research Proceedings 2011 Y1 - 2012 SP - 89 EP - 94 PB - Springer Verlag ER - TY - CHAP A1 - Bentz, Winfried A1 - Martens, Maren A1 - Orlowski, Sebastian A1 - Werner, Axel A1 - Wessäly, Roland T1 - FTTx-PLAN T2 - Breitbandversorgung in Deutschland Y1 - 2010 VL - 220 PB - VDE-Verlag 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 -