@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} } @inproceedings{KosterKutschkaRaack2010, author = {Koster, Arie M.C.A. and Kutschka, Manuel and Raack, Christian}, title = {Towards Robust Network Design using Integer Linear Programming Techniques}, booktitle = {Proceedings of the NGI 2010, Paris, France}, publisher = {Next Generation Internet}, address = {Paris, France}, year = {2010}, language = {en} } @article{AchterbergRaack2010, author = {Achterberg, Tobias and Raack, Christian}, title = {The MCF-Separator - Detecting and Exploiting Multi-Commodity Flows in MIPs}, journal = {Mathematical Programming C}, number = {2}, pages = {125 -- 165}, year = {2010}, language = {en} } @article{DashGuenluekRaack2011, author = {Dash, Sanjeeb and G{\"u}nl{\"u}k, Oktay and Raack, Christian}, title = {A note on the MIR closure and basic relaxations of polyhedra}, volume = {39}, journal = {Optimization Research Letters}, number = {3}, pages = {198 -- 199}, year = {2011}, language = {en} } @inproceedings{KosterRaack2009, author = {Koster, Arie M.C.A. and Raack, C.}, title = {A packing integer program arising in two-layer network design}, booktitle = {Proceedings of the INOC 2009, Pisa, Italy}, publisher = {International Network Optimization Conference}, address = {Pisa, Italy}, year = {2009}, 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{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{KosterKutschkaRaack2011, author = {Koster, Arie M.C.A. and Kutschka, Manuel and Raack, Christian}, title = {Robust Network Design: Formulations, Valid Inequalities, and Computations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13890}, number = {11-34}, year = {2011}, abstract = {Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [2004]. We present three different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements we compare the formulations and report on the speed up by the valid inequalities. We study the "price of robustness" and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods.}, language = {en} } @misc{AchterbergRaack2009, author = {Achterberg, Tobias and Raack, Christian}, title = {The MCF-Separator -- Detecting and Exploiting Multi-Commodity Flow Structures in MIPs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11592}, number = {09-38}, year = {2009}, abstract = {Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.}, language = {en} } @misc{WernerAurzadaBleyetal.2014, author = {Werner, Axel and Aurzada, Frank and Bley, Andreas and Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Guillemard, Mijail and Kutyniok, Gitta and Philipp, Friedrich and Raack, Christian and Scheutzow, Michael}, title = {Mathematics for telecommunications}, volume = {1}, journal = {MATHEON - Mathematics for Key Technologies}, editor = {Deuflhard, Peter and Gr{\"o}tschel, Martin and H{\"o}mberg, Dietmar and Horst, Ulrich and Kramer, J{\"u}rg and Mehrmann, Volker and Polthier, Konrad and Schmidt, Frank and Sch{\"u}tte, Christof and Skutella, Martin and Sprekels, J{\"u}rgen}, edition = {EMS Series in Industrial and Applied Mathematics}, publisher = {European Mathematical Society}, doi = {10.4171/137}, pages = {75 -- 89}, year = {2014}, language = {en} } @article{D'AndreagiovanniKrolikowskiPulaj2014, author = {D'Andreagiovanni, Fabio and Krolikowski, Jonatan and Pulaj, Jonad}, title = {A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods}, volume = {26}, journal = {Applied Soft Computing}, doi = {10.1016/j.asoc.2014.10.016}, pages = {497 -- 507}, year = {2014}, abstract = {We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (B{\"u}sing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.}, language = {en} } @misc{MenneRaackWessaelyetal.2012, author = {Menne, Ulrich and Raack, Christian and Wess{\"a}ly, Roland and Kharitonov, Daniel}, title = {Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks}, issn = {1438-0064}, doi = {10.1109/ONDM.2012.6210206}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14843}, year = {2012}, abstract = {In this paper, we study the influence of technology, traffic properties and price trends on optimized design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node, we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical (packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in traffic volume, demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints, we assess the relative roles of the two distinct equipment groups, IP routers and optical cross-connects, with respect to resulting changes in cost-sensitive network architectures.}, language = {en} }