Exact and memetic algorithms for two network design problems

Abstract

This thesis focuses on two NP-hard network design problems:<br />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.<br />when designing a fiber optic or a district heating network.<br />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.<br />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.<br />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.<br />

Abstract nicht verfügbar