@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} } @article{RaackKosterOrlowskietal.2011, author = {Raack, Christian and Koster, Arie M.C.A. and Orlowski, Sebastian and Wess{\"a}ly, Roland}, title = {On cut-based inequalities for capacitated network design polyhedra}, volume = {57}, journal = {Networks}, number = {2}, pages = {141 -- 156}, year = {2011}, language = {en} } @misc{GroetschelRaackWerner2013, author = {Gr{\"o}tschel, Martin and Raack, Christian and Werner, Axel}, title = {Towards optimizing the deployment of optical access networks}, issn = {1438-0064}, doi = {10.1007/s13675-013-0016-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18627}, year = {2013}, abstract = {In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a "unified" integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.}, language = {en} } @misc{IdzikowskiOrlowskiRaacketal.2010, 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}, year = {2010}, 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} } @inproceedings{IdzikowskiOrlowskiRaacketal.2010, author = {Idzikowski, Filip and Orlowski, Sebastian and Raack, Christian and Woesner, Hagen and Wolisz, Adam}, title = {Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios}, booktitle = {Proceedings of the 14th conference on Optical network design and modeling}, publisher = {IEEE Press}, address = {Piscataway, NJ, USA}, pages = {42 -- 47}, year = {2010}, language = {en} } @article{IdzikowskiOrlowskiRaacketal.2011, 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}, journal = {Optical Switching and Networking, Special Issue on Green Communications}, year = {2011}, 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{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} } @misc{RaackRaymondWerneretal.2013, author = {Raack, Christian and Raymond, Annie and Werner, Axel and Schlechte, Thomas}, title = {Integer Programming and Sports Rankings}, issn = {1438-0064}, doi = {10.1515/jqas-2013-0111}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18068}, year = {2013}, abstract = {Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years.}, language = {en} } @misc{PossRaack2011, 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}, year = {2011}, 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} } @article{RaackRaymondSchlechteetal.2013, author = {Raack, Christian and Raymond, Annie and Schlechte, Thomas and Werner, Axel}, title = {Standings in sports competitions using integer programming}, volume = {10}, journal = {Journal of Quantitative Analysis in Sports}, number = {2}, publisher = {De Gruyter}, doi = {10.1515/jqas-2013-0111}, pages = {131 -- 137}, year = {2013}, language = {en} } @phdthesis{Raack2012, author = {Raack, Christian}, title = {Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-36167}, school = {Technische Universit{\"a}t Berlin}, year = {2012}, abstract = {In this thesis, we develop methods in mathematical optimization to dimension networks at minimal cost. Given hardware and cost models, the challenge is to provide network topologies and efficient capacity plans that meet the demand for network traffic (data, passengers, freight). We incorporate crucial aspects of practical interest such as the discrete structure of available capacities as well as the uncertainty of demand forecasts. The considered planning problems typically arise in the strategic design of telecommunication or public transport networks and also in logistics. One of the essential aspects studied in this work is the use of cutting planes to enhance solution approaches based on multi-commodity flow formulations. Providing theoretical and computational evidence for the efficacy of inequalities based on network cuts, we extend existing theory and algorithmic work in different directions. First, we prove that special-purpose techniques, originally designed to solve capacitated network design problems, can be successfully integrated into general-purpose mixed integer programming (MIP) solvers. Our approach relies on an automatic detection of network structure within the constraint matrix of general mixed in teger programs. More precisely, we identify multi-commodity (MCF) network sub-matrices and resolve the isomorphisms of the commodity blocks as well as the original graph structure. In the subsequent separation framework, we guide the constraint aggregation of available cutting plane procedures (e. g. based on mixed integer rounding) to produce strong cutting planes that reflect the structure of the constructed network. The new MCF-separator integrates network design specific methodology into general optimization tools which is of particular importance for practitioners that tend to use MIP solvers as black boxes. Extensive computational tests show that our network detection procedure operates accurately and reliably. Moreover, due to the generated cutting planes, we achieve an average speed-up of a factor of two for pure network design problems with general MIP solvers. Many of these instances can only be solved to optimality in reasonable time if the new MCF-separator is active. In 9 \% of the instances of general MIP test sets we find consistent embedded networks and generate violated inequalities. In this case the computation time decreases by 18 \% on average with almost no degradation for unaffected instances. Second, we generalize concepts, models, and cutting planes from deterministic network design to robust network design, incorporating the uncertainty of traffic demands. We enhance and compare strategies that are able to handle a polyhedral set of different traffic scenarios. In particular, we consider two correlated solution methods, based on separating extreme demand scenarios and dualizing the linear description of the demand polytope, respectively. We consider robust network design as two-stage robust optimization with recourse. First stage capacity decisions are fixed for all scenarios while the second stage flow depends on the realized demands. In order to reroute the traffic as a function of the demand dynamics, we consider three alternative recourse actions, namely, static, affine, and dynamic routing. We analyze properties of the new affine routing and show that it combines advantages of the well-known static and dynamic models. Using the concept of robust cut-set polyhedra and the corresponding lifting theorems, we develop several classes of facet-defining inequalities based on network cuts that can be used to further accelerate solution strategies for robust network design. Among them are the well-known (flow) cut-set inequalities, which we generalize to general demand polytopes, but also new classes of potential cutting planes, so-called envelope inequalities. The practical importance of the developed cutting planes is revealed by a series of computational tests. Similar to the results for the MCF-separator we achieve speed-ups of two and more using the generalized classes of strong inequalities. To evaluate the robustness of solutions that are computed with our framework we use real-life measurements of traffic dynamics from different existing telecommunication networks, among them data from the German and the European research network. Our results indicate that traffic peaks do not necessarily occur all simultaneously with respect to different source-destination pairs, which is of practical importance for the design of uncertainty sets. It is, in particular, not necessary to dimension networks for a scenario that assumes all source-destination traffic is at its peak simultaneously. With our solutions we save up to 20 \% of the corresponding solution cost compared to this artificial scenario and achieve comparable levels of robustness.}, language = {en} } @article{GroetschelRaackWerner2013, author = {Gr{\"o}tschel, Martin and Raack, Christian and Werner, Axel}, title = {Towards optimizing the deployment of optical access networks}, volume = {2}, journal = {EURO Journal on Computational Optimization}, publisher = {Springer}, doi = {10.1007/s13675-013-0016-x}, pages = {17 -- 53}, year = {2013}, language = {en} } @article{BetkerKosiankowskiLangeetal.2014, author = {Betker, Andreas and Kosiankowski, Dirk and Lange, Christoph and Pfeuffer, Frank and Raack, Christian and Werner, Axel}, title = {Energy efficiency in extensive IP-over-WDM networks with protection}, journal = {Operations Research Proceedings 2012}, editor = {Helber, Stefan and Breitner, Michael and R{\"o}sch, Daniel and Sch{\"o}n, Cornelia and Graf von der Schulenburg, Johann-Matthias and Sibbertsen, Philipp and Steinbach, Marc and Weber, Stefan and Wolter, Anja}, publisher = {Springer}, doi = {10.1007/978-3-319-00795-3_14}, pages = {93 -- 99}, year = {2014}, language = {en} } @article{PossRaack2013, author = {Poss, Michael and Raack, Christian}, title = {Affine recourse for the robust network design problem: Between static and dynamic routing}, volume = {61}, journal = {Networks - Special Issue: INOC 2011 Conference, June 13-16, 2011, Hamburg, Germany}, number = {2}, doi = {10.1002/net.21482}, pages = {180 -- 198}, year = {2013}, 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} } @inproceedings{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}, booktitle = {Optical Network Design and Modeling (ONDM), 2012 16th International Conference on}, doi = {10.1109/ONDM.2012.6210206}, pages = {1 -- 6}, 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} } @misc{Raack2005, type = {Master Thesis}, author = {Raack, Christian}, title = {Employing Mixed-Integer Rounding in Telecommunication Network Design}, year = {2005}, 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} } @inproceedings{BleyMenneKlaehneetal.2008, author = {Bley, Andreas and Menne, Ulrich and Kl{\"a}hne, Roman and Raack, Christian and Wess{\"a}ly, Roland}, title = {Multi-layer network design - A model-based optimization approach}, booktitle = {Proceedings of the PGTS 2008, Berlin, Germany}, publisher = {Polish-German Teletraffic Symposium}, address = {Berlin, Germany}, pages = {107 -- 116}, year = {2008}, language = {en} }