TY - GEN A1 - Bley, Andreas A1 - Koster, Arie M.C.A. A1 - Kröller, Alexander A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Kosten- und Qualitätsoptimierung in Kommunikationsnetzen N2 - Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuführen. Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der mathematischen Optimierung für die Praxis. T3 - ZIB-Report - 03-31 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7537 ER - TY - GEN A1 - Bley, Andreas A1 - Zymolka, Adrian T1 - Planung kostenoptimaler Informations- und Kommunikations-Infrastrukturen N2 - Beim Entwurf und Ausbau von Informations- und Kommunikationsnetzwerken m{ü}ssen zahlreiche interdependente Entscheidungen getroffen und gleichzeitig mannigfaltige Bedingungen ber{ü}cksichtigt werden. Die verf{ü}gbaren technischen und organisatorischen Alternativm{ö}glichkeiten sind normalerweise so vielf{ä}ltig und komplex, dass eine manuelle Planung praktisch nicht m{ö}glich ist. In diesem Artikel wird das Potential und die Methodik der mathematischen Optimierung bei der kostenoptimalen Planung von Kommunikationsnetzen vorgestellt. Als Ausgangspunkt wird exemplarisch eine typische praktische Aufgabe, die Struktur- und Konfigurationsplanung mehrstufiger Telekommunikationsnetzwerke, dargestellt. Anschließend werden kurz die wesentlichen Modellierungstechniken und Verfahrensans{ä}tze der mathematischen Optimierung skizziert. Abschließend gehen wir auf die Planung einer ad{ä}quaten Informations- und Kommunikations- Infrastruktur f{ü}r ein dezentrales Energieversorgungsnetz ein. T3 - ZIB-Report - 03-37 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7591 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten T1 - Integer programming approaches to access and backbone IP-network planning N2 - In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer has to satisfy certain survivability and routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented. T3 - ZIB-Report - 02-41 KW - Network design KW - Traffic enineering KW - Internet routing KW - Mixed-integer programming Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7081 ER - TY - GEN A1 - Bley, Andreas T1 - Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths N2 - We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is $np-hard$ to approximate the minimal longest path length within a factor less than $8/7$ or the minimal longest arc length within a factor less than $9/8$. This answers the (previously) open question whether these problems are $np-hard$ or not. We also present a simple algorithm that achieves an $\mathcal{O}(|V|)$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is $\mathcal{NP}$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP. T3 - ZIB-Report - 05-04 KW - Inverse Shortest Paths KW - Computational Complexity KW - Approximation KW - Shortest Path Routing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8388 ER - TY - GEN A1 - Bienstock, Daniel A1 - Bley, Andreas T1 - Capacitated Network Design with Multicast Commodities N2 - This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations. T3 - ZIB-Report - 00-14 KW - multicast network design KW - Steiner tree packing Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5823 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten T1 - Optimierung in der Planung und beim Aufbau des G-WiN N2 - Ende Juni diesen Jahres wurde das Gigabit-Wissenschaftsnetz offiziell gestartet. In der zweijährigen Vorbereitungsphase wurden nicht nur die technischen Möglichkeiten der neuen Übertragungstechniken und Dienste getestet. Es wurden auch verschiedene Fragestellungen zum effizienten Einsatz der verfügbaren Ressourcen für den Betrieb des G-WiN untersucht. In diesem Artikel beschreiben wir, wie das G-WiN zu seiner jetzigen Struktur und Topologie gekommen ist. T3 - ZIB-Report - 00-48 Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6169 ER - TY - CHAP A1 - Bley, Andreas A1 - Koch, Thorsten T1 - Integer programming approaches to access and backbone IP-network planning T2 - Modeling, Simulation and Optimization of Complex Processes, Proceedings of the 3rd International Conference on High Performance Scientific Computing, March 6-10, Hanoi, Vietnam Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2002/709/ SP - 87 EP - 110 PB - Springer ER - TY - JOUR A1 - Bley, Andreas A1 - Koch, Thorsten T1 - Optimierung des G-WiN JF - DFN-Mitteilungen Y1 - 2000 UR - http://www.dfn.de/content/fileadmin/5Presse/DFNMitteilungen/heft54.pdf IS - 54 SP - 13 EP - 15 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten A1 - Niu, Lingfeng T1 - Experiments with nonlinear extensions to SCIP N2 - This paper describes several experiments to explore the options for solving a class of mixed integer nonlinear programming problems that stem from a real-world mine production planning project. The only type of nonlinear constraints in these problems are bilinear equalities involving continuous variables, which enforce the ratios between elements in mixed material streams. A branch-and-bound algorithm to handle the integer variables has been tried in another project. However, this branch-and-bound algorithm is not effective for handling the nonlinear constraints. Therefore state-of-the-art nonlinear solvers are utilized to solve the resulting nonlinear subproblems in this work. The experiments were carried out using the NEOS server for optimization. After finding that current nonlinear programming solvers seem to lack suitable preprocessing capabilities, we preprocess the instances beforehand and use an heuristic approach to solve the nonlinear subproblems. In the appendix, we explain how to add a polynomial constraint handler that uses IPOPT as embedded nonlinear programming solver for the constraint programming framework SCIP. This is one of the crucial steps for implementing our algorithm in SCIP. We briefly described our approach and give an idea of the work involved. T3 - ZIB-Report - 08-28 Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8300 SN - 1438-0064 ER - TY - CHAP A1 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland ED - Dean, Nathaniel ED - Hsu, D. ED - Ravi, R. T1 - Design of broadband virtual private networks: Model and Heuristics for the B–WiN T2 - Robust communication networks: Interconnection and survivability. DIMACS workshop, Princeton, NJ, USA, 1998 at Rutgers University Y1 - 2000 VL - 53 SP - 1 EP - 16 PB - American Mathematical Society CY - Providence, RI ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks T2 - Photonic Networks, 14. 2013 ITG Symposium. Proceedings Y1 - 2013 SP - 1 EP - 5 ER - TY - CHAP A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts T2 - Proceedings of 4th International Network Optimization Conference (INOC2009) N2 - Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6. Y1 - 2009 ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - WDM Fiber Replacement Scheduling T2 - Proceedings of INOC 2013 Y1 - 2013 U6 - https://doi.org/10.1016/j.endm.2013.05.092 VL - 41 SP - 189 EP - 196 ER - TY - GEN A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks N2 - The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/). T3 - ZIB-Report - 13-62 KW - Scheduling, Extended Formulations, Network Migration, WDM Networks Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42654 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670 SN - 1438-0064 ER - TY - CHAP A1 - Bley, Andreas A1 - Menne, Ulrich A1 - Klähne, Roman A1 - Raack, Christian A1 - Wessäly, Roland T1 - Multi-layer network design – A model-based optimization approach T2 - Proceedings of the PGTS 2008, Berlin, Germany Y1 - 2008 SP - 107 EP - 116 PB - Polish-German Teletraffic Symposium CY - Berlin, Germany ER - TY - GEN A1 - Bley, Andreas T1 - An Integer Programming Algorithm for Routing Optimization in IP Networks N2 - Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm. T3 - ZIB-Report - 08-30 KW - Shortest Path Routing KW - Integer Programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10814 SN - 1438-0064 ER - TY - THES A1 - Bley, Andreas T1 - Routing and Capacity Optimization for IP Networks N2 - This thesis is concerned with dimensioning and routing optimization problems for communication networks that employ a shortest path routing protocol such as OSPF, IS-IS, or RIP. These protocols are widely used in the Internet. With these routing protocols, all end-to-end data streams are routed along shortest paths with respect to a metric of link lengths. The network administrator can configure the routing only by modifying this metric. In this thesis we consider the unsplittable shortest path routing variant, where each communication demand must be sent unsplit through the network. This requires that all shortest paths are uniquely determined. The major difficulties in planning such networks are that the routing can be controlled only indirectly via the routing metric and that all routing paths depend on the same routing metric. This leads to rather complicated and subtle interdependencies among the paths that comprise a valid routing. In contrast to most other routing schemes, the paths for different communication demands cannot be configured independent of each other. Part I of the thesis is dedicated to the relation between path sets and routing metrics and to the combinatorial properties of those path sets that comprise a valid unsplittable shortest path routing. Besides reviewing known approaches to find a compatible metric for a given path set (or to prove that none exists) and discussing some properties of valid path sets, we show that the problem of finding a compatible metric with integer lengths as small as possible and the problem of finding a smallest possible conflict in the given path set are both NP-hard to approximate within a constant factor. In Part II of the thesis we discuss the relation between unsplittable shortest path routing and several other routing schemes and we analyze the computational complexity of three basic unsplittable shortest path routing problems. We show that the lowest congestion that can be obtained with unsplittable shortest path routing may significantly exceed that achievable with other routing paradigms and we prove several non-approximability results for unsplittable shortest path routing problems that are stronger than those for the corresponding unsplittable flow problems. In addition, we derive various polynomial time approximation algorithms for general and special cases of these problems. In Part III of the thesis we finally develop an integer linear programming approach to solve these and more realistic unsplittable shortest path routing problems to optimality. We present alternative formulations for these problems, discuss their strength and computational complexity, and show how to derive strong valid inequalities. Eventually, we describe our implementation of this solution approach and report on the numerical results obtained for real-world problems that came up in the planning the German National Research and Education Networks G-WiN and X-WiN and for several benchmark instances. N2 - Die Arbeit befasst sich mit der Kapazitäts- und Routenplanung für Kommunikationsnetze, die ein kürzeste-Wege Routingprotokoll verwenden. Diese Art von Protokollen ist im Internet weit verbreitet. Bei diesen Routingverfahren wird für jede Verbindung im Netz ein Längenwert festgelegt, diese Längen formen die sogenannte Routingmetrik. Die Routingwege der Kommunikationsbedarfe sind dann die jeweiligen kürzesten Wege bezüglich dieser Metrik. Bei der in der Arbeit untersuchten Variante dieser Routingprotokolle wird zusätzlich verlangt, dass es je Kommunikationsbedarf genau einen eindeutigen kürzesten Weg gibt. Die Schwierigkeit bei der Planung solcher Netze besteht darin, dass sich die Routingwege einerseits nur indirekt über die Routingmetrik beeinflussen lassen, andererseits aber alle Routingwege von der gleichen Metrik abhängen. Dadurch können die Wege verschiedener Kommunikationsanforderungen nicht wie bei anderen Routingverfahren unabhängig voneinander gewählt werden. Im erstem Teil der Arbeit werden der Zusammenhang zwischen gegebenen Wegesystemen und kompatiblen Routingmetriken sowie die Beziehungen der Wege eines zulässigen eindeutige-kürzeste-Wege-Routings untereinander untersucht. Dabei wird unter Anderem gezeigt, dass es NP-schwer ist, eine kompatible Metrik mit kleinstmöglichen Routinglängen zu einem gegebenen Wegesystem zu finden. Es wird auch bewiesen, dass das Finden eines kleinstmöglichen Konfliktes in einem gegebenen Wegesystem, zu dem keine kompatible Metrik existiert, NP-schwer ist. Im zweiten Teil der Arbeit wird die Approximierbarkeit von drei grundlegenden Netz- und Routenplanungsproblemen mit eindeutige-kürzeste-Wege-Routing untersucht. Für diese Probleme werden stärkere Nichtapproximierbarkeitsresultate als für die entsprechenden Einwege-Routing Probleme bewiesen und es werden verschiedene polynomiale Approximationsverfahren für allgemeine und Spezialfälle entworfen. Ausserdem wird die Beziehung zwischen eindeutige-kürzeste-Wege-Routing und anderen Routingverfahren diskutiert. Im dritten und letzten Teil der Arbeit wird ein (gemischt-) ganzzahliger Lösungsansatz für Planungsprobleme mit eindeutige-kürzeste-Wege-Routing vorgestellt. Für die im zweiten Teil diskutierten grundlegenden Netz- und Routenplanungsprobleme werden verschiedene (gemischt-) ganzzahlige lineare Modelle vorgestellt und es wird deren Lösbarkeit und die Stärke ihrer LP Relaxierungen untersucht. Es wird auch gezeigt, wie sich starke gültig Ungleichungen aus den in diesen Modellen enthalten Substrukturen ableiten lassen. Schlielich werden am Ende der Arbeit die Software-Implementierung dieses Lösungsverfahrens für eine praxisrelevante Verallgemeinerung der Planungsprobleme sowie die damit erzielten numerischen Ergebnisse vorgestellt und diskutiert. KW - kombinatorische Optimierung KW - gemischt-ganzzahlige Programmierung KW - kürzeste-Wege Routing KW - Approximationsalgorithmen KW - combinatorial optimization KW - mixed-integer programming KW - shortest path routing KW - approximation algorithms Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-15530 SN - 978-3-86727-281-0 ER - TY - GEN A1 - Bley, Andreas T1 - Routing and Capacity Optimization for IP networks N2 - This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years. T3 - ZIB-Report - 07-33 KW - kombinatorische Optimierung KW - gemischt-ganzzahlige Programmierung KW - kürzeste-Wege Routing KW - Approximationsalgorithmen KW - combinatorial optimization KW - mixed-integer programming KW - shortest path routing KW - approximation algorithms Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10323 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts N2 - Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6. T3 - ZIB-Report - 09-15 KW - shortest path routing KW - computational complexity Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11276 SN - 1438-0064 ER - TY - CHAP A1 - Matuschke, Jannik A1 - Bley, Andreas A1 - Müller, Benjamin ED - Bodlaender, Hans L. ED - Italiano, Giuseppe F. T1 - Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections N2 - We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-40450-4_60 VL - Algorithms -- ESA 2013 SP - 707 EP - 718 PB - Springer ER -