Title: On solving constrained tree problems and an adaptive layers framework
Language: English
Authors: Ruthmair, Mario
Qualification level: Doctoral
Keywords: kombinatorische Optimierung; Netzwerkdesign; beschränkte Baumprobleme; Metaheuristiken; ganzzahlige lineare Programmierung
combinatorial optimization; network design; constrained tree problems; metaheuristics; integer linear programming
Advisor: Raidl, Günther R. 
Assisting Advisor: Pferschy, Ulrich
Issue Date: 2012
Number of Pages: 173
Qualification level: Doctoral
In this thesis we consider selected combinatorial optimization problems arising in the field of network design. In many of these problems there is a central server sending out information to a set of recipients. A common objective is then to choose connections in the network minimizing the total costs. Besides this, current applications, e.g. in multimedia, usually ask for additional quality-of-service constraints, e.g. limiting the communication delay between the central server and the clients. In general, these problems can be modeled on a graph and in many cases an optimal solution corresponds to a rooted tree with minimum costs satisfying all the given constraints. The most relevant of these optimization problems are NP-hard and thus - provided that P is not equal to NP - it is usually not possible to obtain proven optimal solutions for medium- to large-sized problem instances. Therefore, heuristic approaches yielding high quality but in general sub-optimal solutions are of high practical interest. We present sophisticated preprocessing methods to reduce the problem size and new heuristic as well as exact state-of-the-art solution approaches for several of these optimization problems. The proposed heuristics include several construction and improvement methods embedded in various metaheuristics. Small- to medium-sized problem instances are tackled with exact algorithms, mostly concentrating on mathematical programming methods. We compare different modeling approaches, among them a transformation to a layered graph. Finally, we introduce a generally-applicable iterative adaptive layers framework which tries to partly overcome major computational issues of layered graph approaches.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-54456
Library ID: AC07813475
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


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