科研之友
微信
新浪微博
Facebook
分享链接
摘要
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' subset of V x 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-7
