A cutting plane algorithm for computing k-edge survivability of a network

Given an undirected network and a set of traffic demands between pairs of nodes, k-edge survivability of a given network is defined as the percentage of the total traffic surviving the failure of k edges in the worst case. The problem of computing k-edge survivability is known to be NP-hard and no algorithm other than simple enumeration has been found. In this paper, we develop an efficient algorithm for generating lower and upper bounds of k-edge survivability of a network. We present a preprocessing procedure of reducing the problem size, a heuristic of providing a lower bound, and a cutting plane algorithm of obtaining an upper bound. Computational results for evaluating the performance of the proposed algorithm are also presented. (C) 2003 Elsevier B.V. All rights reserved.