Abstract
This paper addresses progressive network recovery under uncertain knowledge of damages. We formulate the problem as a mixed integer linear programming (MILP), 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. Three different algorithms are used to find a feasible set and determine which node to repair, namely, 1) an iterative shortest path algorithm (ISR-SRT), 2) an approximate branch and bound (ISR-BB) and 3) an iterative multi-commodity LP relaxation (ISR-MULT). Further, we have modified the state-of-the-Art iterative split and prune (ISP) algorithm to incorporate the uncertain failures. Our results show that ISR-BB and ISR- MULT outperform the state-of-the-Art 'progressive ISP' algorithm while we can configure our choice of trade-off between the execution time, 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 language | English |
---|---|
Title of host publication | 2017 IFIP Networking Conference, IFIP Networking 2017 and Workshops |
Pages | 1-9 |
Number of pages | 9 |
ISBN (Electronic) | 9783901882944 |
DOIs | |
State | Published - Jul 2 2017 |
Event | 2017 IFIP Networking Conference and Workshops, IFIP Networking 2017 - Stockholm, Sweden Duration: Jun 12 2017 → Jun 16 2017 |
Publication series
Name | 2017 IFIP Networking Conference, IFIP Networking 2017 and Workshops |
---|---|
Volume | 2018-January |
Conference
Conference | 2017 IFIP Networking Conference and Workshops, IFIP Networking 2017 |
---|---|
Country/Territory | Sweden |
City | Stockholm |
Period | 6/12/17 → 6/16/17 |
Bibliographical note
Publisher Copyright:© 2017 IFIP.
ASJC Scopus subject areas
- Computer Networks and Communications