Premium
A computational investigation of heuristic algorithms for 2‐edge‐connectivity augmentation
Author(s) -
BangJensen Jørgen,
Chiarandini Marco,
Morling Peter
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20316
Subject(s) - heuristics , subgradient method , mathematical optimization , integer programming , algorithm , heuristic , mathematics , iterated function , computer science , graph , enhanced data rates for gsm evolution , mixed graph , theoretical computer science , line graph , artificial intelligence , voltage graph , mathematical analysis
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 ′ ⊆ V × V with nonnegative 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. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010