We study a Resilient Shortest Path Problem (RSPP) arising in the literature for the design of communication networks with reliability guarantees. A graph is given, in which every edge has a cost and a probability of availability, and in which two vertices are marked as source and destination. The aim of our RSPP is to find a subgraph of minimum cost, containing a set of paths from the source to the destination vertices, such that the probability that at least one path is available is higher than a given threshold. We explore its theoretical properties and show that, despite a few interesting special cases can be solved in polynomial time, it is in general NP-hard. Computing the probability of availability of a given subgraph is already NP-hard; we therefore introduce an integer relaxation that simplifies the computation of such probability, and we design a corresponding exact algorithm. We present computational results, finding that our algorithm can handle graphs with up to 20 vertices within minutes of computing time.

Mathematical Formulations for the Optimal Design of Resilient Shortest Paths / M. Casazza, A. Ceselli, A. Taverna (AIRO SPRINGER SERIES). - In: New Trends in Emerging Complex Real Life Problems / [a cura di] P. Daniele, L. Scrimali. - [s.l] : Springer, 2018. - ISBN 9783030004729. - pp. 121-129 (( convegno ODS tenutosi a Taormina nel 2018 [10.1007/978-3-030-00473-6_14].

### Mathematical Formulations for the Optimal Design of Resilient Shortest Paths

#### Abstract

We study a Resilient Shortest Path Problem (RSPP) arising in the literature for the design of communication networks with reliability guarantees. A graph is given, in which every edge has a cost and a probability of availability, and in which two vertices are marked as source and destination. The aim of our RSPP is to find a subgraph of minimum cost, containing a set of paths from the source to the destination vertices, such that the probability that at least one path is available is higher than a given threshold. We explore its theoretical properties and show that, despite a few interesting special cases can be solved in polynomial time, it is in general NP-hard. Computing the probability of availability of a given subgraph is already NP-hard; we therefore introduce an integer relaxation that simplifies the computation of such probability, and we design a corresponding exact algorithm. We present computational results, finding that our algorithm can handle graphs with up to 20 vertices within minutes of computing time.
##### Scheda breve Scheda completa Scheda completa (DC)
Network reliability; Shortest path problem; Branch and price; Column generation
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
2018
Book Part (author)
File in questo prodotto:
File
Resilient Shortest Path.pdf

accesso riservato

Descrizione: Articolo principale
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 134.31 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2434/640885`