{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:31:42Z","timestamp":1775716302826,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T00:00:00Z","timestamp":1675728000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T00:00:00Z","timestamp":1675728000000},"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":["CRCTRR154"],"award-info":[{"award-number":["CRCTRR154"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006463","name":"Bayerisches Staatsministerium f\u00fcr Wirtschaft und Medien, Energie und Technologie","doi-asserted-by":"publisher","award":["Energie Campus N\u00fcrnberg"],"award-info":[{"award-number":["Energie Campus N\u00fcrnberg"]}],"id":[{"id":"10.13039\/501100006463","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100018755","name":"Universit\u00e4t Trier","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018755","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to solve. Since no general-purpose solvers are available, a \u201cbest-practice\u201d has developed in the applied OR community, in which not all people want to develop tailored algorithms but \u201cjust use\u201d bilevel optimization as a modeling tool for practice. This best-practice is the big-<jats:italic>M<\/jats:italic> reformulation of the Karush\u2013Kuhn\u2013Tucker (KKT) conditions of the lower-level problem\u2014an approach that has been shown to be highly problematic by Pineda and Morales (2019). Choosing invalid values for <jats:italic>M<\/jats:italic> yields solutions that may be arbitrarily bad. Checking the validity of the big-<jats:italic>M<\/jats:italic>s is however shown to be as hard as solving the original bilevel problem in Kleinert et\u00a0al. (2019). Nevertheless, due to its appealing simplicity, especially w.r.t. the required implementation effort, this ready-to-use approach still is the most popular method. Until now, there has been a lack of approaches that are competitive both in terms of implementation effort and computational cost. In this note we demonstrate that there is indeed another competitive ready-to-use approach: If the SOS-1 technique is applied to the KKT complementarity conditions, adding the simple additional root-node inequality developed by Kleinert et\u00a0al. (2020) leads to a competitive performance\u2014without having all the possible theoretical disadvantages of the big-<jats:italic>M<\/jats:italic> approach.<\/jats:p>","DOI":"10.1007\/s10287-023-00435-5","type":"journal-article","created":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T12:59:10Z","timestamp":1675774750000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Why there is no need to use a big-M in linear bilevel optimization: a computational study of two ready-to-use approaches"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7082-7466","authenticated-orcid":false,"given":"Thomas","family":"Kleinert","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6208-5677","authenticated-orcid":false,"given":"Martin","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,7]]},"reference":[{"issue":"2","key":"435_CR1","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0911017","volume":"11","author":"JF Bard","year":"1990","unstructured":"Bard JF, Moore JT (1990) A branch and bound algorithm for the bilevel programming problem. SIAM J Sci Stat Comput 11(2):281\u2013292. https:\/\/doi.org\/10.1137\/0911017","journal-title":"SIAM J Sci Stat Comput"},{"issue":"9","key":"435_CR2","doi-asserted-by":"publisher","first-page":"3239","DOI":"10.1016\/j.apenergy.2011.03.023","volume":"88","author":"L Baringo","year":"2011","unstructured":"Baringo L, Conejo AJ (2011) Wind power investment within a market environment. Appl Energy 88(9):3239\u20133247. https:\/\/doi.org\/10.1016\/j.apenergy.2011.03.023","journal-title":"Appl Energy"},{"key":"435_CR3","unstructured":"Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Proceedings of the fifth international conference on operational research. J. Lawrence (eds.) Tavistock Publications, 447\u2013454"},{"key":"435_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.06.034","author":"T B\u00f6ttger","year":"2021","unstructured":"B\u00f6ttger T, Grimm V, Kleinert T, Schmidt M (2021) The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market with Linear Physics Modeling. European J Oper Res. https:\/\/doi.org\/10.1016\/j.ejor.2021.06.034","journal-title":"European J Oper Res"},{"key":"435_CR5","doi-asserted-by":"publisher","unstructured":"Constante-Flores G, Conejo AJ, Constante-Flores S (2022) Solving certain complementarity problems in power markets via convex programming. In: TOP 30.3, pp. 465\u2013491. https:\/\/doi.org\/10.1007\/s11750-022-00627-3","DOI":"10.1007\/s11750-022-00627-3"},{"key":"435_CR6","doi-asserted-by":"publisher","unstructured":"Dempe S (2002) Foundations of Bilevel Programming. Springer. https:\/\/doi.org\/10.1007\/b101970","DOI":"10.1007\/b101970"},{"key":"435_CR7","unstructured":"DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis. Lehigh University"},{"issue":"2","key":"435_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan ED, Mor\u00e9 JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201\u2013213. https:\/\/doi.org\/10.1007\/s101070100263","journal-title":"Math Program"},{"issue":"6","key":"435_CR9","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti M, Ljubic I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper Res 65(6):1615\u20131637. https:\/\/doi.org\/10.1287\/opre.2017.1650","journal-title":"Oper Res"},{"issue":"2","key":"435_CR10","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1287\/ijoc.2018.0831","volume":"31","author":"M Fischetti","year":"2019","unstructured":"Fischetti M, Ljubic I, Monaci M, Sinnl M (2019) Interdiction games and monotonicity, with application to knapsack problems. INFORMS J Comput 31(2):390\u2013410. https:\/\/doi.org\/10.1287\/ijoc.2018.0831","journal-title":"INFORMS J Comput"},{"issue":"1","key":"435_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 (2018) A dynamic reformulation heuristic for Generalized Interdiction Problems. Eur J Oper Res 267(1):40\u201351. https:\/\/doi.org\/10.1016\/j.ejor.2017.11.043","journal-title":"Eur J Oper Res"},{"issue":"9","key":"435_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 (1981) A representation and economic interpretation of a two-level programming problem. J Oper Res Soc 32(9):783\u2013792. https:\/\/doi.org\/10.1057\/jors.1981.156","journal-title":"J Oper Res Soc"},{"issue":"3","key":"435_CR13","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1109\/TPWRS.2009.2021230","volume":"24","author":"LP Garces","year":"2009","unstructured":"Garces LP, Conejo AJ, Garcia-Bertrand R, Romero R (2009) A bilevel approach to transmission expansion planning within a market environment. IEEE Trans Power Syst 24(3):1513\u20131522. https:\/\/doi.org\/10.1109\/TPWRS.2009.2021230","journal-title":"IEEE Trans Power Syst"},{"issue":"5","key":"435_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 (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13(5):1194\u20131217. https:\/\/doi.org\/10.1137\/0913069","journal-title":"SIAM J Sci Stat Comput"},{"key":"435_CR15","doi-asserted-by":"publisher","unstructured":"Horst R, Tuy H (2013) Global optimization: deterministic approaches. Springer Science & Business Media. https:\/\/doi.org\/10.1007\/978-3-662-03199-5","DOI":"10.1007\/978-3-662-03199-5"},{"key":"435_CR16","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.ijepes.2015.02.002","volume":"70","author":"TB Jaber Valinejad","year":"2015","unstructured":"Jaber Valinejad TB (2015) Generation expansion planning in electricity markets: a novel framework based on dynamic stochastic MPEC. Int J Electr Power Energy Syst 70:108\u2013117. https:\/\/doi.org\/10.1016\/j.ijepes.2015.02.002","journal-title":"Int J Electr Power Energy Syst"},{"issue":"3","key":"435_CR17","doi-asserted-by":"publisher","first-page":"2639","DOI":"10.1109\/TPWRS.2012.2236110","volume":"28","author":"M Jenabi","year":"2013","unstructured":"Jenabi M, Fatemi Ghomi SMT, Smeers Y (2013) Bi-level game approaches for coordination of generation and transmission expansion planning within a market environment. IEEE Trans Power Syst 28(3):2639\u20132650. https:\/\/doi.org\/10.1109\/TPWRS.2012.2236110","journal-title":"IEEE Trans Power Syst"},{"issue":"1","key":"435_CR18","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1109\/TPWRS.2011.2159251","volume":"27","author":"SJ Kazempour","year":"2012","unstructured":"Kazempour SJ, Conejo AJ (2012) Strategic generation investment under uncertainty via benders decomposition. IEEE Trans Power Syst 27(1):424\u2013432. https:\/\/doi.org\/10.1109\/TPWRS.2011.2159251","journal-title":"IEEE Trans Power Syst"},{"issue":"2","key":"435_CR19","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1109\/TPWRS.2010.2069573","volume":"26","author":"SJ Kazempour","year":"2011","unstructured":"Kazempour SJ, Conejo AJ, Ruiz C (2011) Strategic generation investment using a complementarity approach. IEEE Trans Power Syst 26(2):940\u2013948. https:\/\/doi.org\/10.1109\/TPWRS.2010.2069573","journal-title":"IEEE Trans Power Syst"},{"issue":"3","key":"435_CR20","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1109\/TPWRS.2011.2182664","volume":"27","author":"SJ Kazempour","year":"2012","unstructured":"Kazempour SJ, Conejo AJ, Ruiz C (2012) Strategic generation investment considering futures and spot markets. IEEE Trans Power Syst 27(3):1467\u20131476. https:\/\/doi.org\/10.1109\/TPWRS.2011.2182664","journal-title":"IEEE Trans Power Syst"},{"key":"435_CR21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1944","author":"T Kleinert","year":"2019","unstructured":"Kleinert T, Labb\u00e9 M, Plein F, Schmidt M (2019) There\u2019s no free lunch: on the hardness of choosing a correct big-M in bilevel optimization. Oper Res. https:\/\/doi.org\/10.1287\/opre.2019.1944","journal-title":"Oper Res"},{"key":"435_CR22","doi-asserted-by":"crossref","unstructured":"Kleinert T, Labb\u00e9 M, Plein F, Schmidt M (2020). Closing the gap in linear bilevel optimization: a new valid primal-dual inequality. Tech Rep. http:\/\/www.optimization-online.org\/DB_HTML\/2020\/06\/7826.html. Submitted","DOI":"10.1007\/s11590-020-01660-6"},{"key":"435_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.disopt.2019.02.002","volume":"33","author":"T Kleinert","year":"2019","unstructured":"Kleinert T, Schmidt M (2019) Global optimization of multilevel electricity market models including network design and graph partitioning. Discret Optim 33:43\u201369. https:\/\/doi.org\/10.1016\/j.disopt.2019.02.002","journal-title":"Discret Optim"},{"key":"435_CR24","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0945","author":"T Kleinert","year":"2020","unstructured":"Kleinert T, Schmidt M (2020) Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J Comput. https:\/\/doi.org\/10.1287\/ijoc.2019.0945","journal-title":"INFORMS J Comput"},{"issue":"3","key":"435_CR25","doi-asserted-by":"publisher","first-page":"1633","DOI":"10.1109\/TPWRS.2014.2367107","volume":"30","author":"L Maurovich-Horvat","year":"2015","unstructured":"Maurovich-Horvat L, Boomsma TK, Siddiqui AS (2015) Transmission and wind investment in a deregulated electricity industry. IEEE Trans Power Syst 30(3):1633\u20131643. https:\/\/doi.org\/10.1109\/TPWRS.2014.2367107","journal-title":"IEEE Trans Power Syst"},{"issue":"1","key":"435_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: part I-Convex underestimating problems. Math Program 10(1):147\u2013175. https:\/\/doi.org\/10.1007\/BF01580665","journal-title":"Math Program"},{"issue":"3","key":"435_CR27","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.ejor.2013.11.013","volume":"235","author":"JM Morales","year":"2014","unstructured":"Morales JM, Zugno M, Pineda S, Pinson P (2014) Electricity market clearing with improved scheduling of stochastic production. Eur J Oper Res 235(3):765\u2013774. https:\/\/doi.org\/10.1016\/j.ejor.2013.11.013","journal-title":"Eur J Oper Res"},{"issue":"1","key":"435_CR28","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s11081-017-9369-y","volume":"19","author":"S Pineda","year":"2018","unstructured":"Pineda S, Bylling H, Morales J (2018) Efficiently solving linear bilevel programming problems using off-the-shelf optimization software. Optim Eng 19(1):187\u2013211. https:\/\/doi.org\/10.1007\/s11081-017-9369-y","journal-title":"Optim Eng"},{"key":"435_CR29","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2019.2892607","author":"S Pineda","year":"2019","unstructured":"Pineda S, Morales JM (2019) Solving linear bilevel problems using big-Ms: not all that glitters is gold. IEEE Trans Power Syst. https:\/\/doi.org\/10.1109\/TPWRS.2019.2892607","journal-title":"IEEE Trans Power Syst"},{"issue":"1","key":"435_CR30","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10287-014-0223-9","volume":"13","author":"P Pisciella","year":"2016","unstructured":"Pisciella P, Bertocchi M, Vespucci MT (2016) A leader-followers model of power transmission capacity expansion in a market driven environment. CMS 13(1):87\u2013118. https:\/\/doi.org\/10.1007\/s10287-014-0223-9","journal-title":"CMS"},{"issue":"1","key":"435_CR31","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1109\/TPWRS.2012.2204073","volume":"28","author":"D Pozo","year":"2013","unstructured":"Pozo D, Sauma EE, Contreras J (2013) A three-level static MILP model for generation and transmission expansion planning. IEEE Trans Power Syst 28(1):202\u2013210. https:\/\/doi.org\/10.1109\/TPWRS.2012.2204073","journal-title":"IEEE Trans Power Syst"},{"key":"435_CR32","unstructured":"Regionales Rechenzentrum Erlangen (2020). Woodcrest Cluster. https:\/\/www.anleitungen.rrze.fau.de\/hpc\/woody-cluster\/ (visited on 08\/03\/2020)"},{"issue":"2","key":"435_CR33","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s11067-012-9178-y","volume":"13","author":"S Siddiqui","year":"2013","unstructured":"Siddiqui S, Gabriel SA (2013) An SOS1-based approach for solving MPECs with a natural gas market application. Netw Spat Econ 13(2):205\u2013227. https:\/\/doi.org\/10.1007\/s11067-012-9178-y","journal-title":"Netw Spat Econ"},{"issue":"2","key":"435_CR34","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10898-015-0274-7","volume":"66","author":"Y Tang","year":"2016","unstructured":"Tang Y, Richard J-PP, Smith JC (2016) A class of algorithms for mixed-integer bilevel min-max optimization. J Global Optim 66(2):225\u2013262. https:\/\/doi.org\/10.1007\/s10898-015-0274-7","journal-title":"J Global Optim"},{"issue":"2","key":"435_CR35","doi-asserted-by":"publisher","first-page":"1531","DOI":"10.1109\/TPWRS.2012.2217510","volume":"28","author":"S Wogrin","year":"2013","unstructured":"Wogrin S, Barqu\u00edn J, Centeno E (2013) Capacity expansion equilibria in liberalized electricity markets: an EPEC approach. IEEE Trans Power Syst 28(2):1531\u20131539. https:\/\/doi.org\/10.1109\/TPWRS.2012.2217510","journal-title":"IEEE Trans Power Syst"},{"issue":"4","key":"435_CR36","doi-asserted-by":"publisher","first-page":"2526","DOI":"10.1109\/TPWRS.2011.2138728","volume":"26","author":"S Wogrin","year":"2011","unstructured":"Wogrin S, Centeno E, Barquin J (2011) Generation capacity expansion in liberalized electricity markets: a stochastic MPEC approach. IEEE Trans Power Syst 26(4):2526\u20132532. https:\/\/doi.org\/10.1109\/TPWRS.2011.2138728","journal-title":"IEEE Trans Power Syst"},{"key":"435_CR37","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 (2014) An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput Oper Res 41:309\u2013318. https:\/\/doi.org\/10.1016\/j.cor.2013.07.016","journal-title":"Comput Oper Res"}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-023-00435-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10287-023-00435-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-023-00435-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T15:04:16Z","timestamp":1706195056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10287-023-00435-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["435"],"URL":"https:\/\/doi.org\/10.1007\/s10287-023-00435-5","relation":{},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"value":"1619-697X","type":"print"},{"value":"1619-6988","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,7]]},"assertion":[{"value":"7 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"3"}}