|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||Abstract:||
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.
|Library ID:||AC07813475||Organisation:||E186 - Institut für Computergraphik und Algorithmen||Publication Type:||Thesis
|Appears in Collections:||Thesis|
Show full item record
Files in this item:
|On solving constrained tree problems and an adaptive layers framework.pdf||1.22 MB||Adobe PDF|
checked on Feb 18, 2021
checked on Feb 18, 2021
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.