@misc{RaackKosterOrlowskietal., author = {Raack, Christian and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {Capacitated network design using general flow-cutset inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9576}, number = {07-14}, abstract = {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.}, language = {en} } @misc{OrlowskiPioroTomaszewskietal., author = {Orlowski, Sebastian and Pioro, Michal and Tomaszewski, Artur and Wess{\"a}ly, Roland}, title = {SNDlib 1.0--Survivable Network Design Library}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9582}, number = {07-15}, abstract = {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.}, language = {en} } @misc{OrlowskiKosterRaacketal., author = {Orlowski, Sebastian and Koster, Arie M.C.A. and Raack, Christian and Wess{\"a}ly, Roland}, title = {Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9412}, number = {06-47}, abstract = {This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.}, language = {en} } @misc{KosterOrlowskiRaacketal., author = {Koster, Arie M.C.A. and Orlowski, Sebastian and Raack, Christian and Bayer, Georg and Engel, Thomas}, title = {Single-layer Cuts for Multi-layer Network Design Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9641}, number = {07-21}, abstract = {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.}, language = {en} } @misc{IdzikowskiOrlowskiRaacketal., author = {Idzikowski, Filip and Orlowski, Sebastian and Raack, Christian and Woesner, Hagen and Wolisz, Adam}, title = {Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings}, organization = {Zuse Institute Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11692}, number = {10-07}, abstract = {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.}, language = {en} } @misc{HuelsermannJaegerKosteretal., author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {Availability and Cost Based Evaluation of Demand-wise Shared Protection}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9080}, number = {06-15}, abstract = {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.}, language = {en} } @misc{GruberKosterOrlowskietal., author = {Gruber, Claus G. and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {A new model and a computational study for Demand-wise Shared Protection}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8880}, number = {05-55}, abstract = {This report combines the contributions to INOC 2005 (Wess{\"a}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.}, language = {en} }