Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-951 misc Raack, Christian; Koster, Arie M.C.A.; Wessäly, Roland On the strength of cut-based inequalities for capacitated network design polyhedra 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). 2007 urn:nbn:de:0297-zib-9512 ZIB Allgemein OPUS4-957 misc Raack, Christian; Koster, Arie M.C.A.; Orlowski, Sebastian; Wessäly, Roland Capacitated network design using general flow-cutset inequalities 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. 2007 urn:nbn:de:0297-zib-9576 ZIB Allgemein OPUS4-941 misc Orlowski, Sebastian; Koster, Arie M.C.A.; Raack, Christian; Wessäly, Roland Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics 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. 2006 urn:nbn:de:0297-zib-9412 ZIB Allgemein OPUS4-964 misc Koster, Arie M.C.A.; Orlowski, Sebastian; Raack, Christian; Bayer, Georg; Engel, Thomas Single-layer Cuts for Multi-layer Network Design Problems 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. 2007 urn:nbn:de:0297-zib-9641 Mathematical Optimization OPUS4-1002 Masterarbeit / Diplomarbeit Raack, Christian Employing Mixed-Integer Rounding in Telecommunication Network Design In dieser Diplomarbeit werden grundlegende Probleme der kostenoptimalen Dimensionierung von Telekommunikationsnetzwerken untersucht. Diese werden als lineare gemischt ganzzahlige Programme formuliert, wobei sich in der Modellierung auf die Konzepte Routing und Kapazitätszuweisung beschränkt wird. Es werden parallel drei übliche, aus der Praxis motivierte Möglichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazität zu nutzen. Diese unterscheiden wir als DIrected, BIdirected und UNdirected. Die studierten Probleme treten als Relaxierungen vieler realistischer Fragestellungen der Netzwerkoptimierung auf. Sie enthalten elementare Strukturen, deren Studium ausschlaggebend ist für das Verständnis komplexerer Modelle. Letztere können zusätzliche Erfordernisse berücksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur Lösung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch & Bound und Schnittebenenverfahren kombiniert (Branch & Cut). Für die Wirksamkeit dieser Algorithmen ist es sehr nützlich, möglichst genaue Kenntnisse der Struktur der Seitenflächen der zugrundeliegenden Polyeder zu haben, welche die konvexe Hülle der Lösungsmenge beschreiben. Es sind starke gültige Ungleichungen zu finden, welche hochdimensionale Seitenflächen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden können und die numerische Stabilität der Algorithmen möglichst nicht beeinflussen. Diese Arbeit beschäftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verstärkung gültiger Ungleichungen unter Verwendung der Ganzzahligkeitsnebenbedingungen. Es wird eine MIR-Prozedur motiviert, bestehend aus den Schritten Aggregieren, Substituieren, Komplementieren und Skalieren, welche durch Ausnutzung der Struktur der gegebenen Parameter zu einer gültigen Basisungleichung führt, die dann durch MIR eine starke und oft facetten-induzierende Ungleichung gibt. Es werden verschieden Klassen solcher Ungleichungen untersucht und auf ihre Praxistauglichkeit beim Einsatz in Branch & Cut-Verfahren getestet. Nach einer kurzen Einführung werden in Kapitel 2 die für uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausführliche Übersicht über die Technik MIR.Wir beschäftigen uns vor allen Dingen mit den Begriffen Superadditivität und Lifting und behandeln Aspekte wie Numerik und beschränkte Variablen. Kapitel 4 und Kapitel 5 umfassen Untersuchungen zu so genannten cut sets. Diese Polyeder werden durch Schnitte in Netzwerken definiert und relaxieren die von uns behandelten Probleme. Hauptsächlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen für cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzitätsbereitstellung und durch beschränkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen für cut sets auch Facetten der zugehörigen relaxierten Polyeder sind. Im Kapitel 6 geben wir weitere Typen von MIR-Ungleichungen an, die auf anderen Netzwerkstrukturen basieren und weisen ferner auf offene Fragen sowie interessante Ideen hin. Das Kapitel 7 widmet sich schließlich der Entwicklung und Implementation von Separationsalgorithmen. Wir testen einige der entwickelten Ungleichungsklassen mit Hinblick auf Ihre Wirksamkeit zur Lösung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse. 2005 urn:nbn:de:0297-zib-10023 Mathematical Optimization OPUS4-1169 misc Idzikowski, Filip; Orlowski, Sebastian; Raack, Christian; Woesner, Hagen; Wolisz, Adam Dynamic routing at different layers in IP-over-WDM networks -- Maximizing energy savings 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. 2010 urn:nbn:de:0297-zib-11692 Mathematical Optimization OPUS4-1212 misc Poss, Michael; Raack, Christian Affine recourse for the robust network design problem: between static and dynamic routing 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. 2011 urn:nbn:de:0297-zib-12122 10.1002/net.21482 Mathematical Optimization OPUS4-1715 misc Betker, Andreas; Kosiankowski, Dirk; Lange, Christoph; Pfeuffer, Frank; Raack, Christian; Werner, Axel Energy efficiency in extensive multilayer core and regional networks with protection 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? 2012 urn:nbn:de:0297-zib-17154 Mathematical Optimization OPUS4-1484 misc Menne, Ulrich; Raack, Christian; Wessäly, Roland; Kharitonov, Daniel Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks 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. 2012 urn:nbn:de:0297-zib-14843 10.1109/ONDM.2012.6210206 Mathematical Optimization OPUS4-1159 misc Achterberg, Tobias; Raack, Christian The MCF-Separator -- Detecting and Exploiting Multi-Commodity Flow Structures in MIPs 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. 2009 urn:nbn:de:0297-zib-11592 Mathematical Optimization OPUS4-1389 misc Koster, Arie M.C.A.; Kutschka, Manuel; Raack, Christian Robust Network Design: Formulations, Valid Inequalities, and Computations 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. 2011 urn:nbn:de:0297-zib-13890 Mathematical Optimization OPUS4-3306 Masterarbeit / Diplomarbeit Raack, Christian Employing Mixed-Integer Rounding in Telecommunication Network Design 2005 Mathematical Optimization OPUS4-3295 Wissenschaftlicher Artikel Raack, Christian; Koster, Arie M.C.A.; Orlowski, Sebastian; Wessäly, Roland On cut-based inequalities for capacitated network design polyhedra 2011 15 Networks 57 2 141 156 Mathematical Optimization OPUS4-3296 Wissenschaftlicher Artikel Achterberg, Tobias; Raack, Christian The MCF-Separator - Detecting and Exploiting Multi-Commodity Flows in MIPs 2010 40 Mathematical Programming C 2 125 165 Mathematical Optimization OPUS4-3297 Wissenschaftlicher Artikel Idzikowski, Filip; Orlowski, Sebastian; Raack, Christian; Woesner, Hagen; Wolisz, Adam Dynamic routing at different layers in IP-over-WDM networks - Maximizing energy savings 2011 Optical Switching and Networking, Special Issue on Green Communications Mathematical Optimization OPUS4-3299 Konferenzveröffentlichung Idzikowski, Filip; Orlowski, Sebastian; Raack, Christian; Woesner, Hagen; Wolisz, Adam Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios Piscataway, NJ, USA IEEE Press 2010 5 Proceedings of the 14th conference on Optical network design and modeling 42 47 Mathematical Optimization OPUS4-3300 Teil eines Buches Koster, Arie M.C.A.; Orlowski, Sebastian; Raack, Christian; Baier, Georg; Engel, Thomas; Belotti, Pietro Branch-and-cut techniques for solving realistic two-layer network design problems Springer Berlin Heidelberg 2009 23 Graphs and Algorithms in Communication Networks 95 118 Mathematical Optimization OPUS4-3301 Konferenzveröffentlichung Bley, Andreas; Menne, Ulrich; Klähne, Roman; Raack, Christian; Wessäly, Roland Multi-layer network design - A model-based optimization approach Berlin, Germany Polish-German Teletraffic Symposium 2008 9 Proceedings of the PGTS 2008, Berlin, Germany 107 116 Mathematical Optimization OPUS4-3303 Konferenzveröffentlichung Raack, Christian; Koster, Arie M.C.A.; Orlowski, Sebastian; Wessäly, Roland Capacitated network design using general flow-cutset inequalities Spa, Belgium International Network Optimization Conference 2007 Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-07-14 Mathematical Optimization OPUS4-3304 Teil eines Buches Koster, Arie M.C.A.; Orlowski, Sebastian; Raack, Christian; Baier, Georg; Engel, Thomas Single-layer Cuts for Multi-Layer Network Design Problems College Park, MD, U.S.A. Springer 2008 22 Telecommunications Modeling Policy and Technology, also ZIB Report ZR-07-21 1 23 Mathematical Optimization OPUS4-3305 Konferenzveröffentlichung Orlowski, Sebastian; Koster, Arie M.C.A.; Raack, Christian; Wessäly, Roland Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics Spa, Belgium International Network Optimization Conference 2007 Proceedings of the INOC 2007, Spa, Belgium, also ZIB Report ZR-06-47 Mathematical Optimization OPUS4-5166 misc Werner, Axel; Aurzada, Frank; Bley, Andreas; Eisenblätter, Andreas; Geerdes, Hans-Florian; Guillemard, Mijail; Kutyniok, Gitta; Philipp, Friedrich; Raack, Christian; Scheutzow, Michael Deuflhard, Peter; Grötschel, Martin; Hömberg, Dietmar; Horst, Ulrich; Kramer, Jürg; Mehrmann, Volker; Polthier, Konrad; Schmidt, Frank; Schütte, Christof; Skutella, Martin; Sprekels, Jürgen Mathematics for telecommunications EMS Series in Industrial and Applied Mathematics European Mathematical Society 2014 14 MATHEON - Mathematics for Key Technologies 1 75 89 10.4171/137 Mathematical Optimization OPUS4-4745 Konferenzveröffentlichung Menne, Ulrich; Raack, Christian; Wessäly, Roland; Kharitonov, Daniel Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks 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. 2012 5 Optical Network Design and Modeling (ONDM), 2012 16th International Conference on 1 6 10.1109/ONDM.2012.6210206 Mathematical Optimization OPUS4-4750 Wissenschaftlicher Artikel Poss, Michael; Raack, Christian Affine recourse for the robust network design problem: Between static and dynamic routing 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. 2013 18 Networks - Special Issue: INOC 2011 Conference, June 13–16, 2011, Hamburg, Germany 61 2 180 198 10.1002/net.21482 Mathematical Optimization OPUS4-1862 misc Grötschel, Martin; Raack, Christian; Werner, Axel Towards optimizing the deployment of optical access networks 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. 2013 urn:nbn:de:0297-zib-18627 10.1007/s13675-013-0016-x Mathematical Optimization OPUS4-3293 Wissenschaftlicher Artikel Dash, Sanjeeb; Günlük, Oktay; Raack, Christian A note on the MIR closure and basic relaxations of polyhedra 2011 1 Optimization Research Letters 39 3 198 199 Mathematical Optimization OPUS4-3294 Konferenzveröffentlichung Koster, Arie M.C.A.; Kutschka, Manuel; Raack, Christian Towards Robust Network Design using Integer Linear Programming Techniques Paris, France Next Generation Internet 2010 Proceedings of the NGI 2010, Paris, France Mathematical Optimization OPUS4-4347 Wissenschaftlicher Artikel Grötschel, Martin; Raack, Christian; Werner, Axel Towards optimizing the deployment of optical access networks Springer 2013 36 EURO Journal on Computational Optimization 2 17 53 10.1007/s13675-013-0016-x Mathematical Optimization OPUS4-4348 Wissenschaftlicher Artikel Raack, Christian; Raymond, Annie; Schlechte, Thomas; Werner, Axel Standings in sports competitions using integer programming De Gruyter 2013 7 Journal of Quantitative Analysis in Sports 10 2 131 137 10.1515/jqas-2013-0111 Mathematical Optimization OPUS4-4349 Wissenschaftlicher Artikel Betker, Andreas; Kosiankowski, Dirk; Lange, Christoph; Pfeuffer, Frank; Raack, Christian; Werner, Axel Helber, Stefan; Breitner, Michael; Rösch, Daniel; Schön, Cornelia; Graf von der Schulenburg, Johann-Matthias; Sibbertsen, Philipp; Steinbach, Marc; Weber, Stefan; Wolter, Anja Energy efficiency in extensive IP-over-WDM networks with protection Springer 2014 6 Operations Research Proceedings 2012 93 99 10.1007/978-3-319-00795-3_14 Mathematical Optimization OPUS4-4354 Dissertation Raack, Christian Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty 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. 2012 urn:nbn:de:kobv:83-opus-36167 Mathematical Optimization OPUS4-1806 misc Raack, Christian; Raymond, Annie; Werner, Axel; Schlechte, Thomas Integer Programming and Sports Rankings 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. 2013 urn:nbn:de:0297-zib-18068 10.1515/jqas-2013-0111 Mathematical Optimization