(419e) Network Design with Uncertain Edge Failures: Two-Stage Robust Optimization for Single-Commodity Networks
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  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 . 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.
 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.
 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.
 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.
 Tomaszewski, A.; PiÃ³ro, M.; Å»otkiewicz, M. On the complexity of resilient network design. Networks, 2010, 55, 108â118.
 Orlowski, S; PiÃ³ro, M. Complexity of column generation in network design with path-based survivability mechanisms. Networks, 2012, 59, 132â147.
 Ben-Tal A.; El Ghaoui L.; Nemirovski A. Robust optimization. Princeton University Press, 2009.
 Lappas, N.H.; Gounaris, C.E. Multi-Stage Adjustable Robust Optimization for Process Scheduling Under Uncertainty. AIChE Journal, 2016, 62 (5), 1646-1667.
 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.
 Zeng, B.; Zhao, L.; Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters, 2013, 41, 457-461.
 Orlowski S.; WessÃ¤ly R.; PiÃ³ro M.; Tomaszewski A. SNDlib 1.0âsurvivable network design library. Networks, 2010, 55(3), 276-286.