Title: Exact and memetic algorithms for two network design problems
Language: English
Authors: Ljubić, Ivana
Qualification level: Doctoral
Advisor: Mutzel, Petra 
Assisting Advisor: Pferschy, Ulrich
Issue Date: 2004
Number of Pages: 177
Qualification level: Doctoral
This thesis focuses on two NP-hard network design problems:
the first one, vertex biconnectivity augmentation (V2AUG), appears in the design of survivable communication or electricity networks. In this problem we search for the set of connections of minimal total cost which, when added to the existing network, makes it survivable against failures of any single node. The second problem, the prize-collecting Steiner tree problem (PCST), describes a natural trade-off between maximizing the sum of profits over all selected customers and minimizing the implementation costs, e.g.
when designing a fiber optic or a district heating network.
We provide exact algorithms based on the branch-and-cut technique that can solve given network design problems of respectable size to provable optimality. For fairly large instances, we propose heuristic tools that obtain suboptimal, high quality solutions of practical relevance. Fractional bounds obtained by means of exact methods are therefore used as a measure of quality of obtained heuristic solution.
As a heuristic tool, we choose memetic algorithms (MAs), a symbiosis of evolutionary and neighborhood search algorithms. Our memetic algorithms comprise new representation techniques, search operators,constraint handling techniques and local-improvement strategies. Our exact algorithms are based on the state-of-the-art in polyhedral combinatorics. They rely on sophisticated separation algorithms or advanced column generation methods.
In this thesis, we also investigate some possibilities of combining promising variants of exact algorithms and MAs, e.g. incorporating exact algorithms that solve some special cases within MAs, or guiding column generation using MA results. In extensive computational studies our exact and memetic algorithms show their superiority compared to the previously published results. For many of V2AUG and PCST instances, we are the first to find provably optimalsolutions.

Abstract nicht verfügbar
Keywords: Kombinatorische Optimierung; NP-hartes Problem; Netzwerk; Algorithmus; Steiner-Problem
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-13664
Library ID: AC04351739
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 Jun 5, 2021


checked on Jun 5, 2021

Google ScholarTM


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