×

A survey on mixed-integer programming techniques in bilevel optimization. (English) Zbl 1533.90002

A brief literature survey on bilevel optimization has been efficiently carried out in this paper. Bilevel optimization is a sequential process moving hierarchically from one level to another level problem. Numerous applications of bilevel programming can be seen in real world. Different aspects of bilevel problems comprising of mixed integer programming along with their solution techniques have been analyzed. The authors have scrutinized bilevel problems in which either lower level problem is convex or they have integral constraints. Mixed integer nonlinear bilevel problems are also examined in the paper. Further, bilinear terms in pricing or interdiction models leading to non-convex problems are also studied. A classification of interdiction problems based on the structures of the encompassed lower-level problems is also provided. A discussion on Stackelberg games involving linear constraints and bilinear objective functions at both the levels is also conducted in the paper. Various methods for solving bilevel programming problems consisting of linear as well as mixed nonlinear objective functions and to obtain its optimal solution are studied, namely, branch-and-bound method, branch-and-cut method, decomposition principle, cutting planes, \(K\)th best algorithm, to name a few. Distinct algorithmic and computational techniques are discussed in the paper which will be beneficial to the researchers working in this field. This paper has provided the researchers with all the prospects required for research in bilevel optimization.
Reviewer: Ritu Arora (Delhi)

MSC:

90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90Bxx Operations research and management science
91A65 Hierarchical games (including Stackelberg games)
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C90 Applications of mathematical programming

References:

[1] URL: https://www.gurobi.com/wp-content/uploads/2019/12/Gurobi-9.0-Overview-Webinar-Slides-1.pdf.
[2] Akgün, I.; Tansel, B.Ç.; Wood, R. K., The multi-terminal maximum-flow network-interdiction problem, European Journal of Operational Research, 211, 2, 241-251 (2011) · Zbl 1250.90021
[3] Alguacil, N.; Delgadillo, A.; Arroyo, J. M., A trilevel programming approach for electric grid defense planning, Computers & Operations Research, 41, 282-290 (2014) · Zbl 1348.90378
[4] Ambrosius, M.; Grimm, V.; Kleinert, T.; Liers, F.; Schmidt, M.; Zöttl, G., Endogenous price zones and investment incentives in electricity markets: An application of multilevel optimization with graph partitioning, Energy Economics, 92 (2020)
[5] Anandalingam, G.; Friesz, T., Hierarchical optimization: An introduction, Annals of Operations Research, 34, 1, 1-11 (1992) · Zbl 0751.90067
[6] Anandalingam, G.; White, D., A solution method for the linear static Stackelberg problem using penalty functions, IEEE Transactions on Automatic Control, 35, 10, 1170-1173 (1990) · Zbl 0721.90098
[7] Arroyo, J. M., Bilevel programming applied to power system vulnerability analysis under multiple contingencies, IET Generation, Transmission & Distribution, 4, 2, 178-190 (2010)
[8] Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Computers & Operations Research, 36, 7, 2193-2200 (2009) · Zbl 1158.90411
[9] Assimakopoulos, N., A network interdiction model for hospital infection control, Computers in Biology and Medicine, 17, 6, 413-422 (1987)
[10] Audet, C.; Haddad, J.; Savard, G., A note on the definition of a linear bilevel programming solution, Applied Mathematics and Computation, 181, 1, 351-355 (2006) · Zbl 1163.90641
[11] Audet, C.; Haddad, J.; Savard, G., Disjunctive cuts for continuous linear bilevel programming, Optimization Letters, 1, 3, 259-267 (2007) · Zbl 1127.90069
[12] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., Links between linear bilevel and mixed 0-1 programming problems, Journal of Optimization Theory and Applications, 93, 2, 273-300 (1997) · Zbl 0901.90153
[13] Audet, C.; Savard, G.; Zghal, W., New Branch-and-Cut Algorithm for Bilevel Linear Programming, Journal of Optimization Theory and Applications, 134, 2, 353-370 (2007) · Zbl 1161.90442
[14] Aussel, D.; Brotcorne, L.; Lepaul, S.; von Niederhäusern, L., A trilevel model for best response in energy demand-side management, European Journal of Operational Research, 281, 2, 299-315 (2020) · Zbl 1431.91262
[15] Avraamidou, S.; Pistikopoulos, E. N., B-pop: Bi-level parametric optimization toolbox, Computers & Chemical Engineering, 122, 193-202 (2019)
[16] Avraamidou, S.; Pistikopoulos, E. N., A multi-parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems, Computers & Chemical Engineering, 125, 98-113 (2019)
[17] To appear · Zbl 1470.91037
[18] Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Operations Research, 19, 1, 19-39 (1971) · Zbl 0219.90035
[19] Ball, M. O.; Golden, B. L.; Vohra, R. V., Finding the most vital arcs in a network, Operations Research Letters, 8, 2, 73-76 (1989) · Zbl 0679.90086
[20] Bard, J. F., Coordination of a multidivisional organization through two levels of management, Omega, 11, 5, 457-468 (1983)
[21] Bard, J. F., Optimality conditions for the bilevel programming problem, Naval Research Logistics Quarterly, 31, 1, 13-26 (1984) · Zbl 0537.90087
[22] Bard, J. F., Convex two-level optimization, Mathematical Programming, 40, 1, 15-27 (1988) · Zbl 0655.90060
[23] Bard, J. F., Some properties of the bilevel programming problem, Journal of Optimization Theory and Applications, 68, 2, 371-378 (1991) · Zbl 0696.90086
[24] Bard, J. F., Practical bilevel optimization: algorithms and applications, 30 (1998), Springer Science & Business Media · Zbl 0943.90078
[25] Bard, J. F.; Moore, J. T., A branch and bound algorithm for the bilevel programming problem, SIAM Journal on Scientific and Statistical Computing, 11, 2, 281-292 (1990) · Zbl 0702.65060
[26] Bard, J. F.; Moore, J. T., An algorithm for the discrete bilevel programming problem, Naval Research Logistics, 39, 3, 419-435 (1992) · Zbl 0751.90111
[27] Bard, J. F.; Plummer, J.; Sourie, J. C., A bilevel programming approach to determining tax credits for biofuel production, European Journal of Operational Research, 120, 1, 30-46 (2000) · Zbl 0976.90099
[28] Baringo, L.; Conejo, A. J., Transmission and wind power investment, IEEE Transactions on Power Systems, 27, 2, 885-893 (2012)
[29] Basu, A.; Ryan, C. T.; Sankaranarayanan, S., Mixed-integer bilevel representability, Mathematical Programming, 185, 1, 163-197 (2021) · Zbl 1480.90176
[30] Bazgan, C.; Toubaline, S.; Tuza, Z., The most vital nodes with respect to independent set and vertex cover, Discrete Applied Mathematics, 159, 17, 1933-1946 (2011) · Zbl 1236.05141
[31] Bazgan, C.; Toubaline, S.; Vanderpooten, D., Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Journal of Combinatorial Optimization, 26, 1, 178-189 (2013) · Zbl 1275.90113
[32] Beale, E. M.L.; Tomlin, J. A., Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, (Lawrence, J., Proceedings of the Fifth International Conference on Operational Research (1970), Tavistock Publications), 447-454
[33] 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
[34] Ben-Ayed, O., Bilevel linear programming, Computers & Operations Research, 20, 5, 485-501 (1993) · Zbl 0783.90068
[35] Ben-Ayed, O.; Blair, C. E.; Boyce, D. E.; LeBlanc, L. J., Construction of a real-world bilevel linear programming model of the highway network design problem, Annals of Operations Research, 34, 1, 219-254 (1992) · Zbl 0729.91035
[36] Ben-Ayed, O.; Boyce, D. E.; Blair, C. E., A general bilevel linear programming formulation of the network design problem, Transportation Research Part B: Methodological, 22, 4, 311-318 (1988)
[37] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[38] Bennett, K. P.; Jing Hu; Xiaoyun Ji; Kunapuli, G.; Jong-Shi Pang, Model selection via bilevel optimization, The 2006 IEEE International Joint Conference on Neural Network Proceedings, 1922-1929 (2006)
[39] Bennett, K. P.; Kunapuli, G.; Hu, J.; Pang, J.-S., Bilevel optimization and machine learning, IEEE World Congress on Computational Intelligence, 25-47 (2008), Springer
[40] Besançon, M., Anjos, M. F., Brotcorne, L., 2019. Near-optimal robust bilevel optimization. URL: https://hal.archives-ouvertes.fr/hal-02414848. · Zbl 1477.90051
[41] Besançon, M.; Anjos, M. F.; Brotcorne, L., Complexity of near-optimal robust versions of multilevel optimization problems · Zbl 1477.90051
[42] Bialas, W. F.; Karwan, M. H., Two-level linear programming, Management Science, 30, 8, 1004-1020 (1984) · Zbl 0559.90053
[43] Bolusani, S.; Coniglio, S.; Ralphs, T. K.; Tahernejad, S., A Unified Framework for Multistage Mixed Integer Linear Optimization, 513-560 (2020), Springer International Publishing · Zbl 1481.90229
[44] URL: http://www.optimization-online.org/DB_HTML/2020/04/7755.html.
[45] Bonami, P.; Biegler, L. T.; Conn, A. R.; Cornuéjols, G.; Grossmann, I. E.; Laird, C. D.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optimization, 5, 2, 186-204 (2008) · Zbl 1151.90028
[46] Borrero, J. S.; Prokopyev, O. A.; Sauré, D., Sequential interdiction with incomplete information and learning, Operations Research, 67, 1, 72-89 (2019) · Zbl 1443.90206
[47] Böttger, T.; Grimm, V.; Kleinert, T.; Schmidt, M., The cost of decoupling trade and transport in the European entry-exit gas market, European Journal of Operational Research (2021) · Zbl 1490.91147
[48] Bouhtou, M.; van Hoesel, S.; van der Kraaij, A. F.; Lutton, J.-L., Tariff optimization in networks, INFORMS Journal on Computing, 19, 3, 458-469 (2007) · Zbl 1241.90182
[49] Bracken, J.; McGill, J. T., Mathematical programs with optimization problems in the constraints, Operations Research, 21, 1, 37-44 (1973) · Zbl 0263.90029
[50] Brotcorne, L.; Cirinei, F.; Marcotte, P.; Savard, G., An exact algorithm for the network pricing problem, Discrete Optimization, 8, 2, 246-258 (2011) · Zbl 1241.90156
[51] Brotcorne, L.; Labbé, M.; Marcotte, P.; Savard, G., A bilevel model and solution algorithm for a freight tariff-setting problem, Transportation Science, 34, 3, 289-302 (2000) · Zbl 0991.90573
[52] Brotcorne, L.; Labbé, M.; Marcotte, P.; Savard, G., A bilevel model for toll optimization on a multicommodity transportation network, Transportation Science, 35, 4, 345-358 (2001) · Zbl 1069.90502
[53] Brotcorne, L.; Labbé, M.; Marcotte, P.; Savard, G., Joint design and pricing on a network, Operations Research, 56, 5, 1104-1115 (2008) · Zbl 1167.90373
[54] Brown, G.; Carlyle, M.; Salmerón, J.; Wood, R. K., Defending critical infrastructure, INFORMS Journal on Applied Analytics, 36, 6, 530-544 (2006)
[55] Bucarey, V.; Casorrán, C.; Labbé, M.; Ordoñez, F.; Figueroa, O., Coordinating resources in Stackelberg security games, European Journal of Operational Research (2019)
[56] Burtscheidt, J.; Claus, M., Bilevel Linear Optimization Under Uncertainty, 485-511 (2020), Springer International Publishing · Zbl 1481.90234
[57] Burtscheidt, J.; Claus, M.; Dempe, S., Risk-averse models in bilevel stochastic linear programming, SIAM Journal on Optimization, 30, 1, 377-406 (2020) · Zbl 1431.90099
[58] Bylling, H. C.; Boomsma, T. K.; Gabriel, S. A., A Parametric Programming Approach to Bilevel Merchant Electricity Transmission Investment Problems, (Hesamzadeh, M. R.; Rosellón, J.; Vogelsang, I., Transmission Network Investment in Liberalized Power Markets. Lecture Notes in Energy, vol 79 (2020), Springer, Cham), 237-254
[59] Calvete, H. I.; Galé, C., The bilevel linear/linear fractional programming problem, European Journal of Operational Research, 114, 1, 188-197 (1999) · Zbl 0941.90069
[60] Calvete, H. I.; Galé, C., Solving linear fractional bilevel programs, Operations Research Letters, 32, 2, 143-151 (2004) · Zbl 1036.90068
[61] Calvete, H. I.; Galé, C., Algorithms for Linear Bilevel Optimization, 293-312 (2020), Springer International Publishing · Zbl 1481.90220
[62] Campelo, M.; Dantas, S.; Scheimberg, S., A note on a penalty function approach for solving bilevel linear programs, Journal of Global Optimization, 16, 3, 245-255 (2000) · Zbl 0971.90064
[63] Candler, W.; Fortuny-Amat, J.; McCarl, B., The potential role of multilevel programming in agricultural economics, American Journal of Agricultural Economics, 63, 3, 521-531 (1981)
[64] Candler, W.; Norton, R., Multi-level Programming, Discussion Papers, Development Research Center, International Bank for Reconstruction and Development (1977), World Bank
[65] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, G. J., A study on the computational complexity of the bilevel knapsack problem, SIAM Journal on Optimization, 24, 2, 823-838 (2014) · Zbl 1297.90134
[66] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, G. J., Bilevel knapsack with interdiction constraints, INFORMS Journal on Computing, 28, 2, 319-333 (2016) · Zbl 1343.90075
[67] Caramia, M.; Mari, R., Enhanced exact algorithms for discrete bilevel linear problems, Optimization Letters, 9, 7, 1447-1468 (2015) · Zbl 1332.90170
[68] Cardinal, J.; Demaine, E. D.; Fiorini, S.; Joret, G.; Langerman, S.; Newman, I.; Weimann, O., The Stackelberg minimum spanning tree game, Algorithmica, 59, 2, 129-144 (2011) · Zbl 1207.90091
[69] URL: https://repositorio-aberto.up.pt/bitstream/10216/83362/2/126961.pdf
[70] Casorrán, C.; Fortz, B.; Labbé, M.; Ordóñez, F., A study of general and security Stackelberg game formulations, European Journal of Operational Research, 278, 3, 855-868 (2019) · Zbl 1431.91070
[71] Castelli, L.; Labbé, M.; Violin, A., A network pricing formulation for the revenue maximization of european air navigation service providers, Transportation Research Part C: Emerging Technologies, 33, 214-226 (2013)
[72] Castelli, L.; Labbé, M.; Violin, A., Network pricing problem with unit toll, Networks, 69, 1, 83-93 (2017) · Zbl 1390.90097
[73] Cerulli, M.; D’Ambrosio, C.; Liberti, L., Flying safely by bilevel programming, Advances in Optimization and Decision Science for Society, Services and Enterprises, 197-206 (2019), Springer · Zbl 1455.90021
[74] URL: https://hal.archives-ouvertes.fr/hal-02869699
[75] Clark, F. E., Remark on the constraint sets in linear programming, The American Mathematical Monthly, 68, 4, 351-352 (1961) · Zbl 0109.38204
[76] Clark, P. A., Bilevel programming for steady-state chemical process design-ii. Performance study for nondegenerate problems, Computers & Chemical Engineering, 14, 1, 99-109 (1990)
[77] Clark, P. A.; Westerberg, A. W., Optimization for design problems having more than one objective, Computers & Chemical Engineering, 7, 4, 259-278 (1983)
[78] Clark, P. A.; Westerberg, A. W., Bilevel programming for steady-state chemical process design-i. Fundamentals and algorithms, Computers & Chemical Engineering, 14, 1, 87-97 (1990)
[79] Colson, B.; Marcotte, P.; Savard, G., Bilevel programming: A survey, 4OR, 3, 2, 87-107 (2005) · Zbl 1134.90482
[80] Colson, B.; Marcotte, P.; Savard, G., An overview of bilevel optimization, Annals of Operations Research, 153, 1, 235-256 (2007) · Zbl 1159.90483
[81] Conforti, M.; Cornuejols, G.; Zambelli, G., Integer Programming, Graduate Texts in Mathematics, 271 (2014), Springer · Zbl 1307.90001
[82] Conitzer, V.; Sandholm, T., Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, 82-90 (2006)
[83] Cormican, K. J.; Morton, D. P.; Wood, R. K., Stochastic network interdiction, Operations Research, 46, 2, 184-197 (1998) · Zbl 0987.90516
[84] Costa, M.-C.; de Werra, D.; Picouleau, C., Minimum \(d\)-blockers and \(d\)-transversals in graphs, Journal of Combinatorial Optimization, 22, 4, 857-872 (2011) · Zbl 1263.90110
[85] Dan, T.; Lodi, A.; Marcotte, P., Joint location and pricing within a user-optimized environment, EURO Journal on Computational Optimization, 8, 1, 61-84 (2020) · Zbl 1441.90096
[86] Dan, T.; Marcotte, P., Competitive facility location with selfish users and queues, Operations Research, 67, 2, 479-497 (2019) · Zbl 1444.90024
[87] Della Croce, F.; Scatamacchia, R., Lower bounds and a new exact approach for the bilevel knapsack with interdiction constraints, (Lodi, A.; Nagarajan, V., Integer Programming and Combinatorial Optimization (2019), Springer International Publishing), 155-167 · Zbl 1436.90119
[88] Dempe, S., A simple algorithm for the linear bilevel programming problem, Optimization, 18, 3, 373-385 (1987) · Zbl 0634.90075
[89] Dempe, S., Foundations of Bilevel Programming (2002), Springer. · Zbl 1038.90097
[90] Dempe, S., Computing locally optimal solutions of the bilevel optimization problem using the KKT approach, (Khachay, M.; Kochetov, Y.; Pardalos, P., Mathematical Optimization Theory and Operations Research (2019), Springer International Publishing), 147-157 · Zbl 1443.90279
[91] Dempe, S., Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography, 581-672 (2020), Springer International Publishing · Zbl 1477.90101
[92] 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
[93] Dempe, S.; Franke, S., Solution of bilevel optimization problems using the KKT approach, Optimization, 68, 8, 1471-1489 (2019) · Zbl 1427.90230
[94] Dempe, S.; Ivanov, S.; Naumov, A., Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed-integer problem, Applied Stochastic Models in Business and Industry, 33, 5, 544-554 (2017) · Zbl 1407.90243
[95] Dempe, S.; Kalashnikov, V.; Pérez-Valdés, G. A.; Kalashnykova, N., Bilevel Programming Problems (2015), Springer. · Zbl 1338.90005
[96] Dempe, S.; Kue, F. M., Solving discrete linear bilevel optimization problems using the optimal value reformulation, Journal of Global Optimization, 68, 2, 255-277 (2017) · Zbl 1408.90195
[97] Dempe, S.; Mordukhovich, B. S.; Zemkoho, A. B., Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs, Optimization, 68, 2-3, 433-455 (2019) · Zbl 1414.49027
[98] URL: http://coral.ie.lehigh.edu/ ted/files/papers/ScottDeNegreDissertation11.pdf
[99] DeNegre, S. T.; Ralphs, T. K., A branch-and-cut algorithm for integer bilevel linear programs, Operations research and cyber-infrastructure, 65-78 (2009), Springer
[100] Deng, X., Complexity Issues in Bilevel Linear Programming, 149-164 (1998), Springer US · Zbl 0902.90119
[101] Dewez, S.; Labbé, M.; Marcotte, P.; Savard, G., New formulations and valid inequalities for a bilevel pricing problem, Operations Research Letters, 36, 2, 141-149 (2008) · Zbl 1144.90323
[102] Di Summa, M.; Grosso, A.; Locatelli, M., Branch and cut algorithms for detecting critical nodes in undirected graphs, Computational Optimization and Applications, 53, 3, 649-680 (2012) · Zbl 1264.90170
[103] Didi-Biha, M.; Marcotte, P.; Savard, G., Path-based formulations of a bilevel toll setting problem, Optimization with Multivalued Mappings, 29-50 (2006), Springer · Zbl 1196.90109
[104] Dinitz, M.; Gupta, A., Packing interdiction and partial covering problems, Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, 157-168 (2013), Springer-Verlag · Zbl 1372.90110
[105] Dobson, G.; Kalish, S., Positioning and pricing a product line, Marketing Science, 7, 2, 107-125 (1988)
[106] Dobson, G.; Kalish, S., Heuristics for pricing and positioning a product-line using conjoint and cost data, Management Science, 39, 2, 160-175 (1993)
[107] Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical Programming, 36, 3, 307-339 (1986) · Zbl 0619.90052
[108] Edmunds, T. A.; Bard, J. F., Algorithms for nonlinear bilevel mathematical programs, IEEE Transactions on Systems, Man, and Cybernetics, 21, 1, 83-89 (1991)
[109] Faísca, N. P.; Dua, V.; Rustem, B.; Saraiva, P. M.; Pistikopoulos, E. N., Parametric global optimisation for bilevel programming, Journal of Global Optimization, 38, 4, 609-623 (2007) · Zbl 1145.91016
[110] Fampa, M.; Barroso, L.; Candal, D.; Simonetti, L., Bilevel optimization applied to strategic pricing in competitive electricity markets, Computational Optimization and Applications, 39, 2, 121-142 (2008) · Zbl 1147.90392
[111] Fanghänel, D.; Dempe, S., Bilevel programming with discrete lower level problems, Optimization, 58, 8, 1029-1047 (2009) · Zbl 1175.90315
[112] Fernandes, C. G.; Ferreira, C. E.; Franco, A. J.; Schouery, R. C., The envy-free pricing problem, unit-demand markets and connections with the network pricing problem, Discrete Optimization, 22, 141-161 (2016) · Zbl 1390.91136
[113] Fioretto, F.; Mak, T. W.; Van Hentenryck, P., Privacy-preserving obfuscation of critical infrastructure networks, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, 1086-1092 (2019-07), International Joint Conferences on Artificial Intelligence Organization
[114] Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M., 2017a. Instances and solver software for mixed-integer bilevel linear problems. Last accessed 2020/12/21, URL: https://msinnl.github.io/pages/bilevel.html. · Zbl 1386.90085
[115] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research, 65, 6, 1615-1637 (2017) · Zbl 1386.90085
[116] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., On the use of intersection cuts for bilevel optimization, Mathematical Programming, 172, 1-2, 77-103 (2018) · Zbl 1406.90082
[117] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., Interdiction games and monotonicity, with application to knapsack problems, INFORMS Journal on Computing, 31, 2, 390-410 (2019) · Zbl 07281718
[118] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Mathematical Programming, 66, 1, 327-349 (1994) · Zbl 0833.90088
[119] Fliege, J.; Tin, A.; Zemkoho, A., Gauss-newton-type methods for bilevel optimization, Technical report. (2020)
[120] Fontaine, P.; Minner, S., Benders decomposition for discrete-continuous linear bilevel problems with application to traffic network design, Transportation Research Part B: Methodological, 70, 163-172 (2014)
[121] Fortuny-Amat, J.; McCarl, B., A representation and economic interpretation of a two-level programming problem, The Journal of the Operational Research Society, 32, 9, 783-792 (1981) · Zbl 0459.90067
[122] Franceschi, L.; Frasconi, P.; Salzo, S.; Grazzi, R.; Pontil, M., Bilevel programming for hyperparameter optimization and meta-learning, (Dy, J.; Krause, A., Proceedings of the 35th International Conference on Machine Learning (2018), PMLR), 1568-1577
[123] Fulkerson, D. R.; Harding, G. C., Maximizing the minimum source-sink path subject to a budget constraint, Mathematical Programming, 13, 1, 116-118 (1977) · Zbl 0366.90115
[124] Furini, F.; Ljubić, I.; Malaguti, E.; Paronuzzi, P., On integer and bilevel formulations for the \(k\)-vertex cut problem, Mathematical Programming Computation, 12, 133-164 (2020) · Zbl 1447.90011
[125] Furini, F.; Ljubić, I.; Malaguti, E.; Paronuzzi, P., Casting light on the hidden bilevel combinatorial structure of the capacitated vertex separator problem, Operations Research (2021)
[126] Furini, F.; Ljubić, I.; San Segundo, P.; Martin, S., The maximum clique interdiction problem, European Journal of Operational Research, 277, 1, 112-127 (2019) · Zbl 1430.90543
[127] Furini, F.; Ljubić, I.; San Segundo, P.; Zhao, Y., A branch-and-cut algorithm for the edge interdiction clique problem, European Journal of Operational Research, 294, 1, 54-69 (2020) · Zbl 1487.90618
[128] Gabriel, S. A.; Conejo, A. J.; Fuller, J. D.; Hobbs, B. F.; Ruiz, C., Complementarity modeling in energy markets, 180 (2012), Springer Science & Business Media
[129] Gairing, M.; Harks, T.; Klimm, M., Complexity and approximation of the continuous network design problem, SIAM Journal on Optimization, 27, 3, 1554-1582 (2017) · Zbl 1376.90068
[130] Garcés, L. P.; Conejo, A. J.; García-Bertrand, R.; Romero, R., A bilevel approach to transmission expansion planning within a market environment, IEEE Transactions on Power Systems, 24, 3, 1513-1522 (2009)
[131] Garcia-Herreros, P.; Zhang, L.; Misra, P.; Arslan, E.; Mehta, S.; Grossmann, I. E., Mixed-integer bilevel optimization for capacity planning with rational markets, Computers & Chemical Engineering, 86, 33-47 (2016)
[132] Geoffrion, A. M., Generalized Benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260 (1972) · Zbl 0229.90024
[133] Golden, B., A problem in network interdiction, Naval Research Logistics Quarterly, 25, 4, 711-713 (1978) · Zbl 0394.90038
[134] González-Díaz, J.; González-Rodríguez, B.; Leal, M.; Puerto, J., Global optimization for bilevel portfolio design: Economic insights from the Dow Jones index, Omega, 102353 (2020)
[135] Grimm, V.; Kleinert, T.; Liers, F.; Schmidt, M.; Zöttl, G., Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Optimization Methods and Software, 34, 2, 406-436 (2019) · Zbl 1407.90077
[136] Grimm, V.; Martin, A.; Schmidt, M.; Weibelzahl, M.; Zöttl, G., Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes, European Journal of Operational Research, 254, 2, 493-509 (2016) · Zbl 1346.91098
[137] Grimm, V.; Orlinskaya, G.; Schewe, L.; Schmidt, M.; Zöttl, G., Optimal design of retailer-prosumer electricity tariffs using bilevel optimization, Omega (2020)
[138] Grimm, V.; Schewe, L.; Schmidt, M.; Zöttl, G., A multilevel model of the European entry-exit gas market, Mathematical Methods of Operations Research, 89, 2, 223-255 (2019) · Zbl 1415.90012
[139] Gümüş, Z. H.; Ciric, A. R., Reactive distillation column design with vapor/liquid/liquid equilibria, Computers & Chemical Engineering, 21, S983-S988 (1997)
[140] Guruswami, V.; Hartline, J. D.; Karlin, A. R.; Kempe, D.; Kenyon, C.; McSherry, F., On profit-maximizing envy-free pricing, SODA, 5, 1164-1173 (2005) · Zbl 1297.91072
[141] Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM Journal on scientific and Statistical Computing, 13, 5, 1194-1217 (1992) · Zbl 0760.65063
[142] Harsanyi, J. C.; Selten, R., A generalized Nash solution for two-person bargaining games with incomplete information, Management Science, 18, 5-part-2, 80-106 (1972) · Zbl 0262.90087
[143] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., A parallel between two classes of pricing problems in transportation and marketing, Journal of Revenue and Pricing Management, 9, 1-2, 110-125 (2010)
[144] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., A polyhedral study of the network pricing problem with connected toll arcs, Networks, 55, 3, 234-246 (2010) · Zbl 1200.90031
[145] Heilporn, G.; Labbé, M.; Marcotte, P.; Savard, G., Valid inequalities and branch-and-cut for the clique pricing problem, Discrete Optimization, 8, 3, 393-410 (2011) · Zbl 1233.90095
[146] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Mathematical Programming, 137, 1, 257-288 (2013) · Zbl 1262.65065
[147] Horst, R.; Tuy, H., Global optimization: Deterministic approaches (2013), Springer Science & Business Media
[148] Israeli, E., System interdiction and defense (1999), Naval Postgraduate School., PhD thesis
[149] Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111 (2002) · Zbl 1027.90106
[150] Ivanov, S. V., A bilevel stochastic programming problem with random parameters in the follower’s objective function, Journal of Applied and Industrial Mathematics, 12, 4, 658-667 (2018) · Zbl 1438.90156
[151] Jain, M.; An, B.; Tambe, M., Security games applied to real-world: Research contributions and challenges, Moving Target Defense II, 15-39 (2013), Springer
[152] Jain, M.; Kardes, E.; Kiekintveld, C.; Ordónez, F.; Tambe, M., Security games with arbitrary schedules: A branch and price approach, AAAI (2010)
[153] Jain, M.; Ordonez, F.; Pita, J.; Portway, C.; Tambe, M.; Western, C.; Paruchuri, P.; Kraus, S., Robust solutions in Stackelberg games: Addressing boundedly rational human preference models, Association for the Advancement of Artificial Intelligence 4th Multidiciplinary Workshop on Advances in Preference Handling (2008)
[154] Janjarassuk, U.; Linderoth, J. T., Reformulation and sampling to solve a stochastic network interdiction problem, Networks, 52, 120-132 (2008) · Zbl 1173.90345
[155] Jenabi, M.; Fatemi Ghomi, S. M.T.; Smeers, Y., Bi-level game approaches for coordination of generation and transmission expansion planning within a market environment, IEEE Transactions on Power Systems, 28, 3, 2639-2650 (2013)
[156] Jeroslow, R. G., The polynomial hierarchy and a simple model for competitive analysis, Mathematical Programming, 32, 2, 146-164 (1985) · Zbl 0588.90053
[157] Jin, S.; Ryan, S. M., Capacity expansion in the integrated supply network for an electricity market, IEEE Transactions on Power Systems, 26, 4, 2275-2284 (2011)
[158] Joret, G., Stackelberg network pricing is hard to approximate, Networks, 57, 2, 117-120 (2011) · Zbl 1207.90092
[159] (Jünger, M.; Liebling, T. M.; Naddef, D.; Nemhauser, G. L.; Pulleyblank, W. R.; Reinelt, G.; Rinaldi, G.; Wolsey, L. A., 50 Years of integer programming 1958-2008: From the early years to the state-of-the-art (2010), Springer)
[160] Kelley, J. E., The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics, 8, 4, 703-712 (1960) · Zbl 0098.12104
[161] Kiekintveld, C.; Jain, M.; Tsai, J.; Pita, J.; Ordóñez, F.; Tambe, M., Computing optimal randomized resource allocations for massive security games, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, 689-696 (2009)
[162] Kleinert, T.; Grimm, V.; Schmidt, M., Outer approximation for global optimization of mixed-integer quadratic bilevel problems, Mathematical Programming, 188, 461-521 (2021) · Zbl 1473.90107
[163] Kleinert, T.; Labbé, M.; Plein, F.; Schmidt, M., Closing the gap in linear bilevel optimization: A new valid primal-dual inequality, Optimization Letters, 15, 1027-1040 (2020) · Zbl 1470.90057
[164] Kleinert, T.; Labbé, M.; Plein, F.; Schmidt, M., There’s no free lunch: On the hardness of choosing a correct big-M in bilevel optimization, Operations Research, 68, 6, 1716-1721 (2020) · Zbl 1457.90094
[165] Kleinert, T.; Schmidt, M., Computing stationary points of bilevel problems with a penalty alternating direction method, INFORMS Journal on Computing, 33, 1, 198-215 (2019) · Zbl 07362311
[166] Kleinert, T.; Schmidt, M., Global optimization of multilevel electricity market models including network design and graph partitioning, Discrete Optimization, 33, 43-69 (2019) · Zbl 1474.90302
[167] URL: http://www.optimization-online.org/DB_HTML/2020/10/8065.html
[168] Kleniati, P.-M.; Adjiman, C. S., Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development, Journal of Global Optimization, 60, 3, 425-458 (2014) · Zbl 1310.90093
[169] Kleniati, P.-M.; Adjiman, C. S., Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part II: Convergence analysis and numerical results, Journal of Global Optimization, 60, 3, 459-481 (2014) · Zbl 1310.90092
[170] Kleniati, P.-M.; Adjiman, C. S., A generalization of the branch-and-sandwich algorithm: From continuous to mixed-integer nonlinear bilevel problems, Computers & Chemical Engineering, 72, 373-386 (2015)
[171] Klotz, E., 2017. Performance tuning for CPLEX’s spatial branch-and-bound solver for global nonconvex (mixed integer) quadratic programs. URL: http://orwe-conference.mines.edu/files/IOS2018SpatialPerfTuning.pdf
[172] Kolstad, C. D., A review of the literature on bi-level mathematical programming, Technical report (1985), Los Alamos National Laboratory Los Alamos, NM
[173] Köppe, M.; Queyranne, M.; Ryan, C. T., Parametric integer programming algorithm for bilevel mixed integer programs, Journal of Optimization Theory and Applications, 146, 1, 137-150 (2010) · Zbl 1197.90307
[174] Korzhyk, D.; Conitzer, V.; Parr, R., Complexity of computing optimal Stackelberg strategies in security resource allocation games, Twenty-Fourth AAAI Conference on Artificial Intelligence (2010)
[175] Korzhyk, D.; Yin, Z.; Kiekintveld, C.; Conitzer, V.; Tambe, M., Stackelberg vs. Nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness, Journal of Artificial Intelligence Research, 41, 297-327 (2011) · Zbl 1219.91032
[176] Labbé, M.; Marcotte, P.; Savard, G., A bilevel model of taxation and its application to optimal highway pricing, Management Science, 44, 12-part-1, 1608-1622 (1998) · Zbl 0989.90014
[177] Labbé, M.; Pozo, M.; Puerto, J., Computational comparisons of different formulations for the Stackelberg minimum spanning tree game, International Transactions in Operational Research, 28, 1, 48-69 (2021) · Zbl 07768498
[178] Labbé, M.; Violin, A., Bilevel programming and price setting problems, 4OR, 11, 1, 1-30 (2013) · Zbl 1259.90112
[179] Lagos, F.; Ordóñez, F.; Labbé, M., A branch and price algorithm for a Stackelberg security game, Computers & Industrial Engineering, 111, 216-227 (2017)
[180] Lalou, M.; Tahraoui, M. A.; Kheddouci, H., The critical node detection problem in networks: A survey, Computer Science Review, 28, 92-117 (2018) · Zbl 1387.68186
[181] Land, A. H.; Doig, A. G., An automatic method of solving discrete programming problems, Econometrica, 28, 3, 497-520 (1960) · Zbl 0101.37004
[182] Leal, M.; Ponce, D.; Puerto, J., Portfolio problems with two levels decision-makers: Optimal portfolio selection with pricing decisions on transaction costs, European Journal of Operational Research, 284, 2, 712-727 (2020) · Zbl 1441.91068
[183] LeBlanc, L. J.; Boyce, D. E., A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows, Transportation Research Part B: Methodological, 20, 3, 259-265 (1986)
[184] Lee, J., Leyffer, S. (Eds.). 2012. Mixed integer nonlinear programming. The IMA Volumes in Mathematics and its Applications, 154. Springer New York. doi:10.1007/978-1-4614-1927-3.
[185] Letchford, J.; Conitzer, V., Solving security games on graphs via marginal probabilities, AAAI (2013)
[186] Lim, C.; Smith, J. C., Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Transactions, 39, 1, 15-26 (2007)
[187] Lin, K.-C.; Chern, M.-S., The most vital edges in the minimum spanning tree problem, Information Processing Letters, 45, 1, 25-31 (1993) · Zbl 0768.68051
[188] Liu, J.; Fan, Y.; Chen, Z.; Zheng, Y., Pessimistic bilevel optimization: A survey, International Journal of Computational Intelligence Systems, 11, 725-736 (2018)
[189] Liu, J.; Fan, Y.; Chen, Z.; Zheng, Y., Methods for Pessimistic Bilevel Optimization, 403-420 (2020), Springer, Cham · Zbl 1481.90292
[190] Online first
[191] Lodi, A.; Ralphs, T. K.; Woeginger, G. J., Bilevel programming and the separation problem, Mathematical Programming, 146, 1, 437-458 (2014) · Zbl 1401.90128
[192] Lozano, L.; Smith, J. C., A backward sampling framework for interdiction problems with fortification, INFORMS Journal on Computing, 29, 1, 123-139 (2017) · Zbl 1414.91086
[193] Lozano, L.; Smith, J. C., A value-function-based exact approach for the bilevel mixed-integer programming problem, Operations Research, 65, 3, 768-786 (2017) · Zbl 1387.90161
[194] Luo, Z.-Q.; Pang, J.-S.; Ralph, D., Mathematical programs with equilibrium constraints (1996), Cambridge University Press
[195] Lv, Y.; Hu, T.; Wang, G.; Wan, Z., A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming, Applied Mathematics and Computation, 188, 1, 808-813 (2007) · Zbl 1137.90617
[196] Marcotte, P., Network design problem with congestion effects: A case of bilevel programming, Mathematical Programming, 34, 2, 142-162 (1986) · Zbl 0604.90053
[197] Marcotte, P.; Mercier, A.; Savard, G.; Verter, V., Toll policies for mitigating hazardous materials transport risk, Transportation Science, 43, 2, 228-243 (2009)
[198] Marcotte, P.; Savard, G., A note on the pareto optimality of solutions to the linear bilevel programming problem, Computers and Operations Research, 18, 4, 355-359 (1991) · Zbl 0717.90045
[199] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part i-convex underestimating problems, Mathematical Programming, 10, 1, 147-175 (1976) · Zbl 0349.90100
[200] McNaughton, R., Scheduling with deadlines and loss functions, Management Science, 6, 1, 1-12 (1959) · Zbl 1047.90504
[201] Mersha, A. G.; Dempe, S., Linear bilevel programming with upper level constraints depending on the lower level solution, Applied Mathematics and Computation, 180, 1, 247-254 (2006) · Zbl 1102.90070
[202] Migdalas, A., Bilevel programming in traffic planning: Models, methods and challenge, Journal of Global Optimization, 7, 4, 381-405 (1995) · Zbl 0844.90050
[203] Mitsos, A., Global solution of nonlinear mixed-integer bilevel programs, Journal of Global Optimization, 47, 4, 557-582 (2010) · Zbl 1202.90217
[204] URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.4195&rep=rep1&type=pdf
[205] Mitsos, A.; Lemonidis, P.; Barton, P. I., Global solution of bilevel programs with a nonconvex inner program, Journal of Global Optimization, 42, 4, 475-513 (2008) · Zbl 1163.90700
[206] Moore, J. T.; Bard, J. F., The mixed integer linear bilevel programming problem, Operations Research, 38, 5, 911-921 (1990) · Zbl 0723.90090
[207] Morais, V.; da Cunha, A. S.; Mahey, P., A branch-and-cut-and-price algorithm for the Stackelberg minimum spanning tree game, Electronic Notes in Discrete Mathematics, 52, 309-316 (2016) · Zbl 1351.90054
[208] Morales, J. M.; Pinson, P.; Madsen, H., A transmission-cost-based model to estimate the amount of market-integrable wind resources, IEEE Transactions on Power Systems, 27, 2, 1060-1069 (2012)
[209] Motto, A. L.; Arroyo, J. M.; Galiana, F. D., A mixed-integer LP procedure for the analysis of electric grid security under disruptive threat, IEEE Transactions on Power Systems, 20, 3, 1357-1365 (2005)
[210] Myklebust, T. G.; Sharpe, M.; Tunçel, L., Efficient heuristic algorithms for maximum utility product pricing problems, Computers & Operations Research, 69, 25-39 (2016) · Zbl 1349.90865
[211] Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer · Zbl 1104.65059
[212] Pajouh, F. M., Minimum cost edge blocker clique problem, Annals of Operations Research, 294, 1, 345-376 (2020) · Zbl 1456.90168
[213] Pajouh, F. M.; Boginski, V.; Pasiliao, E. L., Minimum vertex blocker clique problem, Networks, 64, 1, 48-64 (2014) · Zbl 1390.90183
[214] Pajouh, F. M.; Walteros, J. L.; Boginski, V.; Pasiliao, E. L., Minimum edge blocker dominating set problem, European Journal of Operational Research, 247, 1, 16-26 (2015) · Zbl 1346.90788
[215] Pandzic, H.; Conejo, A. J.; Kuzle, I.; Caro, E., Yearly maintenance scheduling of transmission lines within a market environment, IEEE Transactions on Power Systems, 27, 1, 407-415 (2012)
[216] Paruchuri, P.; Kraus, S.; Pearce, J. P.; Marecki, J.; Tambe, M.; Ordonez, F., Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games, (Padgham; Parkes; Mueller; Parsons, Proc. of AAMAS 2008 (2008), Citeseer)
[217] Paulavičius, R.; Adjiman, C. S., New bounding schemes and algorithmic options for the branch-and-sandwich algorithm, Journal of Global Optimization, 1-29 (2020) · Zbl 1442.90151
[218] Paulavičius, R.; Gao, J.; Kleniati, P.-M.; Adjiman, C., Basbl: Branch-and-sandwich bilevel solver. implementation and computational study with the basblib test set, Computers & Chemical Engineering, 106609 (2020)
[219] Paulavičius, R.; Adjiman, C. S., Basblib - a library of bilevel test problems (version v2.3), Zenodo. (2019)
[220] Pineda, S.; Bylling, H.; Morales, J., Efficiently solving linear bilevel programming problems using off-the-shelf optimization software, Optimization and Engineering, 19, 1, 187-211 (2018) · Zbl 1391.90004
[221] Pineda, S.; Morales, J. M., Solving linear bilevel problems using big-Ms: Not all that glitters is gold, IEEE Transactions on Power Systems (2019)
[222] Pita, J.; Jain, M.; Marecki, J.; Ordóñez, F.; Portway, C.; Tambe, M.; Western, C.; Paruchuri, P.; Kraus, S., Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track, 125-132 (2008)
[223] Pita, J.; Jain, M.; Tambe, M.; Ordóñez, F.; Kraus, S., Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition, Artificial Intelligence, 174, 15, 1142-1171 (2010) · Zbl 1237.91065
[224] Poirion, P.; Toubaline, S.; D’Ambrosio, C.; Liberti, L., Algorithms and applications for a class of bilevel milps, Discrete Applied Mathematics, 272, 75-89 (2020) · Zbl 1435.90086
[225] Ralphs, T. K., 2018. Mibs. Last accessed 2020/12/21, URL: https://msinnl.github.io/pages/bilevel.html.
[226] Ralphs, T. K., 2020. Cor@l: Bilevel optimization problem library. URL: http://coral.ise.lehigh.edu/data-sets/bilevel-instances
[227] Reisi, M.; Gabriel, S. A.; Fahimnia, B., Supply chain competition on shelf space and pricing for soft drinks: A bilevel optimization approach, International Journal of Production Economics, 211, 237-250 (2019)
[228] Roch, S.; Savard, G.; Marcotte, P., An approximation algorithm for Stackelberg network pricing, Networks, 46, 1, 57-67 (2005) · Zbl 1072.90004
[229] Ruiz, C.; Conejo, A. J., Pool strategy of a producer with endogenous formation of locational marginal prices, IEEE Transactions on Power Systems, 24, 4, 1855-1866 (2009)
[230] Ruiz, C.; Conejo, A. J.; Smeers, Y., Equilibria in an oligopolistic electricity pool with stepwise offer curves, IEEE Transactions on Power Systems, 27, 2, 752-761 (2012)
[231] Rutenburg, V., Propositional truth maintenance systems: Classification and complexity analysis, Annals of Mathematics and Artificial Intelligence, 10, 3, 207-231 (1994) · Zbl 0855.68076
[232] FOCAPO 2003 Special issue
[233] Saharidis, G. K.; Ierapetritou, M. G., Resolution method for mixed integer bi-level linear problems based on decomposition technique, Journal of Global Optimization, 44, 1, 29-51 (2009) · Zbl 1172.90451
[234] Salmeron, J.; Wood, K.; Baldick, R., Worst-case interdiction analysis of large-scale electric power grids, IEEE Transactions on Power Systems, 24, 1, 96-104 (2009)
[235] Salmeron, J.; Wood, R. K., The value of recovery transformers in protecting an electric transmission grid against attack, IEEE Transactions on Power Systems, 30, 5, 2396-2403 (2015)
[236] Scaparra, M. P.; Church, R. L., A bilevel mixed-integer program for critical infrastructure protection planning, Computers & Operations Research, 35, 6, 1905-1923 (2008) · Zbl 1139.90439
[237] Schewe, L.; Schmidt, M.; Thürauf, J., Global optimization for the multilevel European gas market system with nonlinear flow models on trees, Journal of Global Optimization (2021), forthcoming
[238] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 11, 4, 918-936 (2001) · Zbl 1010.90086
[239] Shen, S.; Smith, J. C., Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks, 60, 2, 103-119 (2012) · Zbl 1251.90376
[240] Shen, S.; Smith, J. C.; Goli, R., Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optimization, 9, 3, 172-188 (2012) · Zbl 1254.90280
[241] URL: http://www.optimization-online.org/DB_HTML/2020/06/7874.html
[242] Shieh, E.; An, B.; Yang, R.; Tambe, M.; Baldwin, C.; DiRenzo, J.; Maule, B.; Meyer, G., Protect: A deployed game theoretic system to protect the ports of the united states, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, 13-20 (2012)
[243] Shioda, R.; Tunçel, L.; Myklebust, T. G., Maximum utility product pricing models and algorithms based on reservation price, Computational Optimization and Applications, 48, 2, 157-198 (2011) · Zbl 1231.91105
[244] Siddiqui, S.; Gabriel, S. A., An SOS1-based approach for solving MPECs with a natural gas market application, Networks and Spatial Economics, 13, 2, 205-227 (2013) · Zbl 1332.91075
[245] Sinha, A.; Fang, F.; An, B.; Kiekintveld, C.; Tambe, M., Stackelberg security games: Looking beyond a decade of success, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18),Stockholm, Sweden, July 13-19, 5494-5501 (2018), IJCAI
[246] Sinha, A.; Malo, P.; Deb, K., A review on bilevel optimization: From classical to evolutionary approaches and applications, IEEE Transactions on Evolutionary Computation, 22, 2, 276-295 (2018)
[247] Sinha, A.; Malo, P.; Xu, P.; Deb, K., A bilevel optimization approach to automated parameter tuning, Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, 847-854 (2014), Association for Computing Machinery
[248] Sinnl, M., 2020. Bilevel integer programming and interdiction problems. Accessed: 2020-12-21, URL: https://msinnl.github.io/pages/bilevel.html.
[249] Smith, J. C.; Song, Y., A survey of network interdiction models and algorithms, European Journal of Operational Research, 283, 3, 797-811 (2020) · Zbl 1441.90048
[250] Still, G., Linear bilevel problems: Genericity results and an efficient method for computing local minima, Mathematical Methods of Operations Research, 55, 3, 383-400 (2002) · Zbl 1115.90364
[251] Tahernejad, S.; Ralphs, T. K.; DeNegre, S. T., A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation, Mathematical Programming Computation, 12, 529-568 (2020) · Zbl 1458.90488
[252] Tambe, M., Security and game theory: algorithms, deployed systems, lessons learned (2011), Cambridge university press · Zbl 1235.91005
[253] Tang, Y.; Richard, J. P.; Smith, J. C., A class of algorithms for mixed-integer bilevel min-max optimization, Journal of Global Optimization, 66, 2, 225-262 (2016) · Zbl 1380.90197
[254] Van Hoesel, S., An overview of Stackelberg pricing in networks, European Journal of Operational Research, 189, 3, 1393-1402 (2008) · Zbl 1146.91018
[255] Vicente, L.; Calamai, P. H., Bilevel and multilevel programming: A bibliography review, Journal of Global optimization, 5, 3, 291-306 (1994) · Zbl 0822.90127
[256] Vicente, L.; Savard, G.; Júdice, J., Descent approaches for quadratic bilevel programming, Journal of Optimization Theory and Applications, 81, 2, 379-399 (1994) · Zbl 0819.90076
[257] Vicente, L.; Savard, G.; Júdice, J., Discrete linear bilevel programming problem, Journal of Optimization Theory and Applications, 89, 3, 597-614 (1996) · Zbl 0851.90084
[258] von Stackelberg, H., Marktform und Gleichgewicht (1934), Springer · Zbl 1405.91003
[259] von Stackelberg, H., Theory of the market economy (1952), Oxford University Press
[260] Wang, L.; Xu, P., The watermelon algorithm for the bilevel integer linear programming problem, SIAM Journal on Optimization, 27, 3, 1403-1430 (2017) · Zbl 1373.90078
[261] Wang, Z.; Yin, Y.; An, B., Computing optimal monitoring strategy for detecting terrorist plots, (Schuurmans, D.; Wellman, M. P., Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA (2016), AAAI Press), 637-643
[262] Washburn, A.; Wood, R. K., Two-person zero-sum games for network interdiction, Operations Research, 43, 2, 243-251 (1995) · Zbl 0832.90124
[263] Wen, U.-P.; Hsu, S.-T., Linear bi-level programming problems – a review, The Journal of the Operational Research Society, 42, 2, 125-133 (1991) · Zbl 0722.90046
[264] Wiesemann, W.; Tsoukalas, A.; Kleniati, P.; Rustem, B., Pessimistic bilevel optimization, SIAM Journal on Optimization, 23, 1, 353-380 (2013) · Zbl 1270.90088
[265] Williams, A., Boundedness relations for linear constraint sets, Linear Algebra and its Applications, 3, 2, 129-141 (1970) · Zbl 0201.22003
[266] Wogrin, S.; Pineda, S.; Tejada-Arango, D. A., Applications of Bilevel Optimization in Energy and Electricity Markets, 139-168 (2020), Springer International Publishing
[267] Wolsey, L. A., Integer programming (1998), John Wiley & Sons · Zbl 0930.90072
[268] Wood, R. K., Deterministic network interdiction, Mathematical and Computer Modelling, 17, 2, 1-18 (1993) · Zbl 0800.90772
[269] Wood, R. K., Bilevel Network Interdiction Models: Formulations and Solutions (2011), American Cancer Society
[270] Wu, S.; Marcotte, P.; Chen, Y., A cutting plane method for linear bilevel programs, Systems Science and Mathematical Sciences, 11, 125-133 (1998) · Zbl 0915.90205
[271] Xu, P., Three essays on bilevel optimization algorithms and applications (2012), Iowa State University., PhD thesis
[272] Xu, P.; Wang, L., An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Computers & Operations Research, 41, 309-318 (2014) · Zbl 1348.90496
[273] Yang, R.; Ford, B. J.; Tambe, M.; Lemieux, A., Adaptive resource allocation for wildlife protection against illegal poachers, AAMAS, 453-460 (2014)
[274] Yanikoglu, I.; Kuhn, D., Decision rule bounds for two-stage stochastic bilevel programs, SIAM Journal on Optimization, 28, 1, 198-222 (2018) · Zbl 1392.90086
[275] Ye, J. J.; Zhu, D. L., Optimality conditions for bilevel programming problems, Optimization, 33, 1, 9-27 (1995) · Zbl 0820.65032
[276] Yin, Z.; Jiang, A. X.; Johnson, M. P.; Kiekintveld, C.; Leyton-Brown, K.; Sandholm, T.; Tambe, M.; Sullivan, J. P., Trusts: Scheduling randomized patrols for fare inspection in transit systems, IAAI (2012)
[277] Yin, Z.; Tambe, M., A unified method for handling discrete and continuous uncertainty in bayesian Stackelberg games, Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, 855-862 (2012)
[278] Yue, D.; Gao, J.; Zeng, B.; You, F., A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs, Journal of Global Optimization, 73, 1, 27-57 (2019) · Zbl 1417.90106
[279] Sustainability & Energy Systems
[280] Zare, M. H.; Borrero, J. S.; Zeng, B.; Prokopyev, O. A., A note on linearized reformulations for a class of bilevel linear integer problems, Annals of Operations Research, 272, 1-2, 99-117 (2019) · Zbl 1411.90228
[281] URL: http://www.optimization-online.org/DB_FILE/2014/07/4455.pdf
[282] Zenklusen, R., Matching interdiction, Discrete Applied Mathematics, 158, 15, 1676-1690 (2010) · Zbl 1208.05120
[283] Zenklusen, R.; Ries, B.; Picouleau, C.; de Werra, D.; Costa, M.-C.; Bentz, C., Blockers and transversals, Discrete Mathematics, 309, 13, 4306-4314 (2009) · Zbl 1204.05085
[284] Zhang, Y.; Snyder, L. V.; Ralphs, T. K.; Xue, Z., The competitive facility location problem under disruption risks, Transportation Research Part E: Logistics and Transportation Review, 93, 453-473 (2016)
[285] Zhao, L.; Zeng, B., Vulnerability analysis of power grids with line switching, IEEE Transactions on Power Systems, 28, 3, 2727-2736 (2013)
[286] Zhou, S.; Zemkoho, A. B.; Tin, A., BOLIB: Bilevel Optimization LIBrary of test problems, 513-560 (2020), Springer International Publishing · Zbl 1477.90002
[287] Zugno, M.; Morales, J. M.; Pinson, P.; Madsen, H., A bilevel model for electricity retailers’ participation in a demand response market environment, Energy Economics, 36, 182-197 (2013)
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.