@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{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{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{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{IdzikowskiOrlowskiRaacketal., author = {Idzikowski, Filip and Orlowski, Sebastian and Raack, Christian and Woesner, Hagen and Wolisz, Adam}, title = {Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings}, organization = {Zuse Institute Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11692}, number = {10-07}, abstract = {We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure.}, language = {en} } @misc{PossRaack, author = {Poss, Michael and Raack, Christian}, title = {Affine recourse for the robust network design problem: between static and dynamic routing}, doi = {10.1002/net.21482}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12122}, number = {11-03}, abstract = {Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.}, language = {en} } @misc{BetkerKosiankowskiLangeetal., author = {Betker, Andreas and Kosiankowski, Dirk and Lange, Christoph and Pfeuffer, Frank and Raack, Christian and Werner, Axel}, title = {Energy efficiency in extensive multilayer core and regional networks with protection}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17154}, abstract = {Energy-efficient operation of large telecommunication networks is an important issue today and in the near future. Given that the energy consumption rises with the ever increasing demand for capacity and network speed, there is a growing interest in strategies for a sustainable network management. It is a well-known fact that traffic demands vary significantly over time, most notably in day/night- and in weekly cycles. This provides the main potential for energy-saving strategies. We study the question of how much power is necessary to operate a network with state-of-the-art hardware during peak or low-traffic times. The study respects realistic side constraints, such as protection requirements and routing schemes, and takes the special structure of an extensive nation-wide optical network, including backbone and regional sections, into account. We formulate mixed integer programming models for the corresponding optimization problems using predictions for traffic matrices, as well as state-of-the-art hardware and power models. We address questions as the following: How much energy is spent in the core and in metro regions of the network and how big are the savings in low-demand scenarios if we always assume the system power-minimum in these situations? What is the influence of different hardware on the overall energy consumption? How much do different routing schemes or protection scenarios restrict potential energy savings?}, language = {en} } @misc{MenneRaackWessaelyetal., 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}, 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} } @misc{AchterbergRaack, 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}, 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{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} }