Designing networks with resiliency to edge failures using two-stage robust optimization

Logan R. Matthews, Chrysanthos E. Gounaris and Ioannis G. Kevrekidis

European Journal of Operational Research, 2019, vol. 279, issue 3, 704-720

Abstract: We study the design of resilient single-commodity flow networks that can remain robust against multiple concurrent edge failures. We model these failures as binary random variables, allowing us to formally formulate the network design problem as a two-stage robust optimization problem. With an objective of minimizing the overall cost of building and operating the network, the capacities of the edges are decided in the first stage, while the optimal flows are determined in the second stage once the uncertainty has been realized. We first examine the standard affine decision rules approach and show that it is not a viable approach when two or more edges are allowed to fail at the same time. We then propose a column and constraint generation algorithm that we tailor to this application. Since the problem does not satisfy the relatively complete recourse assumption, we employ an oracle with two subproblems: one to determine edge failure scenarios that render the required demand satisfaction infeasible, and if no such scenario exists, a second one to determine the flow rerouting plan of highest cost. Our column and constraint generation algorithm is applied to networks adapted from the Survivable Network Design Library. For each instance, we determine sequences of fully adaptive, robust optimal solutions for various levels of resiliency, identifying also the maximum number of concurrent edge failures that can be sustained by these networks. Finally, we demonstrate how our algorithm can be applied to a defender versus attacker context, via the use of a decision-dependent uncertainty set.

Keywords: Networks; Network design; Network resiliency; Two-stage robust optimization; Column and constraint generation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719304965
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:279:y:2019:i:3:p:704-720

DOI: 10.1016/j.ejor.2019.06.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().