@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} } @inproceedings{OrlowskiKosterRaacketal.2007, 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}, series = {Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-06-47}, booktitle = {Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-06-47}, publisher = {International Network Optimization Conference}, address = {Spa, Belgium}, year = {2007}, language = {en} } @misc{OrlowskiWessaely, author = {Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {The Effect of Hop Limits on Optimal Cost in Survivable Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7980}, number = {04-23}, abstract = {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.}, 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{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} } @incollection{KosterOrlowskiRaacketal.2008, author = {Koster, Arie M.C.A. and Orlowski, Sebastian and Raack, Christian and Baier, Georg and Engel, Thomas}, title = {Single-layer Cuts for Multi-Layer Network Design Problems}, series = {Telecommunications Modeling Policy and Technology, also ZIB Report ZR-07-21}, booktitle = {Telecommunications Modeling Policy and Technology, also ZIB Report ZR-07-21}, publisher = {Springer}, address = {College Park, MD, U.S.A.}, pages = {1 -- 23}, year = {2008}, language = {en} } @misc{WessaelyWernerEckeletal., author = {Wess{\"a}ly, Roland and Werner, Axel and Eckel, Klaus and Seibel, Julia and Orlowski, Sebastian and Louchet, Hadrien and Patzak, Erwin and Bentz, Winfried}, title = {Sch{\"a}tze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14861}, abstract = {Das vom BMBF gef{\"o}rderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu k{\"o}nnen. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.}, language = {de} } @inproceedings{BentzEckelLouchetetal.2011, author = {Bentz, Winfried and Eckel, Klaus and Louchet, Hadrien and Orlowski, Sebastian and Patzak, Erwin and Seibel, Julia and Werner, Axel and Wess{\"a}ly, Roland}, title = {Sch{\"a}tze heben bei der Planung von FTTx-Netzen}, series = {Breitbandversorgung in Deutschland}, volume = {227}, booktitle = {Breitbandversorgung in Deutschland}, publisher = {VDE-Verlag}, year = {2011}, language = {en} } @inproceedings{IdzikowskiOrlowskiRaacketal.2010, author = {Idzikowski, Filip and Orlowski, Sebastian and Raack, Christian and Woesner, Hagen and Wolisz, Adam}, title = {Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios}, series = {Proceedings of the 14th conference on Optical network design and modeling}, booktitle = {Proceedings of the 14th conference on Optical network design and modeling}, publisher = {IEEE Press}, address = {Piscataway, NJ, USA}, pages = {42 -- 47}, year = {2010}, language = {en} } @phdthesis{Orlowski, author = {Orlowski, Sebastian}, title = {Optimal Design of Survivable Multi-layer Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11876}, abstract = {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.}, language = {en} }