×

Outer approximation for global optimization of mixed-integer quadratic bilevel problems. (English) Zbl 1473.90107

Summary: Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.

MSC:

90C20 Quadratic programming
90C11 Mixed integer programming
90C25 Convex programming
90C46 Optimality conditions and duality in mathematical programming

Software:

Bonmin; FilMINT

References:

[1] Abhishek, K.; Leyffer, S.; Linderoth, J., FilMINT: an outer approximationbased solver for convex mixed-integer nonlinear programs, INFORMS J. Comput., 22, 4, 555-567 (2010) · Zbl 1243.90142 · doi:10.1287/ijoc.1090.0373
[2] Arroyo, JM, Bilevel programming applied to power system vulnerability analysis under multiple contingencies, IET Gener. Transm. Distrib., 4, 2, 178-190 (2010) · doi:10.1049/iet-gtd.2009.0098
[3] Avraamidou, S.; Pistikopoulos, EN, A Multi-Parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems, Comput. Chem. Eng., 125, 98-113 (2019) · Zbl 1432.90088 · doi:10.1016/j.compchemeng.2019.01.021
[4] Baggio, A., Carvalho, M., Lodi, A., Tramontani, A.: Multilevel approaches for the critical node problem. Technical report, École Polytechnique de Montréal (2016) · Zbl 1470.91037
[5] Bard, JF, Convex two-level optimization, Math. Program., 40, 1, 15-27 (1988) · Zbl 0655.90060 · doi:10.1007/BF01580720
[6] Bard, JF; Moore, JT, A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Stat. Comput., 11, 2, 281-292 (1990) · Zbl 0702.65060 · doi:10.1137/0911017
[7] 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 · doi:10.1017/S0962492913000032
[8] Bonami, P.; Biegler, LT; Conn, AR; Cornuéjols, G.; Grossmann, IE; Laird, CD; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[9] Böttger, T., Grimm, V., Kleinert, T., Schmidt, M.: The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market. Technical report (2020). http://www.optimization-online.org/DB_HTML/2020/06/7851.html
[10] Boyd, S.; Vandenberghe, L., Convex Optim. (2004) · Zbl 1058.90049 · doi:10.1017/cbo9780511804441
[11] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, GJ, Bilevel knapsack with interdiction constraints, INFORMS J. Comput., 28, 2, 319-333 (2016) · Zbl 1343.90075 · doi:10.1287/ijoc.2015.0676
[12] Daxhelet, O.; Smeers, Y., The EU regulation on cross-border trade of electricity: a two-stage equilibrium model, Eur. J. Oper. Res., 181, 3, 1396-1412 (2007) · Zbl 1123.91314 · doi:10.1016/j.ejor.2005.12.040
[13] Dempe, S.: Foundations of Bilevel Programming. Springer, Berlin (2002). doi:10.1007/b101970 · Zbl 1038.90097
[14] Dempe, S.; Kalashnikov, V.; Pérez-Valdés, GA; Kalashnykova, N., Bilevel Program. Problems (2015) · Zbl 1338.90005 · doi:10.1007/978-3-662-45827-3
[15] Dempe, S.; Zemkoho, AB, Bilevel road pricing: theoretical analysis and optimality conditions, Ann. Oper. Res., 196, 1, 223-240 (2012) · Zbl 1274.90374 · doi:10.1007/s10479-011-1023-z
[16] DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. thesis. Lehigh University (2011)
[17] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[18] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[19] Edmunds, TA; Bard, JF, Algorithms for nonlinear bilevel mathematical programs, IEEE Trans. Syst. Man Cybern., 21, 1, 83-89 (1991) · doi:10.1109/21.101139
[20] J. Egerer, V. Grimm, T. Kleinert, M. Schmidt, G. Zöttl. The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment. Eur. J. Oper. Res. (2020). doi:10.1016/j.ejor.2020.10.055 · Zbl 1487.90658
[21] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bilevel linear programs, Oper. Res., 65, 6, 1615-1637 (2017) · Zbl 1386.90085 · doi:10.1287/opre.2017.1650
[22] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., Interdiction games and monotonicity, with application to knapsack problems, INFORMS J. Comput., 31, 2, 390-410 (2019) · Zbl 07281718 · doi:10.1287/ijoc.2018.0831
[23] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., On the use of intersection cuts for bilevel optimization, Math. Program., 172, 1-2, 77-103 (2018) · Zbl 1406.90082 · doi:10.1007/s10107-017-1189-5
[24] Fischetti, M.; Monaci, M.; Sinnl, M., A dynamic reformulation heuristic for generalized interdiction problems, Eur. J. Oper. Res., 267, 1, 40-51 (2018) · Zbl 1403.90524 · doi:10.1016/j.ejor.2017.11.043
[25] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1, 327-349 (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153
[26] Fortuny-Amat, J.; McCarl, B., A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc., 32, 9, 783-792 (1981) · Zbl 0459.90067 · doi:10.1057/jors.1981.156
[27] Garcés, LP; Conejo, AJ; García-Bertrand, R.; Romero, R., A bilevel approach to transmission expansion planning within a market environment, IEEE Trans. Power Syst., 24, 3, 1513-1522 (2009) · doi:10.1109/TPWRS.2009.2021230
[28] Garcia-Herreros, P.; Zhang, L.; Misra, P.; Arslan, E.; Mehta, S.; Grossmann, IE, Mixed-integer bilevel optimization for capacity planning with rational markets, Comput. Chem. Eng., 86, 33-47 (2016) · doi:10.1016/j.compchemeng.2015.12.007
[29] Grimm, V.; Grübel, J.; Schewe, L.; Schmidt, M.; Zöttl, G., Nonconvex equilibrium models for gas market analysis: failure of standard techniques and alternative modeling approaches, Eur. J. Oper. Res., 273, 3, 1097-1108 (2019) · Zbl 1403.90201 · doi:10.1016/j.ejor.2018.09.016
[30] Grimm, V., Orlinskaya, G., Schewe, L., Schmidt, M., Zöttl, G.: Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization. In: Omega (2020). doi:10.1016/j.omega.2020.102327
[31] Grimm, V., Schewe, L., Schmidt, M., Zöttl, G (2018) A multilevel model of the European entry-exit gas market. Math. Methods Oper. Res. doi:10.1007/s00186-018-0647-z · Zbl 1415.90012
[32] Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J. Sci. Stat. Comput., 13, 5, 1194-1217 (1992) · Zbl 0760.65063 · doi:10.1137/0913069
[33] He, X.; Li, C.; Huang, T.; Li, C., Neural network for solving convex quadratic bilevel programming problems, Neural Netw., 51, 17-25 (2014) · Zbl 1298.90069 · doi:10.1016/j.neunet.2013.11.015
[34] Hu, X.; Ralph, D., Using EPECs to model bilevel games in restructured electricity markets with locational prices, Oper. Res., 55, 5, 809-827 (2007) · Zbl 1167.91357 · doi:10.1287/opre.1070.0431
[35] Jeroslow, RG, The polynomial hierarchy and a simple model for competitive analysis, Math. Program., 32, 2, 146-164 (1985) · Zbl 0588.90053 · doi:10.1007/BF01586088
[36] Kelley, JE Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053
[37] 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. Oper. Res. (2020). doi:10.1287/opre.2019.1944 · Zbl 1457.90094
[38] Kleinert, T.; Schmidt, M., Computing feasible points of bilevel problems with a penalty alternating direction method, INFORMS J. Comput. (2020) · Zbl 07362311 · doi:10.1287/ijoc.2019.0945
[39] Kleinert, T.; Schmidt, M., Global optimization of multilevel electricity market models including network design and graph partitioning, Discrete Optim., 33, 43-69 (2019) · Zbl 1474.90302 · doi:10.1016/j.disopt.2019.02.002
[40] Labbé, M.; Marcotte, P.; Savard, G., A bilevel model of taxation and its application to optimal highway pricing, Manag. Sci., 44, 12, 1608-1622 (1998) · Zbl 0989.90014 · doi:10.1287/mnsc.44.12.1608
[41] Lozano, L.; Smith, JC, A value-function-based exact approach for the bilevel mixed-integer programming problem, Oper. Res., 65, 3, 768-786 (2017) · Zbl 1387.90161 · doi:10.1287/opre.2017.1589
[42] Lv, Y.; Chen, Z.; Wan, Z., A neural network for solving a convex quadratic bilevel programming problem, J. Comput. Appl. Math., 234, 2, 505-511 (2010) · Zbl 1196.65103 · doi:10.1016/j.cam.2009.12.041
[43] Moore, JT; Bard, JF, The mixed integer linear bilevel programming problem, Oper. Res., 38, 5, 911-921 (1990) · Zbl 0723.90090 · doi:10.1287/opre.38.5.911
[44] Morales, JM; Pinson, P.; Madsen, H., A transmission-cost-based model to estimate the amount of market-integrable wind resources, IEEE Trans. Power Syst., 27, 2, 1060-1069 (2012) · doi:10.1109/TPWRS.2011.2177281
[45] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), Berlin: Springer, Berlin · Zbl 1104.65059 · doi:10.1007/978-0-387-40065-5
[46] Pineda, S.; Morales, JM, Solving linear bilevel problems using Big-Ms: not all that glitters is gold, IEEE Trans. Power Syst. (2019) · doi:10.1109/TPWRS.2019.2892607
[47] Quesada, I.; Grossmann, IE, An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 10-11, 937-947 (1992) · doi:10.1016/0098-1354(92)80028-8
[48] Ralphs, T.: Cor@l: Bilevel Optimization Problem Library. http://coral.ise.lehigh.edu/data-sets/bilevel-instances/. Accessed 12 Dec 2019
[49] Regionales Rechenzentrum Erlangen. Woodcrest Cluster. https://www.anleitungen.rrze.fau.de/hpc/woody-cluster/. Accessed 12 Dec 2019
[50] 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). doi:10.1007/s12532-020-00183-6 · Zbl 1458.90488
[51] Tang, Y.; Richard, J-PP; Smith, JC, A class of algorithms for mixedinteger bilevel min-max optimization, J. Global Optim., 66, 2, 225-262 (2015) · Zbl 1380.90197 · doi:10.1007/s10898-015-0274-7
[52] Vanderbei, RJ, Linear Program. (2014) · Zbl 1299.90243 · doi:10.1007/978-1-4614-7630-6
[53] Vicente, L.; Savard, G.; Júdice, J., Descent approaches for quadratic bilevel programming, J. Optim. Theory Appl., 81, 2, 379-399 (1994) · Zbl 0819.90076 · doi:10.1007/BF02191670
[54] Xu, P.; Wang, L., An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Comput. Oper. Res., 41, 309-318 (2014) · Zbl 1348.90496 · doi:10.1016/j.cor.2013.07.016
[55] Zare, MH; Borrero, JS; Zeng, B.; Prokopyev, OA, A note on linearized reformulations for a class of bilevel linear integer problems, Ann. Oper. Res., 272, 1-2, 99-117 (2019) · Zbl 1411.90228 · doi:10.1007/s10479-017-2694-x
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.