@misc{OrlowskiKosterRaacketal.2006, 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}, year = {2006}, 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{HuelsermannJaegerKosteretal.2006, 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}, year = {2006}, 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{KosterZymolkaJaegeretal.2003, author = {Koster, Arie M.C.A. and Zymolka, Adrian and J{\"a}ger, Monika and H{\"u}lsermann, Ralf and Gerlach, Christoph}, title = {Demand-wise Shared Protection for Meshed Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7461}, number = {03-24}, year = {2003}, abstract = {In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs.}, language = {en} } @misc{RaackKosterWessaely2007, author = {Raack, Christian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {On the strength of cut-based inequalities for capacitated network design polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9512}, number = {07-08}, year = {2007}, abstract = {In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).}, language = {en} } @phdthesis{Bley2007, author = {Bley, Andreas}, title = {Routing and Capacity Optimization for IP Networks}, isbn = {978-3-86727-281-0}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-15530}, year = {2007}, abstract = {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.}, language = {en} } @misc{Bley2007, author = {Bley, Andreas}, title = {Routing and Capacity Optimization for IP networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10323}, number = {07-33}, year = {2007}, abstract = {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.}, language = {en} } @misc{Raack2005, type = {Master Thesis}, author = {Raack, Christian}, title = {Employing Mixed-Integer Rounding in Telecommunication Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10023}, school = {Zuse Institute Berlin (ZIB)}, year = {2005}, abstract = {In dieser Diplomarbeit werden grundlegende Probleme der kostenoptimalen Dimensionierung von Telekommunikationsnetzwerken untersucht. Diese werden als lineare gemischt ganzzahlige Programme formuliert, wobei sich in der Modellierung auf die Konzepte Routing und Kapazit{\"a}tszuweisung beschr{\"a}nkt wird. Es werden parallel drei {\"u}bliche, aus der Praxis motivierte M{\"o}glichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazit{\"a}t zu nutzen. Diese unterscheiden wir als DIrected, BIdirected und UNdirected. Die studierten Probleme treten als Relaxierungen vieler realistischer Fragestellungen der Netzwerkoptimierung auf. Sie enthalten elementare Strukturen, deren Studium ausschlaggebend ist f{\"u}r das Verst{\"a}ndnis komplexerer Modelle. Letztere k{\"o}nnen zus{\"a}tzliche Erfordernisse ber{\"u}cksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur L{\"o}sung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch \& Bound und Schnittebenenverfahren kombiniert (Branch \& Cut). F{\"u}r die Wirksamkeit dieser Algorithmen ist es sehr n{\"u}tzlich, m{\"o}glichst genaue Kenntnisse der Struktur der Seitenfl{\"a}chen der zugrundeliegenden Polyeder zu haben, welche die konvexe H{\"u}lle der L{\"o}sungsmenge beschreiben. Es sind starke g{\"u}ltige Ungleichungen zu finden, welche hochdimensionale Seitenfl{\"a}chen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden k{\"o}nnen und die numerische Stabilit{\"a}t der Algorithmen m{\"o}glichst nicht beeinflussen. Diese Arbeit besch{\"a}ftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verst{\"a}rkung g{\"u}ltiger Ungleichungen unter Verwendung der Ganzzahligkeitsnebenbedingungen. Es wird eine MIR-Prozedur motiviert, bestehend aus den Schritten Aggregieren, Substituieren, Komplementieren und Skalieren, welche durch Ausnutzung der Struktur der gegebenen Parameter zu einer g{\"u}ltigen Basisungleichung f{\"u}hrt, die dann durch MIR eine starke und oft facetten-induzierende Ungleichung gibt. Es werden verschieden Klassen solcher Ungleichungen untersucht und auf ihre Praxistauglichkeit beim Einsatz in Branch \& Cut-Verfahren getestet. Nach einer kurzen Einf{\"u}hrung werden in Kapitel 2 die f{\"u}r uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausf{\"u}hrliche {\"U}bersicht {\"u}ber die Technik MIR.Wir besch{\"a}ftigen uns vor allen Dingen mit den Begriffen Superadditivit{\"a}t und Lifting und behandeln Aspekte wie Numerik und beschr{\"a}nkte Variablen. Kapitel 4 und Kapitel 5 umfassen Untersuchungen zu so genannten cut sets. Diese Polyeder werden durch Schnitte in Netzwerken definiert und relaxieren die von uns behandelten Probleme. Haupts{\"a}chlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen f{\"u}r cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzit{\"a}tsbereitstellung und durch beschr{\"a}nkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen f{\"u}r cut sets auch Facetten der zugeh{\"o}rigen relaxierten Polyeder sind. Im Kapitel 6 geben wir weitere Typen von MIR-Ungleichungen an, die auf anderen Netzwerkstrukturen basieren und weisen ferner auf offene Fragen sowie interessante Ideen hin. Das Kapitel 7 widmet sich schließlich der Entwicklung und Implementation von Separationsalgorithmen. Wir testen einige der entwickelten Ungleichungsklassen mit Hinblick auf Ihre Wirksamkeit zur L{\"o}sung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse.}, language = {de} } @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} }