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.

Introduction

Networks are prevalent in a vast variety of contexts, and it comes as no surprise that their optimal design has arisen as a prime research question that has been contemplated extensively in the open literature. Whether it be a supply chain (Snyder, Scaparra, Daskin, & Church, 2006), telecommunications (Orlowski, Wessäly, Pióro, & Tomaszewski, 2010), or transportation (Alderson, Brown, & Carlyle, 2015; Zhang, Lawphongpanich, & Yin, 2009) application, to name but a few, obtaining optimal designs for such networks is a very important task. Network design problems come in many flavors, such as problems involving a single versus multiple commodities, problems in which the demands are to be met exactly versus allowing for demand shortfall and pursuing some sort of penalization scheme, as well as problems in which the network is to be designed from scratch versus the case where a pre-existing network is to be expanded. The nominal case for a network design problem is often straightforward: decisions must be made on the capacities of and/or flows through each edge of the network such that demand is satisfied at each node. Designing nominal networks in all of the above settings can typically be achieved via solving some monolithic, often mixed-integer linear, optimization formulation that utilizes flow balance constraints at its core. Mixed-integer linear optimization has also been shown to be an effective tool to control the levels of network connectivity, spread and assortativity by explicitly imposing constraints on collective properties of the network (Gounaris, Rajendran, Kevrekidis, & Floudas, 2011; 2016).