{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T02:59:45Z","timestamp":1787799585738,"version":"build-2784847793"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T00:00:00Z","timestamp":1605052800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T00:00:00Z","timestamp":1605052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TRR 154"],"award-info":[{"award-number":["TRR 154"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Bayerische Staatsregierung","award":["Energie Campus N\u00fcrnberg"],"award-info":[{"award-number":["Energie Campus N\u00fcrnberg"]}]},{"DOI":"10.13039\/501100002661","name":"Fonds de la Recherche Scientifique","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002661","name":"Fonds de la Recherche Scientifique","doi-asserted-by":"crossref","award":["Grant(s) no PDR T0098.18"],"award-info":[{"award-number":["Grant(s) no PDR T0098.18"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush\u2013Kuhn\u2013Tucker conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem\u2019s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.<\/jats:p>","DOI":"10.1007\/s11590-020-01660-6","type":"journal-article","created":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T11:02:56Z","timestamp":1605092576000},"page":"1027-1040","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Closing the gap in linear bilevel optimization: a new valid primal-dual inequality"],"prefix":"10.1007","volume":"15","author":[{"given":"Thomas","family":"Kleinert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martine","family":"Labb\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fr\u00e4nk","family":"Plein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6208-5677","authenticated-orcid":false,"given":"Martin","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,11]]},"reference":[{"issue":"3","key":"1660_CR1","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s11590-006-0024-3","volume":"1","author":"C Audet","year":"2007","unstructured":"Audet, C., Haddad, J., Savard, G.: Disjunctive cuts for continuous linear bilevel programming. Optim. Lett. 1(3), 259\u2013267 (2007). https:\/\/doi.org\/10.1007\/s11590-006-0024-3","journal-title":"Optim. Lett."},{"issue":"2","key":"1660_CR2","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10957-007-9263-4","volume":"134","author":"C Audet","year":"2007","unstructured":"Audet, C., Savard, G., Zghal, W.: New branch-and-cut algorithm for bilevel linear programming. J. Optim. Theory Appl. 134(2), 353\u2013370 (2007). https:\/\/doi.org\/10.1007\/s10957-007-9263-4","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"1660_CR3","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0911017","volume":"11","author":"JF Bard","year":"1990","unstructured":"Bard, J.F., Moore, J.T.: A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Stat. Comput. 11(2), 281\u2013292 (1990). https:\/\/doi.org\/10.1137\/0911017","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"2","key":"1660_CR4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/ijoc.2015.0676","volume":"28","author":"A Caprara","year":"2016","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2), 319\u2013333 (2016). https:\/\/doi.org\/10.1287\/ijoc.2015.0676","journal-title":"INFORMS J. Comput."},{"key":"1660_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/b101970","volume-title":"Foundations of Bilevel Programming","author":"S Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bilevel Programming. Springer, Berlin (2002). https:\/\/doi.org\/10.1007\/b101970"},{"key":"1660_CR6","unstructured":"DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. thesis. Lehigh University, (2011). https:\/\/preserve.lehigh.edu\/etd\/1226"},{"issue":"2","key":"1660_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002). https:\/\/doi.org\/10.1007\/s101070100263","journal-title":"Math. Program."},{"key":"1660_CR8","doi-asserted-by":"crossref","unstructured":"Egerer, J., Grimm, V., Kleinert, T., Schmidt, M., Zottl, G.: The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment. Eur J Ope Res (2020) (forthcoming)","DOI":"10.2139\/ssrn.3498339"},{"issue":"6","key":"1660_CR9","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6), 1615\u20131637 (2017). https:\/\/doi.org\/10.1287\/opre.2017.1650","journal-title":"Oper. Res."},{"issue":"2","key":"1660_CR10","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1287\/ijoc.2018.0831","volume":"31","author":"M Fischetti","year":"2019","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., Sinnl, M.: Interdiction games and monotonicity, with application to knapsack problems. INFORMS J. Comput. 31(2), 390\u2013410 (2019). https:\/\/doi.org\/10.1287\/ijoc.2018.0831","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1660_CR11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ejor.2017.11.043","volume":"267","author":"M Fischetti","year":"2018","unstructured":"Fischetti, M., Monaci, M., Sinnl, M.: A dynamic reformulation heuristic for generalized interdiction problems. Eur. J. Oper. Res. 267(1), 40\u201351 (2018). https:\/\/doi.org\/10.1016\/j.ejor.2017.11.043","journal-title":"Eur. J. Oper. Res."},{"issue":"9","key":"1660_CR12","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1057\/jors.1981.156","volume":"32","author":"J Fortuny-Amat","year":"1981","unstructured":"Fortuny-Amat, J., McCarl, B.: A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32(9), 783\u2013792 (1981). https:\/\/doi.org\/10.1057\/jors.1981.156","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"1660_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00186-018-0647-z","volume":"89","author":"V Grimm","year":"2019","unstructured":"Grimm, V., Schewe, L., Schmidt, M., Z\u00f6ttl, G.: A multilevel model of the european entry-exit gas market. Math. Methods Oper. Res. 89(2), 223\u2013255 (2019). https:\/\/doi.org\/10.1007\/s00186-018-0647-z","journal-title":"Math. Methods Oper. Res."},{"issue":"5","key":"1660_CR14","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1137\/0913069","volume":"13","author":"P Hansen","year":"1992","unstructured":"Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194\u20131217 (1992). https:\/\/doi.org\/10.1137\/0913069","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"5","key":"1660_CR15","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1287\/opre.1070.0431","volume":"55","author":"X Hu","year":"2007","unstructured":"Hu, X., Ralph, D.: Using EPECs to model bilevel games in restructured electricity markets with locational prices. Oper. Res. 55(5), 809\u2013827 (2007). https:\/\/doi.org\/10.1287\/opre.1070.0431","journal-title":"Oper. Res."},{"issue":"6","key":"1660_CR16","doi-asserted-by":"publisher","first-page":"1716","DOI":"10.1287\/opre.2019.1944","volume":"68","author":"T Kleinert","year":"2020","unstructured":"Kleinert, T., Labb\u00e9, M., Plein, F., Schmidt, M.: There\u2019s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization. Oper Res 68(6), 1716\u20131721 (2020). https:\/\/doi.org\/10.1287\/opre.2019.1944","journal-title":"Oper Res"},{"key":"1660_CR17","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0945","author":"T Kleinert","year":"2019","unstructured":"Kleinert, T., Schmidt, M.: Computing stationary points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. (2019). https:\/\/doi.org\/10.1287\/ijoc.2019.0945","journal-title":"INFORMS J. Comput."},{"issue":"12 part 1","key":"1660_CR18","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1287\/mnsc.44.12.1608","volume":"44","author":"M Labb\u00e9","year":"1998","unstructured":"Labb\u00e9, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Manag. Sci. 44(12 part 1), 1608\u20131622 (1998). https:\/\/doi.org\/10.1287\/mnsc.44.12.1608","journal-title":"Manag. Sci."},{"issue":"1","key":"1660_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-012-0213-0","volume":"11","author":"M Labb\u00e9","year":"2013","unstructured":"Labb\u00e9, M., Violin, A.: Bilevel programming and price setting problems. 4OR 11(1), 1\u201330 (2013). https:\/\/doi.org\/10.1007\/s10288-012-0213-0","journal-title":"4OR"},{"issue":"1","key":"1660_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/2FBF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Math. Program. 10(1), 147\u2013175 (1976). https:\/\/doi.org\/10.1007\/2FBF01580665","journal-title":"Math. Program."},{"key":"1660_CR21","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2019.2892607","author":"S Pineda","year":"2019","unstructured":"Pineda, S., Morales, J.M.: Solving linear bilevel problems using big-ms: not all that glitters is gold. IEEE Trans. Power Syst. (2019). https:\/\/doi.org\/10.1109\/TPWRS.2019.2892607","journal-title":"IEEE Trans. Power Syst."},{"key":"1660_CR22","unstructured":"Regionales Rechenzentrum Erlangen. Woodcrest Cluster. url: https:\/\/www.anleitungen.rrze.fau.de\/hpc\/woody-cluster (visited on 06\/03\/2020)"},{"issue":"2","key":"1660_CR23","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF02191670","volume":"81","author":"L Vicente","year":"1994","unstructured":"Vicente, L., Savard, G., J\u00fadice, J.: Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2), 379\u2013399 (1994). https:\/\/doi.org\/10.1007\/BF02191670","journal-title":"J. Optim. Theory Appl."},{"key":"1660_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.cor.2013.07.016","volume":"41","author":"P Xu","year":"2014","unstructured":"Xu, P., Wang, L.: An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41, 309\u2013318 (2014). https:\/\/doi.org\/10.1016\/j.cor.2013.07.016","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1660_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s10479-017-2694-x","volume":"272","author":"MH Zare","year":"2019","unstructured":"Zare, M.H., Borrero, J.S., Zeng, B., Prokopyev, O.A.: A note on linearized reformulations for a class of bilevel linear integer problems. Ann. Oper. Res. 272(1), 99\u2013117 (2019). https:\/\/doi.org\/10.1007\/s10479-017-2694-x","journal-title":"Ann. Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01660-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-020-01660-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01660-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T19:10:46Z","timestamp":1620414646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-020-01660-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,11]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["1660"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01660-6","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,11]]},"assertion":[{"value":"5 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}