{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T05:39:58Z","timestamp":1770701998386,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NSERC Energy Storage Technologies Network"},{"DOI":"10.13039\/501100010095","name":"R\u00e9gion Hauts-de-France","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010095","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,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions.<\/jats:p>","DOI":"10.1007\/s11590-021-01754-9","type":"journal-article","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T13:02:46Z","timestamp":1624971766000},"page":"2597-2610","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Complexity of near-optimal robust versions of multilevel optimization problems"],"prefix":"10.1007","volume":"15","author":[{"given":"Mathieu","family":"Besan\u00e7on","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8258-9116","authenticated-orcid":false,"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[]},{"given":"Luce","family":"Brotcorne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,29]]},"reference":[{"key":"1754_CR1","doi-asserted-by":"crossref","unstructured":"Dempe, S.: Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography, pp.\u00a0581\u2013672. Springer (2020)","DOI":"10.1007\/978-3-030-52119-6_20"},{"key":"1754_CR2","unstructured":"Besan\u00e7on, M., Anjos, M.F., Brotcorne, L.: Near-optimal Robust Bilevel Optimization (2019). https:\/\/arxiv.org\/abs\/1908.04040"},{"key":"1754_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-45827-3","volume-title":"Bilevel programming problems. Energy Systems","author":"S Dempe","year":"2015","unstructured":"Dempe, S., Kalashnikov, V., P\u00e9rez-Vald\u00e9s, G.A., Kalashnykova, N.: Bilevel programming problems. Energy Systems. Springer, Berlin (2015)"},{"key":"1754_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/120864015","volume":"23","author":"W Wiesemann","year":"2013","unstructured":"Wiesemann, W., Tsoukalas, A., Kleniati, P.-M., Rustem, B.: Pessimistic bilevel optimization. SIAM J. Optim. 23, 353\u2013380 (2013)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1754_CR5","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)","journal-title":"J. Optim. Theory Appl."},{"issue":"1\u20132","key":"1754_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s10107-012-0535-x","volume":"138","author":"GB Allende","year":"2013","unstructured":"Allende, G.B., Still, G.: Solving bilevel programs with the KKT-approach. Math. Progr. 138(1\u20132), 309\u2013332 (2013)","journal-title":"Math. Progr."},{"issue":"8","key":"1754_CR7","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1080\/02331934.2019.1581192","volume":"68","author":"S Dempe","year":"2019","unstructured":"Dempe, S., Franke, S.: Solution of bilevel optimization problems using the KKT approach. Optimization 68(8), 1471\u20131489 (2019)","journal-title":"Optimization"},{"issue":"3","key":"1754_CR8","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00940344","volume":"60","author":"S-J Chung","year":"1989","unstructured":"Chung, S.-J.: NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60(3), 393\u2013399 (1989)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"1754_CR9","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10898-019-00822-w","volume":"76","author":"S Dempe","year":"2020","unstructured":"Dempe, S., Khamisov, O., Kochetov, Y.: A special three-level optimization problem. J. Glob. Optim. 76(3), 519\u2013531 (2020)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1754_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10898-017-0549-2","volume":"71","author":"MH Zare","year":"2018","unstructured":"Zare, M.H., \u00d6zalt\u0131n, O.Y., Prokopyev, O.A.: On a class of bilevel linear mixed-integer programs in adversarial settings. J. Glob. Optim. 71(1), 91\u2013113 (2018)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1754_CR11","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1287\/deca.2019.0392","volume":"17","author":"MH Zare","year":"2020","unstructured":"Zare, M.H., Prokopyev, O.A., Saur\u00e9, D.: On bilevel optimization with inexact follower. Decis. Anal. 17(1), 74\u201395 (2020)","journal-title":"Decis. Anal."},{"key":"1754_CR12","unstructured":"Shi, X., Prokopyev, O., Ralphs, T.: Mixed integer bilevel optimization with k-optimal follower: a hierarchy of bounds. (2020). http:\/\/www.optimization-online.org\/DB_HTML\/2020\/06\/7874.html"},{"issue":"6","key":"1754_CR13","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)","journal-title":"Oper. Res."},{"key":"1754_CR14","unstructured":"Tahernejad, S., Ralphs, T.K., DeNegre, S.T.: A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. COR@ L Technical Report 16T-015-R3, Lehigh University (2016)"},{"key":"1754_CR15","doi-asserted-by":"crossref","unstructured":"Liu, S., Wang, M., Kong, N., Hu, X.: An enhanced branch-and-bound algorithm for bilevel integer linear programming. Eur. J. Oper. Res 291(2), 661\u2013679 (2021)","DOI":"10.1016\/j.ejor.2020.10.002"},{"issue":"2","key":"1754_CR16","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2), 823\u2013838 (2014)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1754_CR17","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. Progr. 32(2), 146\u2013164 (1985)","journal-title":"Math. Progr."},{"key":"1754_CR18","doi-asserted-by":"crossref","unstructured":"Bolusani, S., Coniglio, S., Ralphs, T.K., Tahernejad, S.: A Unified Framework for Multistage Mixed Integer Linear Optimization. pp. 513\u2013560. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-52119-6_18"},{"issue":"3","key":"1754_CR19","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/582475.582484","volume":"33","author":"M Schaefer","year":"2002","unstructured":"Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: a compendium. SIGACT News 33(3), 32\u201349 (2002)","journal-title":"SIGACT News"},{"key":"1754_CR20","doi-asserted-by":"crossref","unstructured":"Kleinert, T., Labb\u00e9, M., Ljubi\u0107, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization (2021). https:\/\/hal.inria.fr\/hal-03095139","DOI":"10.1016\/j.ejco.2021.100007"},{"issue":"1","key":"1754_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"LJ Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1754_CR22","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1287\/opre.38.5.911","volume":"38","author":"JT Moore","year":"1990","unstructured":"Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38(5), 911\u2013921 (1990)","journal-title":"Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01754-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01754-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01754-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T12:20:52Z","timestamp":1699186852000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01754-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,29]]},"references-count":22,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1754"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01754-9","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,29]]},"assertion":[{"value":"31 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}