{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T20:35:26Z","timestamp":1774557326364,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T00:00:00Z","timestamp":1733184000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T00:00:00Z","timestamp":1733184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M22UTB"],"award-info":[{"award-number":["05M22UTB"]}],"id":[{"id":"10.13039\/501100002347","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":["Optim Lett"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>It is well-known that coupling constraints in linear bilevel optimization can lead to disconnected feasible sets, which is not possible without coupling constraints. However, there is no difference between linear bilevel problems with and without coupling constraints w.r.t. their complexity-theoretical hardness. In this note, we prove that, although there is a clear difference between these two classes of problems in terms of their feasible sets, the classes are equivalent on the level of optimal solutions. To this end, given a general linear bilevel problem with coupling constraints, we derive a respective problem without coupling constraints and prove that it has the same optimal solutions (when projected back to the original variable space).<\/jats:p>","DOI":"10.1007\/s11590-024-02156-3","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T07:24:13Z","timestamp":1733210653000},"page":"689-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On coupling constraints in linear bilevel optimization"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9190-642X","authenticated-orcid":false,"given":"Dorothee","family":"Henke","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2914-9850","authenticated-orcid":false,"given":"Henri","family":"Lefebvre","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6208-5677","authenticated-orcid":false,"given":"Martin","family":"Schmidt","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8516-6250","authenticated-orcid":false,"given":"Johannes","family":"Th\u00fcrauf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,3]]},"reference":[{"issue":"2","key":"2156_CR1","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1023\/A:1022645805569","volume":"93","author":"C Audet","year":"1997","unstructured":"Audet, C., Hansen, P., Jaumard, B., Savard, G.: Links between linear bilevel and mixed 0\u20131 programming problems. J. Optim. Theory Appl. 93(2), 273\u2013300 (1997). https:\/\/doi.org\/10.1023\/A:1022645805569","journal-title":"J. Optim. Theory Appl."},{"key":"2156_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2836-1","volume-title":"Practical bilevel optimization: algorithms and applications","author":"JF Bard","year":"1998","unstructured":"Bard, J.F.: Practical bilevel optimization: algorithms and applications, vol. 30. Springer Science and Business Media, Berlin (1998). https:\/\/doi.org\/10.1007\/978-1-4757-2836-1"},{"issue":"3","key":"2156_CR3","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1287\/opre.38.3.556","volume":"38","author":"O Ben-Ayed","year":"1990","unstructured":"Ben-Ayed, O., Blair, C.E.: Computational difficulties of bilevel linear programming. Oper. Res. 38(3), 556\u2013560 (1990). https:\/\/doi.org\/10.1287\/opre.38.3.556","journal-title":"Oper. Res."},{"issue":"3","key":"2156_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF00940342","volume":"60","author":"HP Benson","year":"1989","unstructured":"Benson, H.P.: On the structure and properties of a linear multilevel programming problem. J. Optim. Theory Appl. 60(3), 353\u2013373 (1989). https:\/\/doi.org\/10.1007\/BF00940342","journal-title":"J. Optim. Theory Appl."},{"issue":"6","key":"2156_CR5","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/j.orl.2023.10.006","volume":"51","author":"C Buchheim","year":"2023","unstructured":"Buchheim, C.: Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations. Oper. Res. Lett. 51(6), 618\u2013622 (2023). https:\/\/doi.org\/10.1016\/j.orl.2023.10.006","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"2156_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10107-010-0342-1","volume":"131","author":"S Dempe","year":"2012","unstructured":"Dempe, S., Dutta, J.: Is bilevel programming a special case of a mathematical program with complementarity constraints? Math. Program. 131(1\u20132), 37\u201348 (2012). https:\/\/doi.org\/10.1007\/s10107-010-0342-1","journal-title":"Math. Program."},{"key":"2156_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52119-6","volume-title":"Bilevel Optimization. Advances and Next Challenges. Springer Optimization and Its Applications 161","year":"2020","unstructured":"Dempe, S., Zemkoho, A. (eds.): Bilevel Optimization. Advances and Next Challenges. Springer Optimization and Its Applications 161. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-52119-6"},{"issue":"1\u20132","key":"2156_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-016-1012-8","volume":"161","author":"MJ Feizollahi","year":"2016","unstructured":"Feizollahi, M.J., Ahmed, S., Sun, A.: Exact augmented Lagrangian duality for mixed integer linear programming. Math. Program. 161(1\u20132), 365\u2013387 (2016). https:\/\/doi.org\/10.1007\/s10107-016-1012-8","journal-title":"Math. Program."},{"key":"2156_CR9","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)"},{"issue":"1","key":"2156_CR10","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/19m1271695","volume":"30","author":"X Gu","year":"2020","unstructured":"Gu, X., Ahmed, S., Dey, S.S.: Exact augmented Lagrangian duality for mixed integer quadratic programming. SIAM J. Optim. 30(1), 781\u2013797 (2020). https:\/\/doi.org\/10.1137\/19m1271695","journal-title":"SIAM J. Optim."},{"issue":"5","key":"2156_CR11","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":"2","key":"2156_CR12","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01586088","volume":"32","author":"RG Jeroslow","year":"1985","unstructured":"Jeroslow, R.G.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32(2), 146\u2013164 (1985). https:\/\/doi.org\/10.1007\/BF01586088","journal-title":"Math. Program."},{"key":"2156_CR13","unstructured":"Kleinert, T.: Algorithms for Mixed-Integer Bilevel Problems with Convex Followers. PhD thesis. (2021). https:\/\/opus4.kobv.de\/opus4-trr154\/frontdoor\/index\/index\/docId\/383"},{"key":"2156_CR14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/0-387-25592-3_7","volume-title":"Graph Theory and Combinatorial Optimization","author":"P Marcotte","year":"2005","unstructured":"Marcotte, P., Savard, G.: Bilevel Programming: A Combinatorial Perspective. In: Avis, D., Hertz, A., Marcotte, O. (eds.) Graph Theory and Combinatorial Optimization, pp. 191\u2013217. Springer, Boston (2005). https:\/\/doi.org\/10.1007\/0-387-25592-3_7"},{"issue":"2","key":"2156_CR15","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."},{"issue":"3","key":"2156_CR16","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/BF02275351","volume":"89","author":"L Vicente","year":"1996","unstructured":"Vicente, L., Savard, G., J\u00fadice, J.: Discrete linear bilevel programming problem. J. Optim. Theory Appl. 89(3), 597\u2013614 (1996). https:\/\/doi.org\/10.1007\/BF02275351","journal-title":"J. Optim. Theory Appl."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02156-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-024-02156-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02156-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T16:31:26Z","timestamp":1742056286000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-024-02156-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,3]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["2156"],"URL":"https:\/\/doi.org\/10.1007\/s11590-024-02156-3","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,3]]},"assertion":[{"value":"23 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}