66 research outputs found
Employing Mixed-Integer Rounding in Telecommunication Network Design
No full textIn 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
Netzwerkdesign - Mehrgüterflussformulierungen, Schnittebenen und Bedarfsunsicherheit
No full textIn 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
Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty
No full textIn 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
Affine recourse for the robust network design problem: Between static and dynamic routing
No full textAffinely-Adjustable Robust Counterparts are used to 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. 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 strongly) dominated demand vectors are not necessarily supported by affine solutions. © 2011 Springer-Verlag.SCOPUS: cp.kinfo:eu-repo/semantics/publishe
The MCF-separator – detecting and exploiting multi-commodity flows in MIPs
No full textGiven a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multicommodity 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 branchand-cut libraries of Scip and Cplex. We make use of the complemented mixed integer rounding framework (c-MIR) 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
- …
