@misc{BauschertBuesingD'Andreagiovannietal., 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}, 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} } @misc{KosterKutschkaRaack, 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}, 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{RaackKosterWessaely, 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}, 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{KosterZymolkaKutschka, 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}, 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., 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}, 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} } @misc{KosterOrlowskiRaacketal., 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}, 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{KosterWagler, 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}, 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., 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}, 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{OrlowskiKosterRaacketal., 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}, 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., 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}, 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} }