Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3291
Main Title: Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty
Translated Title: Netzwerkdesign - Mehrgüterflussformulierungen, Schnittebenen und Bedarfsunsicherheit
Author(s): Raack, Christian
Advisor(s): Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: In der vorliegenden Dissertation entwickeln wir spezielle Methoden der mathematischen Optimierung zur kostenoptimalen Dimensionierung von Netzwerken. Die betrachteten Probleme entstehen z.B. bei der strategischen Planung von Telekommunikationsnetzen, aber auch in der Logistik. Ein wesentlicher Aspekt der Arbeit ist der Einsatz von Schnittebenen zur Steigerung der Effizienz von Lösungsansätzen, die auf Mehrgüterflussformulierungen (engl. Abk.: MCF) basieren. Insbesondere unterstreichen wir die theoretische und numerische Bedeutung von Ungleichungen, die auf Netzwerkschnitten definiert sind. Zunächst zeigen wir, dass Techniken, die ursprünglich zur Lösung von Netzwerkdesignproblemen entwickelt wurden, erfolgreich in allgemeine Löser für Gemischt Ganzzahlige Programme (engl. Abk.: MIP) eingebettet werden können. Unser Ansatz beruht auf einer automatischen Erkennung von Netzwerkstrukturen in MIPs und der anschließenden strukturellen Aggregation von Modellungleichungen. Eingebettet in vorhandene Schnittebenenprozeduren liefert dieser Ansatz starke Ungleichungen, welche die erkannte Netzwerkstruktur widerspiegeln. Ausführliche numerische Tests belegen eine durchschnittliche Beschleunigung allgemeiner MIP-Löser um den Faktor 2 bei reinen Netzwerkdesignproblemen. Für allgemeine MIPs kann die Lösungszeit um etwa 18\% reduziert werden, wenn ein konsistentes Netzwerk erkannt wird, was in etwa einem Zehntel der Instanzen der Fall ist. Im zweiten Teil dieser Dissertation studieren wir Konzepte und Modelle für das Design von Netzen unter Berücksichtigung der Unsicherheit bei der Schätzung des Verkehrsaufkommens. Dabei verbessern und vergleichen wir Strategien, die polyedrische Mengen von Bedarfsszenarien annehmen. Netzwerkdesign wird eingebettet in die allgemeine Theorie zweistufiger robuster Optimierung. Die Kapazitäten in der ersten Stufe werden für alle Szenarien fixiert, der Verkehrsfluss in der zweiten Stufe jedoch hängt von den realisierten Bedarfen ab (recourse action). Mit Hilfe sogenannter cut-set-Polyeder und zugehöriger Liftingtheoreme entwickeln wir einerseits einige Klassen facetten-definierender Ungleichungen, die zu Netzwerkschnitten gehören. Diese werden in entsprechenden Schnittebenenverfahren eingesetzt, wobei wir eine Beschleunigung unterschiedlicher Lösungsverfahren um mehr als den Faktor 2 erreichen. Andererseits analysieren wir die Eigenschaften eines neuen affinen Modells (affine routing), den Verkehrsfluss bei fester Kapazität in Abhängigkeit vom realisierten Verkehrsbedarf zu organisieren. Wir zeigen theoretisch und numerisch, dass dieses Modell Vorteile der bekannten statischen und dynamischen Modelle vereint. Um die Robustheit der mit unseren Algorithmen berechneten Lösungen zu evaluieren, benutzen wir Messungen des Datenaufkommens und der Verkehrsdynamik in realen Telekommunikationsnetzen, unter anderem Daten aus dem deutschen sowie dem europäischen Forschungsnetz.
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.
URI: urn:nbn:de:kobv:83-opus-36167
http://depositonce.tu-berlin.de/handle/11303/3588
http://dx.doi.org/10.14279/depositonce-3291
Exam Date: 26-Jun-2012
Issue Date: 27-Jul-2012
Date Available: 27-Jul-2012
DDC Class: 510 Mathematik
Subject(s): Ganzzahlige Programmierung
Kombinatorische Optimierung
Netzwerkdesign
Robustheit
Schnittebenen
Combinatorial optimization
Cutting planes
Integer programming
Network design
Robustness
Creative Commons License: https://creativecommons.org/licenses/by-sa/2.0/de
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_7.pdf2.36 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.