We study a Resilient Path Selection Problem (RPSP) arising in the design of communication networks with reliability guarantees. A graph is given, in which every arc has a cost and a probability of failure, and in which two nodes are marked as source and destination. The aim of our RPSP is to find a subgraph of minimum cost, containing a set of paths from the source to the destination nodes, such that the probability that all paths fail simultaneously is lower 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. In fact, we prove that even deciding if a given subgraph has a probability of failure not exceeding a given threshold is already NP-Complete. We therefore introduce an integer relaxation that simplifies the computation of such probability, and we design an exact algorithm for the full RPSP exploiting this relaxation and other ad hoc procedures. We present computational results, highlighting that our exact algorithms can handle graphs with up to 30 nodes within minutes of computing time, consistently producing proven optimal solutions. Moreover, we show that our algorithms can be used also as heuristics, outperforming path protection schemes from the literature also on much larger networks.

Optimization algorithms for resilient path selection in networks / M. Casazza, A. Ceselli. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 128(2021 Apr). [10.1016/j.cor.2020.105191]

Optimization algorithms for resilient path selection in networks

M. Casazza
Primo
;
A. Ceselli
Ultimo
2021

Abstract

We study a Resilient Path Selection Problem (RPSP) arising in the design of communication networks with reliability guarantees. A graph is given, in which every arc has a cost and a probability of failure, and in which two nodes are marked as source and destination. The aim of our RPSP is to find a subgraph of minimum cost, containing a set of paths from the source to the destination nodes, such that the probability that all paths fail simultaneously is lower 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. In fact, we prove that even deciding if a given subgraph has a probability of failure not exceeding a given threshold is already NP-Complete. We therefore introduce an integer relaxation that simplifies the computation of such probability, and we design an exact algorithm for the full RPSP exploiting this relaxation and other ad hoc procedures. We present computational results, highlighting that our exact algorithms can handle graphs with up to 30 nodes within minutes of computing time, consistently producing proven optimal solutions. Moreover, we show that our algorithms can be used also as heuristics, outperforming path protection schemes from the literature also on much larger networks.
Branch and price; Column generation; Failure probability; Network reliability; Path selection;
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
apr-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
Resilient_Shortest_Path.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 476.23 kB
Formato Adobe PDF
476.23 kB Adobe PDF Visualizza/Apri
1-s2.0-S0305054820303087-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 518 kB
Formato Adobe PDF
518 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/807791
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact