Mathematical Formulations for the Optimal Design of Resilient Shortest Paths

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.