Ruthmair, M. (2012). On solving constrained tree problems and an adaptive layers framework [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-54456
combinatorial optimization; network design; constrained tree problems; metaheuristics; integer linear programming
en
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.