On Progressive Network Recovery from Massive Failures under Uncertainty

Diman Zad Tootaghaj, Novella Bartolini, Hana Khamfroush, Thomas La Porta

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Network recovery after large-scale failures has tremendous cost implications. While numerous approaches have been proposed to restore critical services after large-scale failures, they mostly assume having full knowledge of failure location, which cannot be achieved in real failure scenarios. Making restoration decisions under uncertainty is often further complicated in a large-scale failure. This paper addresses progressive network recovery under the uncertain knowledge of damages. We formulate the problem as a mixed integer linear programming and show that it is NP-hard. We propose an iterative stochastic recovery algorithm (ISR) to recover the network in a progressive manner to satisfy the critical services. At each optimization step, we make a decision to repair a part of the network and gather more information iteratively, until critical services are completely restored. We propose three different approaches: 1) an iterative shortest path algorithm; 2) an approximate branch and bound (ISR-BB); and 3) an iterative multicommodity LP relaxation (ISR-MULT). Further, we compared our approach with the state-of-the-art centrality-based damage assessment and recovery (CeDAR) and iterative split and prune (ISP) algorithms. Our results show that ISR-BB and ISR-MULT outperform the state-of-the-art ISP and CeDAR algorithms while we can configure our choice of tradeoff between the execution time, the number of repairs (cost), and the demand loss. We show that our recovery algorithm, on average, can reduce the total number of repairs by a factor of about 3 with respect to ISP, while satisfying all critical demands.

Original languageEnglish
Article number8527547
Pages (from-to)113-126
Number of pages14
JournalIEEE Transactions on Network and Service Management
Issue number1
StatePublished - Mar 2019

Bibliographical note

Publisher Copyright:
© 2018 IEEE.


  • Network recovery
  • massive disruption
  • stochastic optimization
  • uncertainty

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On Progressive Network Recovery from Massive Failures under Uncertainty'. Together they form a unique fingerprint.

Cite this