@misc{EisenblaetterGroetschelKoster2002, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequenzplanung im Mobilfunk}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6762}, number = {02-09}, year = {2002}, abstract = {Telekommunikation ist seit Jahren \glqq in\grqq. Zun{\"a}chst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine {\"u}berw{\"a}ltigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgel{\"o}st durch die UMTS-Lizenzversteigerungen, Rezessions- und S{\"a}ttigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon {\"u}berzeugt, dass technischer Fortschritt und n{\"u}tzliche Dienste demn{\"a}chst die Stimmung wieder {\"a}ndern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein {\"U}berblick {\"u}ber diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemad{\"a}quater Algorithmen erreichen kann.}, language = {de} } @misc{KosterWagler2006, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {The extreme points of QSTAB(G) and its implications}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9249}, number = {06-30}, year = {2006}, abstract = {Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs \$G\$ where the stable set polytope STAB\$(G)\$ coincides with the clique constraint stable set polytope QSTAB\$(G)\$. For all imperfect graphs STAB\$(G) \subset\$ QSTAB\$(G)\$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB\$(G)\$ and QSTAB\$(G)\$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB\$(G)\$ and QSTAB\$(G)\$ which is equivalent to the imperfection ratio imp\$(G)\$ of \$G\$. To determine imp\$(G)\$, both knowledge on the facets of STAB\$(G)\$ and the extreme points of QSTAB\$(G)\$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB\$(G)\$, provided a complete description of the facets of STAB\$(\overline G)\$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB\$(G)\$ by establishing a 1-1 correspondence to the facet-defining subgraphs of \$\overline G\$. We discuss several consequences, in particular, we give alternative proofs of several famous results.}, language = {en} } @misc{BodlaenderFominKosteretal.2006, author = {Bodlaender, Hans L. and Fomin, Fedor V. and Koster, Arie M.C.A. and Kratsch, Dieter and Thilikos, Dimitrios M.}, title = {On exact algorithms for treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9265}, number = {06-32}, year = {2006}, abstract = {We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time \$O^\ast(2^n)\$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple \$O^\ast(4^n)\$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in \$O^\ast(2.9512^n)\$ time and polynomial space.}, 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} } @misc{KosterZymolkaKutschka2007, author = {Koster, Arie M.C.A. and Zymolka, Adrian and Kutschka, Manuel}, title = {Algorithms to Separate {0,1/2}-Chvatal-Gomory Cuts}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9531}, number = {07-10}, year = {2007}, abstract = {Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or \$\frac{1}{2}\$, such cuts are known as \$\{0,\frac{1}{2}\}\$-cuts. It has been proven by Caprara and Fischetti (1996) that separation of \$\{0,\frac{1}{2}\}\$-cuts is NP-hard. In this paper, we study ways to separate \$\{0,\frac{1}{2}\}\$-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated \$\{0,\frac{1}{2}\}\$-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.}, 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} } @article{EisenblaetterGroetschelKoster2002, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequency Planning and Ramifications of Coloring}, journal = {Discussiones Mathematicae, Graph Theory}, number = {22}, pages = {51 -- 88}, year = {2002}, language = {en} } @article{EisenblaetterGroetschelKoster2002, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequenzplanung im Mobilfunk}, journal = {DMV-Mitteilungen}, number = {1}, pages = {18 -- 25}, year = {2002}, language = {en} } @incollection{EisenblaetterFuegenschuhKochetal.2002, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Mathematical Model of Feasible Network Configurations for UMTS}, booktitle = {Telecommunications network design and management}, editor = {G. Anandalingam, S.}, publisher = {Kluwer}, pages = {1 -- 24}, year = {2002}, language = {en} } @article{BauschertBuesingD'Andreagiovannietal.2014, author = {Bauschert, Thomas and B{\"u}sing, Christina and D'Andreagiovanni, Fabio and Koster, Arie M.C.A. and Kutschka, Manuel and Steglich, Uwe}, title = {Network planning under demand uncertainty with robust optimization}, volume = {52}, journal = {IEEE Communications Magazine}, number = {2}, doi = {10.1109/MCOM.2014.6736760}, pages = {178 -- 185}, year = {2014}, language = {en} } @misc{BauschertBuesingD'Andreagiovannietal.2013, author = {Bauschert, Thomas and B{\"u}sing, Christina and D'Andreagiovanni, Fabio and Koster, Arie M.C.A. and Kutschka, Manuel and Steglich, Uwe}, title = {Network Planning under Demand Uncertainty with Robust Optimization}, issn = {1438-0064}, doi = {10.1109/MCOM.2014.6736760}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42557}, year = {2013}, abstract = {The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.}, 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} } @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} } @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{ConiglioGrimmKosteretal.2015, author = {Coniglio, Stefano and Grimm, Boris and Koster, Arie M.C.A. and Tieves, Martin and Werner, Axel}, title = {Optimal offline virtual network embedding with rent-at-bulk aspects}, arxiv = {http://arxiv.org/abs/1501.07887}, pages = {9}, year = {2015}, abstract = {Network virtualization techniques allow for the coexistence of many virtual networks (VNs) jointly sharing the resources of an underlying substrate network. The Virtual Network Embedding problem (VNE) arises when looking for the most profitable set of VNs to embed onto the substrate. In this paper, we address the offline version of the problem. We propose a Mixed-Integer Linear Programming formulation to solve it to optimality which accounts for acceptance and rejection of virtual network requests, allowing for both splittable and unsplittable (single path) routing schemes. Our formulation also considers a Rent-at-Bulk (RaB) model for the rental of substrate capacities where economies of scale apply. To better emphasize the importance of RaB, we also compare our method to a baseline one which only takes RaB into account a posteriori, once a solution to VNE, oblivious to RaB, has been found. Computational experiments show the viability of our approach, stressing the relevance of addressing RaB directly with an exact formulation.}, 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{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} }