A Computational Investigation of Heuristic Algorithms for 2-Edge-Connectivity Augmentation - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Faculty of Science, SDU^{2} Central Administration, SDU^{3} IT-service, Rektorat, Central Administration, SDU^{4} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{5} Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{6} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{7} Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{8} Central Administration, SDU

DOI:

DOI: 10.1002/net.20316

Abstract:

We consider the 2-edge-connectivity augmentation problem: given a graph $S=(V,E)$ which is not 2-edge-connected and a set of new edges $E' \subseteq V \times V$ with non-negative weights, find a minimum cost subset $X$ of $E'$ such that adding the edges of $X$ to $S$ results in a 2-edge-connected graph. A practical application is the extension of an existing telecommunication network to become robust against single link failures. We compare, experimentally, different algorithms for solving general and large-scale instances. This includes exact methods based on mathematical programming, simple construction heuristics and metaheuristics. As part of the design of heuristics, we consider different neighborhood structures for local search, among which is a very large scale neighborhood. In all cases, we exploit approaches through the graph formulation as well as through an equivalent set covering formulation. The results indicate that exact solutions by means of a basic integer programming model can be obtained in reasonably short time even on networks with 800 vertices and around 287,000 edges. Alternatively, an advanced heuristic algorithm based on subgradient optimization and iterated greedy often finds the optimal solution and is very fast. All previous benchmark instances are easily solved to optimality and new, larger instances are introduced and studied.

Type:

Journal article

Language:

English

Published in:

Networks (new York), 2010, Vol 55, Issue 4, p. 299-325

Keywords:

Edge-Connectivity, Augmentation, Survivable Networks, Local Search, Heuristics, Set Covering, Very Large Scale Neighborhood