Musil, N. (2008). Design eines sicherheits-, zeit- und kostenkritischen Kommunikationsnetzwerkes mittels Lagrange Relaxierung und Spaltengenerierung [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-22850
Lagrangean Relaxation; Column Generation; network design; Constrained Shortest Path Problem
en
Abstract:
Das effiziente Senden von Daten über Netzwerke gewinnt zunehmend mehr an Relevanz - von Internettelefonie bis hin zu Event-basierten Nachrichtensystemen. Die konkrete Aufgabenstellung entstand aus dem Industrieprojekt SWIS im Bereich der sicherheitskritischen Kommunikation bei der Flughafensicherung. In dieser Arbeit wird das Design eines Netzwerkes, in welchem mehrere Nachrichten gleichzeitig übermittelt werden sollen, hinsichtlich Erstellungs- und Übertragungskosten optimiert. Die Verbindungen sind durch Kapazitäten beschränkt, die Nachrichten müssen Zeitvorgaben hinsichtlich der Übermittlungsdauer und Vorgaben bezüglich des Übertragungsprotokolls einhalten.<br />In dieser Arbeit werden verschiedene algorithmische Ansätze zur Lösung dieses NP-schweren Problems erörtert. Ein Verfahren ganzzahliger linearer Programmierung basierend auf einer Mehrgüterflussformulierung ermöglicht das exakte Lösen kleiner Probleminstanzen.<br />Um das Problem zu vereinfachen werden bei der Lagrange Relaxierung schwierige Nebenbedingungen als Lagrange-Multiplikatoren in die Zielfunktion aufgenommen. Dadurch ergibt sich für jeden Transport ein unabhängiges Teilproblem. Aufgrund dessen werden durch iterative Verfahren die Koeffizienten der Lagrange-Multiplikatoren angepasst und somit untere Schranken für das Ausgangsproblem gefunden. Durch Heuristiken wird versucht daraus gültige Lösungen zu erzeugen.<br />Basierend auf einer alternativen Problemformulierung, bei welcher jedem möglichen Pfad eine Variable entspricht, wird das Problem durch Spaltengenerierung gelöst. Ausgehend von einer gültigen Lösung werden in einem iterativen Prozess nur jene Variablen hinzugefügt, welche die Lösung weiter verbessern können. Die Bestimmung dieser Variablen erfolgt aufgrund der Lösung des selben Subproblems wie bei der Lagrange Relaxierung.<br />Mit den vorgestellten Verfahren können kleine Instanzen in wenigen Minuten beweisbar optimal gelöst werden, für größere Instanzen können gute heuristische Lösungen gefunden werden. Die scharfen unteren Schranken der Lagrange Relaxierung ermöglichen zuverlässige Aussagen über die Qualität heuristischer Lösungen. Umfangreiche experimentelle Tests belegen die Vor- und Nachteile der vorgestellten Verfahren.<br />
de
Efficient network routing is becoming more and more important - examples are internet telephony or event-based message systems. The particular problem emerged from the industry cooperation SWIS in the context safety-critical communication of air traffic management. In this thesis the design of a network is optimized for design and protocol costs. The goal is to find a minimum cost network enabling the simultaneous routing of multiple messages. Capacity constraints for each edge, delay constraints for individual messages, as well as a global delay, and security constraints make the optimization difficult.<br />In this thesis several algorithmic approaches for solving this NP-hard problem are discussed. An Integer Linear Programming based approach using a multi-commodity flow formulation enables to solve small problem instances to provable optimality.<br />To simplify the problem constraints are brought into the objective function by attaching Lagrangean multipliers to them. This approach is called Lagrangean relaxation. This yields independent subproblems for each transport. In an iterative process the coefficients of the Lagrange multipliers are systematically adapted and lower bounds for the original problem are obtained. Heuristics can be used to derive valid solutions.<br />Based on an alternative formulation, which introduces a variable for each possible path, the problem is solved by Column Generation. Starting from a valid solution, further improving variables are iteratively added. These variables can be found by solving the same subproblem as for Lagrangean relaxation.<br />By the presented algorithms small instances can be solved within a few minutes to optimality. For larger instances good heuristic solutions can be found. Tight lower bounds obtained by Lagrangean relaxation enable to measure the quality of heuristic solutions. Based on extensive experimental tests, pros and cons of each approach are discussed in this thesis.
en
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers Zsfassung in engl. Sprache