@misc{OrlowskiWessaely2004, 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}, year = {2004}, 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{RaackKosterOrlowskietal.2007, 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}, year = {2007}, 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} } @phdthesis{Orlowski2009, author = {Orlowski, Sebastian}, title = {Optimal Design of Survivable Multi-layer Telecommunication Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11876}, year = {2009}, 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} } @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}, 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} } @inproceedings{RaackKosterOrlowskietal.2007, 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}, booktitle = {Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-07-14}, publisher = {International Network Optimization Conference}, address = {Spa, Belgium}, year = {2007}, 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}, 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} } @incollection{KosterOrlowskiRaacketal.2009, author = {Koster, Arie M.C.A. and Orlowski, Sebastian and Raack, Christian and Baier, Georg and Engel, Thomas and Belotti, Pietro}, title = {Branch-and-cut techniques for solving realistic two-layer network design problems}, booktitle = {Graphs and Algorithms in Communication Networks}, publisher = {Springer Berlin Heidelberg}, pages = {95 -- 118}, year = {2009}, language = {en} } @misc{KosterOrlowskiRaacketal.2007, 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}, year = {2007}, 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{OrlowskiPioroTomaszewskietal.2007, 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}, year = {2007}, 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{OrlowskiWernerWessaely2012, author = {Orlowski, Sebastian and Werner, Axel and Wess{\"a}ly, Roland}, title = {Estimating trenching costs in FTTx network planning}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_15}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14884}, year = {2012}, abstract = {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".}, language = {en} } @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}, volume = {227}, booktitle = {Breitbandversorgung in Deutschland}, publisher = {VDE-Verlag}, year = {2011}, language = {en} } @inproceedings{OrlowskiWernerWessaely2012, author = {Orlowski, Sebastian and Werner, Axel and Wess{\"a}ly, Roland}, title = {Estimating trenching costs in FTTx network planning}, booktitle = {Operations Research Proceedings 2011}, editor = {Klatte, Diethart and L{\"u}thi, Hans-Jakob and Schmedders, Karl}, publisher = {Springer Verlag}, pages = {89 -- 94}, year = {2012}, language = {en} } @inproceedings{BentzMartensOrlowskietal.2010, author = {Bentz, Winfried and Martens, Maren and Orlowski, Sebastian and Werner, Axel and Wess{\"a}ly, Roland}, title = {FTTx-PLAN}, volume = {220}, booktitle = {Breitbandversorgung in Deutschland}, publisher = {VDE-Verlag}, year = {2010}, language = {en} } @misc{OrlowskiPioro2008, author = {Orlowski, Sebastian and Pi{\´o}ro, Michal}, title = {On the complexity of column generation in survivable network design with path-based survivability mechanisms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11058}, number = {08-51}, year = {2008}, abstract = {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.}, language = {en} } @misc{Orlowski2003, type = {Master Thesis}, author = {Orlowski, Sebastian}, title = {Local and global restoration of node and link failures in telecommunication networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10008}, school = {Zuse Institute Berlin (ZIB)}, year = {2003}, abstract = {This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration,Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using diffeent restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost ifference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time. This diploma thesis deals with the restoration problem in telecommunication networks. The goal is to find a cost minimal capacity capacity assignment on the edges and nodes of a network such that given demands can be satisfied even in case of the failure of an edge or node in the network. Moreover, restrictions on the routing paths (like length restrictions) and hardware constraints have to be satisfied. A Mixed Integer Programming model is presented which takes into account restoration requirements as well as hardware constraints and which abstracts from a particular restoration protocol and failure situation. This abstraction provides new insight into the structure of the network restoration problem and shows that from a mathematical point of view, the commonly used restoration techniques Link Restoration, Path Restoration and Reservation are not as different as they seem to be from a practical point of view. In addition, our model allows (but is not limited to) optimizing working capacity, intended for normal use, and spare capacity, intended for rerouting purposes in case of a failure, in one step. Furthermore, our formulation of capacity cost allows taking into account the effects of discrete, non-linear cost structures which are common in practice. Up to our knowledge, no publication in the existing literature covers all these aspects, let alone in one model, although they are of major practical interest. The model has been implemented in a Branch and Cut framework. The theoretical background of the algorithmic procedure is presented in detail, including computational complexity investigations on the pricing problem. The abstraction from a particular restoration protocol turns out to be useful both from a theoretical and computational point of view. In fact, our investigations suggest a distinction into Local Restoration and Global Restoration rather than into Link Restoration, Path Restoration, Reservation and mixtures of these concepts. In addition to the theoretical aspects of the algorithmic procedure, some implementational details are briefly discussed. Our implementation has been tested on 14 real world instances, which is described in detail. One part of the computational results consists of a comparison of optimal network cost values using different restoration mechanisms, applied to securing either all single node failures, all single edge failures or both. In addition, the effects of a discrete cost structure are investigated, which has rarely been considered yet in literature. Furthermore, the cost difference between joint and successive working and spare capacity optimization is investigated. In the second part of the computational results, several heuristics for the network restoration problem are compared with respect to both solution quality and time.}, language = {en} } @misc{WessaelyWernerEckeletal.2012, 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}, year = {2012}, 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} }