On solving constrained tree problems and an adaptive layers framework / Mario Ruthmair
VerfasserRuthmair, Mario
Begutachter / BegutachterinRaidl, Günther R. ; Pferschy, Ulrich
UmfangXII, 173 S. : graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2012
Zsfassung in dt. Sprache
Bibl. ReferenzOeBB
Schlagwörter (DE)kombinatorische Optimierung / Netzwerkdesign / beschränkte Baumprobleme / Metaheuristiken / ganzzahlige lineare Programmierung
Schlagwörter (EN)combinatorial optimization / network design / constrained tree problems / metaheuristics / integer linear programming
Schlagwörter (GND)Netzwerk / Design / Kombinatorische Optimierung / Metaheuristik / Spannender Baum / Steiner-Problem
URNurn:nbn:at:at-ubtuw:1-54456 Persistent Identifier (URN)
 Das Werk ist frei verfügbar
On solving constrained tree problems and an adaptive layers framework [1.19 mb]
Zusammenfassung (Englisch)

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.