×

Tri-level mixed-binary linear programming: solution approaches and application in defending critical infrastructure. (English) Zbl 1490.90280

Summary: Decentralized decision-making is becoming more ubiquitous in different organizations that often follow a hierarchical structure. To model these problems, multi-level programming has been suggested as a suitable methodology for modeling the interaction between the different levels of decisions. However, multi-level programming, even for the case of bi-levels, is known to be strongly \(\mathcal{N}P\)-hard. To address this computational challenge, we develop three different heuristic-based approaches for solving a specific class of tri-level programming problems, in which the leader has direct control over the follower’s decisions to a certain extent, with a common objective function shared at all levels. As expected, each heuristic type offers a trade-off between solution quality and computational time. To illustrate our solution approach, we present an application for defending critical infrastructure to improve its resilience against intentional attacks. In this context we use a defender-attacker-defender model and apply it to electrical power grids. We also propose a modified implementation of a widely adopted enumeration algorithm in this area, with a warm-starting solution technique that significantly enhanced the computational performance of the enumeration algorithm. We test our solution approaches on three electrical transmission networks and present the results of our numerical computations as well as some insights.

MSC:

90C30 Nonlinear programming
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alguacil, N.; Delgadillo, A.; Arroyo, J. M., A trilevel programming approach for electric grid defense planning, Computers and Operations Research, 41, 282-290 (2014) · Zbl 1348.90378
[2] Alvarez, R. E., Interdicting Electrical Power Grids (2004), Monterey, California. Naval Postgraduate School, Ph.D. thesis.
[3] Anandalingam, G., A mathematical programming model of decentralized multi-level systems, Journal of the Operational Research Society, 39, 11, 1021-1033 (1988) · Zbl 0657.90061
[4] Arroyo, J. M., Bilevel programming applied to power system vulnerability analysis under multiple contingencies, IET Generation, Transmission and Distribution, 4, 2, 178-190 (2010)
[5] Arroyo, J. M.; Galiana, F. D., On the solution of the bilevel programming formulation of the terrorist threat problem, IEEE Transactions on Power Systems, 20, 2, 789-797 (2005)
[6] Aussel, D.; Svensson, A., Is pessimistic bilevel programming a special case of a mathematical program with complementarity constraints?, Journal of Optimization Theory and Applications, 181, 2, 504-520 (2019) · Zbl 1414.90324
[7] Babick, J. P., Tri-Level Optimization of Critical Infrastructure Resilience, Technical Report (2009), Naval Postgraduate School Monterey United States
[8] Bard, J. F., An investigation of the linear three level programming problem, IEEE Transactions on Systems, Man, and Cybernetics, 5, 711-717 (1984) · Zbl 0552.90081
[9] Bard, J. F., Some properties of the bilevel programming problem, Journal of Optimization Theory and Applications, 68, 2, 371-378 (1991) · Zbl 0696.90086
[10] Bard, J. F., Practical bilevel optimization: Algorithms and applications, vol. 30 (2013), Springer Science & Business Media
[11] Bard, J. F.; Moore, J. T., An algorithm for the discrete bilevel programming problem, Naval Research Logistics (NRL), 39, 3, 419-435 (1992) · Zbl 0751.90111
[12] Blair, C., The computational complexity of multi-level linear programs, Annals of Operations Research, 34, 1, 13-19 (1992) · Zbl 0751.90046
[13] Brown, G.; Carlyle, M.; Salmerón, J.; Wood, K., Defending critical infrastructure, Interfaces, 36, 6, 530-544 (2006)
[14] Candler, W.; Norton, R., Multilevel Programming and Developing Policy, Technical Report 258 (1977), World Bank Development Research Center
[15] Colson, B.; Marcotte, P.; Savard, G., Bilevel programming: A survey, 4OR, 3, 2, 87-107 (2005) · Zbl 1134.90482
[16] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Annals of Operations Research, 153, 1, 235-256 (2007) · Zbl 1159.90483
[17] Dempe, S., Foundations of bilevel programming (2002), Springer Science & Business Media · Zbl 1038.90097
[18] Dempe, S.; Dutta, J., Is bilevel programming a special case of a mathematical program with complementarity constraints?, Mathematical Programming, 131, 1-2, 37-48 (2012) · Zbl 1235.90145
[19] Fathollahi-Fard, A. M.; Hajiaghaei-Keshteli, M.; Mirjalili, S., Hybrid optimizers to solve a tri-level programming model for a tire closed-loop supply chain network design problem, Applied Soft Computing, 70, 701-722 (2018)
[20] Florensa, C.; Garcia-Herreros, P.; Misra, P.; Arslan, E.; Mehta, S.; Grossmann, I. E., Capacity planning with competitive decision-makers: Trilevel milp formulation, degeneracy, and solution approaches, European Journal of Operational Research, 262, 2, 449-463 (2017) · Zbl 1375.90149
[21] Floudas, C. A., Nonlinear and mixed-integer optimization: Fundamentals and applications (1995), Oxford University Press · Zbl 0886.90106
[22] Fortuny-Amat, J.; McCarl, B., A representation and economic interpretation of a two-level programming problem, Journal of the Operational Research Society, 32, 9, 783-792 (1981) · Zbl 0459.90067
[23] Gu, Y.; Cai, X.; Han, D.; Wang, D. Z., A tri-level optimization model for a private road competition problem with traffic equilibrium constraints, European Journal of Operational Research, 273, 1, 190-197 (2019) · Zbl 1403.90225
[24] Han, J.; Zhang, G.; Hu, Y.; Lu, J., A solution to bi/tri-level programming problems using particle swarm optimization, Information Sciences, 370, 519-537 (2016) · Zbl 1428.90181
[25] Hong, S.; Cheng, H.; Zeng, P., Nk constrained composite generation and transmission expansion planning with interval load, IEEE Access, 5, 2779-2789 (2017)
[26] Irohara, T.; Kuo, Y.-H.; Leung, J. M., From preparedness to recovery: A tri-level programming model for disaster relief planning, International conference on computational logistics, 213-228 (2013), Springer
[27] Jiang, P.; Huang, S.; Zhang, T., Optimal deception strategies in power system fortification against deliberate attacks, Energies, 12, 3, 342 (2019)
[28] Krebs, V.; Schewe, L.; Schmidt, M., Uniqueness and multiplicity of market equilibria on dc power flow networks, European Journal of Operational Research, 271, 1, 165-178 (2018) · Zbl 1403.90206
[29] Lazzaro, G. L., Tri-level Optimization Algorithms for Solving Defender-Attacker-Defender Network Models, Technical Report (2016), Naval Postgraduate School Monterey United States
[30] Lin, Y.; Bie, Z., Tri-level optimal hardening plan for a resilient distribution system considering reconfiguration and DG islanding, Applied Energy, 210, 1266-1279 (2018)
[31] Mahmoodjanloo, M.; Parvasi, S. P.; Ramezanian, R., A tri-level covering fortification model for facility protection against disturbance in r-interdiction median problem, Computers and Industrial Engineering, 102, 219-232 (2016)
[32] Manual, C. U., IBM ILOG CPLEX optimization studio, Version, 12, 1987-2018 (1987)
[33] Moore, J. T.; Bard, J. F., The mixed integer linear bilevel programming problem, Operations Research, 38, 5, 911-921 (1990) · Zbl 0723.90090
[34] O’Flaherty, K. (2019). U.S. government makes surprise move to secure power grid from cyberattacks. https://www.forbes.com/sites/kateoflahertyuk/2019/07/03/u-s-government-makes-surprise-move-to-secure-power-grid-from-cyber-attacks#73c27cac3191. Accessed: 2019-11-06.
[35] Parkatti, V.-P.; Assmuth, A.; Rämö, J.; Tahvonen, O., Economics of boreal conifer species in continuous cover and rotation forestry, Forest Policy and Economics, 100, 55-67 (2019)
[36] Ríos-Mercado, R. Z.; Wu, S.; Scott, L. R.; Boyd, E. A., A reduction technique for natural gas transmission network optimization problems, Annals of Operations Research, 117, 1-4, 217-234 (2002) · Zbl 1028.90501
[37] Sarhadi, H.; Tulett, D. M.; Verma, M., A defender-attacker-defender approach to the optimal fortification of a rail intermodal terminal network, Journal of Transportation Security, 8, 1-2, 17-32 (2015)
[38] Sarhadi, H.; Tulett, D. M.; Verma, M., An analytical approach to the protection planning of a rail intermodal terminal network, European Journal of Operational Research, 257, 2, 511-525 (2017) · Zbl 1394.90394
[39] Scaparra, M. P.; Church, R. L., A bilevel mixed-integer program for critical infrastructure protection planning, Computers and Operations Research, 35, 6, 1905-1923 (2008) · Zbl 1139.90439
[40] Schweitzer, D.; Medal, H., Wireless LAN transmitter location under the threat of jamming attacks, Computers and Operations Research, 106, 14-27 (2019) · Zbl 1458.90194
[41] Sinha, S., A comment on Anandalingam (1988). A mathematical programming model of decentralized multi-level systems. J Opl Res Soc 39: 1021-1033, Journal of the Operational Research Society, 52, 5, 594-596 (2001) · Zbl 0657.90061
[42] Smith, R. (2014). Assault on california power station raises alarm on potential for terrorism. https://www.wsj.com/articles/assault-on-california-power-station-raises-alarm-on-potential-for-terrorism-1391570879. Accessed: 2019-04-30.
[43] Sussman, B. (2019). Revealed: Details of ‘first of its kind’ disruptive power grid attack. https://www.secureworldexpo.com/industry-news/first-u.s.-power-grid-attack-details. Accessed: 2019-11-06.
[44] Vicente, L. N.; Calamai, P. H., Bilevel and multilevel programming: A bibliography review, Journal of Global Optimization, 5, 3, 291-306 (1994) · Zbl 0822.90127
[45] Von Stackelberg, H., The theory of the market economy (1952), Oxford University Press
[46] White, D., Penalty function approach to linear trilevel programming, Journal of Optimization Theory and Applications, 93, 1, 183-197 (1997) · Zbl 0898.90089
[47] Wu, X.; Conejo, A. J., An efficient tri-level optimization model for electric grid defense planning, IEEE Transactions on Power Systems, 32, 4, 2984-2994 (2017)
[48] Xu, P.; Wang, L., An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Computers and Operations Research, 41, 309-318 (2014) · Zbl 1348.90496
[49] Yao, Y.; Edmunds, T.; Papageorgiou, D.; Alvarez, R., Trilevel optimization in power network defense, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 37, 4, 712-718 (2007)
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.