Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 156, Issue 3, Pages 579-589Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0377-2217(03)00135-8
Keywords
integer programming; network survivability; polyhedral analysis; cutting plane algorithm
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available