A generic optimization framework for resilient systems. (English) Zbl 1515.90086
Summary: This paper addresses the optimal design of resilient systems, in which components can fail. The system can react to failures and its behaviour is described by general mixed integer nonlinear programs, which allows for applications to many (technical) systems. This then leads to a three-level optimization problem. The upper level designs the system minimizing a cost function, the middle level represents worst-case failures of components, i.e. interdicts the system, and the lowest level operates the remaining system. We describe new inequalities that characterize the set of resilient solutions and allow to reformulate the problem. The reformulation can then be solved using a nested branch-and-cut approach. We discuss several improvements, for instance, by taking symmetry into account and strengthening cuts. We demonstrate the effectiveness of our implementation on the optimal design of water networks, robust trusses, and gas networks, in comparison to an approach in which the failure scenarios are directly included into the model.
MSC:
| 90C17 | Robustness in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
multi-level optimization; mixed integer nonlinear programming; interdiction problems; gas and water network design; truss topology optimizationReferences:
| [1] | Adjiashvili, D., Hommelsheim, F., Mühlenthaler, M., and Schaudt, O., Fault-tolerant edge-disjoint paths – beyond uniform faults, arXiv preprint 2009.05382 (2020). |
| [2] | Adjiashvili, D.; Stiller, S.; Zenklusen, R., Bulk-robust combinatorial optimization, Math. Program., 149, 361-390 (2015) · Zbl 1307.90148 |
| [3] | Alderson, D.L., Brown, G.G., Carlyle, W.M., and Wood, R.K., Solving defender-attacker-defender models for infrastructure defense, in Operations Research, Computing and Homeland Defense, INFORMS, R.K. Wood and R.F. Dell, eds., Hanover, MD: Institute for Operations Research and the Management Sciences, 2011, pp. 28-49. |
| [4] | Alguacil, N.; Delgadillo, A.; Arroyo, J. M., A trilevel programming approach for electric grid defense planning, Comput. Oper. Res., 41, 282-290 (2014) · Zbl 1348.90378 |
| [5] | Altherr, L.C., Brötz, N., Dietrich, I., Gally, T., Geßner, F., Kloberdanz, H., Leise, P., Pelz, P.F., Schlemmer, P., and Schmitt, A., Resilience in mechanical engineering – a concept for controlling uncertainty during design, production and usage phase of load-carrying structures, in Uncertainty in Mechanical Engineering III, P.F. Pelz and P. Groche, eds., Applied Mechanics and Materials Vol. 885. Trans Tech Publications, 2018, pp. 187-198. |
| [6] | Altherr, L. C.; Leise, P.; Pfetsch, M. E.; Schmitt, A., Resilient layout, design and operation of energy-efficient water distribution networks for high-rise buildings using MINLP, Optim. Eng., 20, 605-645 (2019) · Zbl 1431.62677 |
| [7] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press · Zbl 1193.68112 |
| [8] | Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta. Numerica., 22, 1-131 (2013) · Zbl 1291.65172 |
| [9] | Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 464-501 (2011) · Zbl 1233.90259 |
| [10] | Bestuzheva, K., Gleixner, A., and Vigerske, S., A computational study of perspective cuts, arXiv preprint 2103.09573 (2021). |
| [11] | Bienstock, D., Electrical transmission system cascades and vulnerability: An operations research viewpoint, SIAM-MOS Ser. Optim. (2015) · Zbl 1344.90001 |
| [12] | Borraz-Sánchez, C.; Bent, R.; Backhaus, S.; Hijazi, H.; Hentenryck, P. V., Convex relaxations for gas expansion planning, INFORMS J. Comput., 28, 645-656 (2016) · Zbl 1355.90063 |
| [13] | Brown, G.; Carlyle, M.; Salmerón, J.; Wood, K., Defending critical infrastructure, Interfaces, 36, 530-544 (2006) |
| [14] | Church, R. L.; Scaparra, M. P., Protecting critical assets: The R-interdiction median problem with fortification, Geogr. Anal., 39, 129-146 (2007) |
| [15] | D’Ambrosio, C.; Lodi, A.; Wiese, S.; Bragalli, C., Mathematical programming techniques in water network optimization, Eur. J. Oper. Res., 243, 774-788 (2015) · Zbl 1346.90211 |
| [16] | De Wolf, D.; Smeers, Y., The gas transmission problem solved by an extension of the simplex algorithm, Manage. Sci., 46, 1454-1465 (2000) · Zbl 1232.90355 |
| [17] | DeNegre, S., Interdiction and discrete bilevel linear programming, Ph.D. diss., Lehigh University, 2011. |
| [18] | Ding, T.; Yao, L.; Li, F., A multi-uncertainty-set based two-stage robust optimization to defender-attacker-defender model for power system protection, Reliab. Eng. Syst. Saf., 169, 179-186 (2018) |
| [19] | Fang, Y. and Zio, E., Optimizing the resilience of interdependent infrastructure systems against intentional attacks, in 2nd International Conference on System Reliability and Safety (ICSRS), 2017, pp. 62-67. |
| [20] | Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Oper. Res., 65, 1615-1637 (2017) · Zbl 1386.90085 |
| [21] | Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., Interdiction games and monotonicity, with application to knapsack problems, INFORMS. J. Comput., 31, 390-410 (2019) · Zbl 07281718 |
| [22] | Furini, F.; Ljubić, I.; Martin, S.; San Segundo, P., The maximum clique interdiction problem, Eur. J. Oper. Res., 277, 112-127 (2019) · Zbl 1430.90543 |
| [23] | Gally, T., Computational mixed-integer semidefinite programming, Ph.D. diss., Darmstadt, 2019. · Zbl 1423.90153 |
| [24] | Gally, T., Kuttich, A., Pfetsch, M.E., Schaeffner, M., and Ulbrich, S., Optimal placement of active bars for buckling control in truss structures under bar failures, in Uncertainty in Mechanical Engineering III, P.F. Pelz and P. Groche, eds., Applied Mechanics and Materials Vol. 885. Trans Tech Publications, 2018, pp. 119-130. |
| [25] | Gally, T.; Pfetsch, M. E.; Ulbrich, S., A framework for solving mixed-integer semidefinite programs, Optim. Methods Softw., 33, 594-632 (2018) · Zbl 1398.90109 |
| [26] | Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., and Witzig, J., The SCIP optimization suite 7.0, Tech. Rep., Optimization Online, 2020. Available at www.optimization-online.org/DB_HTML/2020/03/7705.html. |
| [27] | Ghorbani-Renani, N.; González, A. D.; Barker, K.; Morshedlou, N., Protection-interdiction-restoration: Tri-level optimization for enhancing interdependent network resilience, Reliab. Eng. Syst. Saf., 199 (2020) |
| [28] | Gleixner, A. M.; Held, H.; Huang, W.; Vigerske, S., Towards globally optimal operation of water supply networks, Numer. Algebra, Control Optim., 2, 695-711 (2012) · Zbl 1269.90083 |
| [29] | Grötschel, M.; Monma, C. L.; Stoer, M., Design of survivable networks, Handbooks Oper. Res. Manag. Sci., 7, 617-672 (1995) · Zbl 0839.90132 |
| [30] | Habeck, O.; Pfetsch, M. E., Combinatorial acyclicity models for potential-based flows, Networks, 79, 83-104 (2021) · Zbl 07775499 |
| [31] | Hojny, C.; Pfetsch, M. E., Polytopes associated with symmetry handling, Math. Program., 175, 197-240 (2019) · Zbl 1421.90088 |
| [32] | Humpola, J., Gas network optimization by MINLP, Ph.D. diss., Berlin, 2014. |
| [33] | Humpola, J.; Fügenschuh, A., Convex reformulations for solving a nonlinear network design problem, Comput. Optim. Appl., 62, 717-759 (2015) · Zbl 1337.90072 |
| [34] | Israeli, E., System interdiction and defense, Ph.D. diss., Naval Postgraduate School Monterey, 1999. |
| [35] | Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 97-111 (2002) · Zbl 1027.90106 |
| [36] | Kerivin, H.; Mahjoub, A. R., Design of survivable networks: A survey, Networks, 46, 1-21 (2005) · Zbl 1072.90003 |
| [37] | Kleinert, T.; Labbé, M.; Ljubić, I.; Schmidt, M., A survey on mixed-integer programming techniques in bilevel optimization, EURO J. Comput. Optim., 9, 100007 (2021) · Zbl 1533.90002 · doi:10.1016/j.ejco.2021.100007 |
| [38] | Kleniati, P. M.; Adjiman, C. S., A generalization of the branch-and-Sandwich algorithm: from continuous to mixed-integer nonlinear bilevel problems, Comput. Chem. Eng., 72, 373-386 (2015) |
| [39] | Koch, T., Hiller, B., Pfetsch, M.E., and Schewe, L., Evaluating gas network capacities, MOS-SIAM Series on Optimization, SIAM, 2015. · Zbl 1322.90007 |
| [40] | Kočvara, M., Truss topology design with integer variables made easy, Tech. Rep., Optimization Online, 2010. Available at www.optimization-online.org/DB_HTML/2010/05/2614.html. |
| [41] | Liberti, L., Symmetry in mathematical programming, in Mixed Integer Nonlinear Programming, J. Lee and S. Leyffer, eds., Springer, 2012, pp. 263-283. · Zbl 1242.90236 |
| [42] | Lozano, L.; Smith, J. C., A backward sampling framework for interdiction problems with fortification, INFORMS J. Comput., 29, 123-139 (2017) · Zbl 1414.91086 |
| [43] | Lozano, L.; Smith, J. C., A value-function-based exact approach for the bilevel mixed-integer programming problem, Oper. Res., 65, 768-786 (2017) · Zbl 1387.90161 |
| [44] | Lozano, L.; Smith, J. C.; Kurz, M. E., Solving the traveling salesman problem with interdiction and fortification, Oper. Res. Lett., 45, 210-216 (2017) · Zbl 1409.90111 |
| [45] | Margot, F., Symmetry in integer linear programming, in 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, eds., Springer, 2010, pp. 647-686. · Zbl 1187.90200 |
| [46] | Mars, S., Mixed-integer semidefinite programming with an application to truss topology design, Ph.D. diss., FAU Erlangen-Nürnberg, 2013. |
| [47] | Mitsos, A., Global solution of nonlinear mixed-integer bilevel programs, J. Glob. Optim., 47, 557-582 (2010) · Zbl 1202.90217 |
| [48] | Morsi, A., Geißler, B., and Martin, A., Mixed integer optimization of water supply networks, in Mathematical Optimization of Water Networks, Springer, 2012, pp. 35-54. · Zbl 1259.90076 |
| [49] | MOSEK ApS, MOSEK Optimizer API for C Release 9.2.35 (2021). Available at docs.mosek.com/9.2/capi/index.html |
| [50] | Müller, T. M.; Leise, P.; Lorenz, I. S.; Altherr, L. C.; Pelz, P. F., Optimization and validation of pumping system design and operation for water supply in high-rise buildings, Optim. Eng., 22, 643-686 (2021) · Zbl 1486.90129 |
| [51] | Papadimitriou, C., Computational Complexity (1994), Addison Welsey: Addison Welsey, Reading (MA) · Zbl 0833.68049 |
| [52] | Pfetsch, M. E.; Fügenschuh, A.; Geißler, B.; Geißler, N.; Gollmer, R.; Hiller, B.; Humpola, J.; Koch, T.; Lehmann, T.; Martin, A.; Morsi, A.; Rövekamp, J.; Schewe, L.; Schmidt, M.; Schultz, R.; Schwarz, R.; Schweiger, J.; Stangl, C.; Steinbach, M. C.; Vigerske, S.; Willert, B. M., Validation of nominations in gas network optimization: Models, methods, and solutions, Optim. Methods Softw., 30, 15-53 (2015) · Zbl 1325.90019 |
| [53] | Scaparra, M. P.; Church, R. L., A bilevel mixed-integer program for critical infrastructure protection planning, Comput. Oper. Res., 35, 1905-1923 (2008) · Zbl 1139.90439 |
| [54] | Schmidt, M.; Aßmann, D.; Burlacu, R.; Humpola, J.; Joormann, I.; Kanelakis, N.; Koch, T.; Oucherif, D.; Pfetsch, M. E.; Schewe, L.; Schwarz, R.; Sirvent, M., GasLiblibrary of gas network instances, Data, 2, 40 (2017) |
| [55] | Schrijver, A., Combinatorial optimization: Polyhedra and efficiency, Algorithms and Combinatorics, Vol. 24, Springer, 2003. · Zbl 1041.90001 |
| [56] | Schweiger, J.; Liers, F., A decomposition approach for optimal gas network extension with a finite set of demand scenarios, Optim. Eng., 19, 297-326 (2018) · Zbl 1397.90085 |
| [57] | SCIP-SDP - a mixed integer semidefinite programming plugin for SCIP, 2019. Available at www.opt.tu-darmstadt.de/scipsdp/. |
| [58] | Sharkey, T. C.; Nurre Pinkley, S. G.; Eisenberg, D. A.; Alderson, D. L., In search of network resilience: an optimization-based view, Networks, 77, 225-254 (2021) |
| [59] | Smith, J.C. and Lim, C., Algorithms for network interdiction and fortification games, in Pareto Optimality, Game Theory And Equilibria, A. Chinchuluun, P.M. Pardalos, A. Migdalas, and L. Pitsoulis, eds., Springer, New York, NY, 2008, pp. 609-644. · Zbl 1152.91385 |
| [60] | Smith, J. C.; Song, Y., A survey of network interdiction models and algorithms, Eur. J. Oper. Res., 283, 797-811 (2020) · Zbl 1441.90048 |
| [61] | Stackelberg, H.v., Theory of the Market Economy (1952), Oxford University Press |
| [62] | Tahernejad, S.; Ralphs, T. K.; DeNegre, S. T., A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, Math. Program. Comput., 12, 529-568 (2020) · Zbl 1458.90488 |
| [63] | Tanınmış, K. and Sinnl, M., A branch-and-cut algorithm for submodular interdiction games, arXiv preprint 2103.15788 (2021). · Zbl 07625894 |
| [64] | Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542 |
| [65] | Wang, Q.; Watson, J.; Guan, Y., Two-stage robust optimization for N-k contingency-constrained unit commitment, IEEE Trans. Power Syst., 28, 2366-2375 (2013) |
| [66] | Wollmer, R., Removing arcs from a network, Oper. Res., 12, 934-940 (1964) · Zbl 0204.20102 |
| [67] | Wood, R.K., Bilevel network interdiction models: Formulations and solutions, in Wiley Encyclopedia of Operations Research and Management Science, John Wiley & Sons, 2011. |
| [68] | Xiang, Y.; Wang, L., An improved defender-attacker-defender model for transmission line defense considering offensive resource uncertainties, IEEE. Trans. Smart. Grid., 10, 2534-2546 (2019) |
| [69] | Yao, Y.; Edmunds, T.; Papageorgiou, D.; Alvarez, R., Trilevel optimization in power network defense, IEEE. Trans. Syst. Man Cybern. Part C Appl. Rev., 37, 712-718 (2007) |
| [70] | Yuan, W.; Zhao, L.; Zeng, B., Optimal power grid protection through a defender-attacker-defender model, Reliab. Eng. Syst. Saf., 121, 83-89 (2014) |
| [71] | Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 457-461 (2013) · Zbl 1286.90143 |
| [72] | Zheng, K.; Albert, L. A., An exact algorithm for solving the bilevel facility interdiction and fortification problem, Oper. Res. Lett., 46, 573-578 (2018) · Zbl 1476.90184 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
