DC FieldValueLanguage
dc.contributor.advisorRaidl, Günther-
dc.contributor.authorMusil, Nina-
dc.date.accessioned2020-06-30T17:57:59Z-
dc.date.issued2008-
dc.date.submitted2008-12-
dc.identifier.urihttps://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-22850-
dc.identifier.urihttp://hdl.handle.net/20.500.12708/13403-
dc.descriptionAbweichender Titel laut Übersetzung der Verfasserin/des Verfassers-
dc.descriptionZsfassung in engl. Sprache-
dc.description.abstractDas 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
dc.description.abstractEfficient 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
dc.formatX, 85 Bl.-
dc.languageDeutsch-
dc.language.isode-
dc.subjectLagrange Relaxierungde
dc.subjectSpaltengenerierungde
dc.subjectNetzwerkdesignde
dc.subjectLagrangean Relaxationen
dc.subjectColumn Generationen
dc.subjectnetwork designen
dc.subjectConstrained Shortest Path Problemen
dc.titleDesign eines sicherheits-, zeit- und kostenkritischen Kommunikationsnetzwerkes mittels Lagrange Relaxierung und Spaltengenerierungde
dc.title.alternativeDesign of a safety-, time- and cost-critical communication network by Lagrangean Relaxation and Column Generationen
dc.typeThesisen
dc.typeHochschulschriftde
dc.contributor.assistantChwatal, Andreas-
tuw.publication.orgunitE186 - Institut für Computergraphik und Algorithmen-
dc.type.qualificationlevelDiploma-
dc.identifier.libraryidAC05039457-
dc.description.numberOfPages85-
dc.identifier.urnurn:nbn:at:at-ubtuw:1-22850-
dc.thesistypeDiplomarbeitde
dc.thesistypeDiploma Thesisen
item.languageiso639-1de-
item.openairetypeThesis-
item.openairetypeHochschulschrift-
item.fulltextwith Fulltext-
item.cerifentitytypePublications-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.grantfulltextopen-
Appears in Collections:Thesis

Files in this item:

Show simple item record

Page view(s)

18
checked on Apr 15, 2021

Download(s)

60
checked on Apr 15, 2021

Google ScholarTM

Check


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