The minimum cost network upgrade problem with maximum robustness to multiple node failures

Abstract The design of networks which are robust to multiple failures is gaining increasing attention in areas such as telecommunications. In this paper, we consider the problem of upgrading an existent network in order to enhance its robustness to events involving multiple node failures. This problem is modeled as a bi-objective mixed linear integer formulation considering both the minimization of the cost of the added edges and the maximization of the robustness of the resulting upgraded network. As the robustness metric of the network, we consider the value of the Critical Node Detection (CND) problem variant which provides the minimum pairwise connectivity between all node pairs when a set of c critical nodes are removed from the network. We present a general iterative framework to obtain the complete Pareto frontier that alternates between the minimum cost edge selection problem and the CND problem. Two different approaches based on a cover model are introduced for the edge selection problem. Computational results conducted on different network topologies show that the proposed methodology based on the cover model is effective in computing Pareto solutions for graphs with up to 100 nodes, which includes four commonly used telecommunication networks.