TY - GEN A1 - Idzikowski, Filip A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Woesner, Hagen A1 - Wolisz, Adam T1 - Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings N2 - 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. T3 - ZIB-Report - 10-07 KW - network design KW - energy efficiency KW - power consumption KW - multi-layer KW - multi-hour KW - multi-period Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11692 SN - 1438-0064 ER - TY - GEN A1 - Raack, Christian A1 - Koster, Arie M.C.A. A1 - Wessäly, Roland T1 - On the strength of cut-based inequalities for capacitated network design polyhedra N2 - 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). T3 - ZIB-Report - 07-08 KW - cutset-polyhedra KW - flow-cutset inequalities KW - network design KW - mixed integer programming Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9512 ER - TY - GEN A1 - Poss, Michael A1 - Raack, Christian T1 - Affine recourse for the robust network design problem: between static and dynamic routing N2 - 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. T3 - ZIB-Report - 11-03 KW - robust optimization KW - network design KW - recourse KW - affine adjustable robust counterparts KW - affine routing Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12122 ER - TY - THES A1 - Raack, Christian T1 - Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty N2 - 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. KW - combinatorial optimization KW - cutting planes KW - integer programming KW - network design KW - robustness Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-36167 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/3407 ER - TY - GEN A1 - Betker, Andreas A1 - Kosiankowski, Dirk A1 - Lange, Christoph A1 - Pfeuffer, Frank A1 - Raack, Christian A1 - Werner, Axel T1 - Energy efficiency in extensive multilayer core and regional networks with protection N2 - 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? T3 - ZIB-Report - 12-45 KW - telecommunications KW - network design KW - routing KW - energy efficiency Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17154 SN - 1438-0064 ER -