Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/33069
Title: | The minimum cost network upgrade problem with maximum robustness to multiple node failures |
Author: | Barbosa, Fábio Agra, Agostinho Sousa, Amaro de |
Keywords: | Robust network design Critical node detection Mixed integer linear programming Pareto frontier Telecommunications |
Issue Date: | Dec-2021 |
Publisher: | Elsevier |
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. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/33069 |
DOI: | 10.1016/j.cor.2021.105453 |
ISSN: | 0305-0548 |
Publisher Version: | https://www.sciencedirect.com/science/article/pii/S0305054821002057 |
Appears in Collections: | CIDMA - Artigos DETI - Artigos DMat - Artigos IT - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
The minimum cost network upgrade problem with maximum robustness.pdf | 1.92 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.