(419e) Network Design with Uncertain Edge Failures: Two-Stage Robust Optimization for Single-Commodity Networks

The design of networks has applications in a wide variety of fields, and the tools of process systems engineering are well suited for this task. For example, mixed-integer linear optimization techniques have been shown to be a suitable framework for generating networks with specific requirements regarding their properties [1,2]. In other cases, such as in single-commodity networks, a general graph of nodes is known a priori, and a final network of edges must be built between these nodes such that the demands at each location are met [3]. For this latter problem, uncertainty may arise when constructed edges randomly fail after being built. Generally known as survivable or resilient network design [4,5], optimization that takes into account the possibility of edge failures can prevent disastrous logistical issues which can arise through purely deterministic designs.

The deterministic single-commodity network design problem involves the minimization of the total cost of the network, including the investment cost and operational costs. The capacities of each edge of the network, as well as the actual flows along each edge, must be determined and their associated costs calculated. When edges can fail, the uncertain problem naturally separates into two stages. The initial capacities of each edge must be chosen in the first stage, while the flows may only be determined in the second stage, after one has observed which edges have failed. We formalize this problem as a two-stage robust optimization problem [6,7,8] using an uncertainty set of binary random variables that indicate whether an edge has failed. The two-stage robust optimization formulation is solved using a suitably modified column and constraint generation algorithm [9] in order to determine the minimum cost network that remains feasible for a given number of possible simultaneous edge failures.

The two-stage robust optimization formulation and column and constraint generation algorithm for the network design problem under demand uncertainty is presented and used to solve various problems adapted for our robust optimization context from the Survivable Network Design Library [10]. A preprocessing algorithm is presented which analyzes the initial graph and simplifies it when possible to reduce problem complexity. Results are obtained for various levels of robustness; that is, optimal network topologies are determined for different allowable extents of possible edge failures. The required computational effort for optimization with our modified column and constraint generation algorithm is also discussed.

[1] Gounaris, C.E.; Rajendran, K.; Kevrekidis, I.G.; Floudas, C. A. Generation of networks with prescribed degree-dependent clustering. Optimization Letters, 2011, 5 (3), 435-451.

[2] Gounaris, C.E.; Rajendran, K; Kevrekidis, I.G.; Floudas, C.A. Designing Networks: A Mixed-Integer Linear Optimization Approach. Networks, 2016, 68 (6), 283-301.

[3] Cacchiani, V.; Jünger, M.; Liers, F.; Lodi, A.; Schmidt, D. R. Single-commodity robust network design with finite and Hose demand sets. Math. Program. Ser. B, 2016, 157, 297-342.

[4] Tomaszewski, A.; Pióro, M.; Żotkiewicz, M. On the complexity of resilient network design. Networks, 2010, 55, 108–118.

[5] Orlowski, S; Pióro, M. Complexity of column generation in network design with path-based survivability mechanisms. Networks, 2012, 59, 132–147.

[6] Ben-Tal A.; El Ghaoui L.; Nemirovski A. Robust optimization. Princeton University Press, 2009.

[7] Lappas, N.H.; Gounaris, C.E. Multi-Stage Adjustable Robust Optimization for Process Scheduling Under Uncertainty. AIChE Journal, 2016, 62 (5), 1646-1667.

[8] Gounaris, C.E. Advances in Robust Optimization and Opportunities for Process Operations. In: Proceedings of the Foundations of Computer-Aided Process Operations/Chemical Process Control (FOCAPO 2017/CPC IX), C.T. Maravelias, L. Megan, J. Wassick and E.B. Ydstie (Eds.), 2017, Paper ID IF110.

[9] Zeng, B.; Zhao, L.; Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters, 2013, 41, 457-461.

[10] Orlowski S.; Wessäly R.; Pióro M.; Tomaszewski A. SNDlib 1.0—survivable network design library. Networks, 2010, 55(3), 276-286.