{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T18:14:11Z","timestamp":1773944051499,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"16","license":[{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T00:00:00Z","timestamp":1684972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012740","name":"Gruppo Nazionale per l\u2019Analisi Matematica, la Probabilit\u00e0 e le loro Applicazioni","doi-asserted-by":"publisher","award":["Progetti di ricerca 2020 (Ottimizzazione Bilivello) and Progetti di Ricerca 2022 (Ottimizzazione con Incertezza, CUP_E55F22000270001)"],"award-info":[{"award-number":["Progetti di ricerca 2020 (Ottimizzazione Bilivello) and Progetti di Ricerca 2022 (Ottimizzazione con Incertezza, CUP_E55F22000270001)"]}],"id":[{"id":"10.13039\/100012740","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study linear bilevel programming problems, where (some of) the leader and the follower variables are restricted to be integer. A discussion on the relationships between the optimistic and the pessimistic setting is presented, providing necessary and sufficient conditions for them to be equivalent. A new class of inequalities, the follower optimality cuts, is introduced. They are used to derive a single-level non-compact reformulation of a bilevel problem, both for the optimistic and for the pessimistic case. The same is done for a family of known inequalities, the no-good cuts, and a polyhedral comparison of the related formulations is carried out. Finally, for both the optimistic and the pessimistic approach, we present a branch-and-cut algorithm and discuss computational results.<\/jats:p>","DOI":"10.1007\/s00500-023-08379-3","type":"journal-article","created":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T16:02:01Z","timestamp":1685030521000},"page":"11529-11550","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The follower optimality cuts for mixed integer linear bilevel programming problems"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5054-731X","authenticated-orcid":false,"given":"Sara","family":"Mattia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,25]]},"reference":[{"key":"8379_CR1","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01580440","volume":"8","author":"E Balas","year":"1975","unstructured":"Balas E (1975) Facets of the knapsack polytope. Math Program 8:146\u2013164","journal-title":"Math Program"},{"key":"8379_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2836-1","volume-title":"Practical bilevel optimization: algorithms and applications","author":"J Bard","year":"1998","unstructured":"Bard J (1998) Practical bilevel optimization: algorithms and applications. Kluwer Academic Publishers, Dordrecht"},{"key":"8379_CR3","doi-asserted-by":"crossref","unstructured":"Bard J, Moore T (1990) The mixed integer linear bilevel programming problem. Oper Res 28:911\u2013921","DOI":"10.1287\/opre.38.5.911"},{"key":"8379_CR4","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10107-003-0454-y","volume":"99","author":"A Ben-Tal","year":"2004","unstructured":"Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjusting robust solutions of uncertain linear programs. Math Program 99:351\u2013376","journal-title":"Math Program"},{"key":"8379_CR5","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"J Benders","year":"1962","unstructured":"Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:238\u2013252","journal-title":"Numer Math"},{"key":"8379_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program B 98:49\u201371","journal-title":"Math Program B"},{"key":"8379_CR7","doi-asserted-by":"crossref","unstructured":"Bonami P, Margot F (2015) Cut generation through binarization. Math Program 154:197\u2013223","DOI":"10.1007\/s10107-015-0924-z"},{"key":"8379_CR8","doi-asserted-by":"crossref","unstructured":"Colson B, Marcotte P, Savard G (2007) Bilevel programming: a survey. 4OR Q J Oper Res 3:87\u2013107","DOI":"10.1007\/s10288-005-0071-0"},{"key":"8379_CR9","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/s10107-018-1294-0","volume":"170","author":"S Dash","year":"2018","unstructured":"Dash S, G\u00fcnl\u00fck O, Hildebrand R (2018) Binary extended formulations of polyhedral mixed-integer sets. Math Program 170:206\u2013236","journal-title":"Math Program"},{"key":"8379_CR10","volume-title":"Foundations of bilevel programming","author":"S Dempe","year":"2002","unstructured":"Dempe S (2002) Foundations of bilevel programming. Kluwer Academic Publishers, Dordrecht"},{"key":"8379_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1080\/0233193031000149894","volume":"52","author":"S Dempe","year":"2003","unstructured":"Dempe S (2003) Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52:333\u2013359","journal-title":"Optimization"},{"key":"8379_CR12","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1080\/02331934.2012.696641","volume":"63","author":"S Dempe","year":"2014","unstructured":"Dempe S, Mordukhovich B, Zemkoho A (2014) Necessary optimality conditions in pessimistic bilevel programming. Optimization 63:505\u2013533","journal-title":"Optimization"},{"key":"8379_CR13","unstructured":"DeNegre S (2011) Interdiction and discrete bilevel programming. Ph.D. thesis, Lehigh University, Bethlehem."},{"key":"8379_CR14","doi-asserted-by":"crossref","unstructured":"DeNegre S, Ralphs T (2009) A branch-and-cut algorithm for integer bilevel linear programs. In: Operations research and cyber-infrastructure, operations research\/computer science interfaces series, vol 47, pp 65\u201378","DOI":"10.1007\/978-0-387-88843-9_4"},{"key":"8379_CR15","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:1615\u20131637","journal-title":"Oper Res"},{"key":"8379_CR16","unstructured":"Fischetti M, Ljubic I, Monaci M, Sinnl M (2019) http:\/\/msinnl.github.io\/pages\/bilevel.html. Accessed Jan 2019"},{"key":"8379_CR17","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01586088","volume":"32","author":"R Jeroslov","year":"1985","unstructured":"Jeroslov R (1985) The polynomial hierarchy and a simple model for competitive analysis. Math Program 32:146\u2013164","journal-title":"Math Program"},{"key":"8379_CR18","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","journal-title":"Discret Optim"},{"key":"8379_CR19","doi-asserted-by":"crossref","unstructured":"Kleinert T, Labb\u00e9 M, Ljubic I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. http:\/\/www.optimization-online.org\/DB_FILE\/2021\/01\/8187.pdf. Accessed Feb 2021","DOI":"10.1016\/j.ejco.2021.100007"},{"key":"8379_CR20","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10957-010-9668-3","volume":"146","author":"M K\u00f6ppe","year":"2010","unstructured":"K\u00f6ppe M, Queyranne M, Ryan C (2010) Parametric integer programming algorithm for bilevel integer programs. J Optim Theory Appl 146:137\u2013150","journal-title":"J Optim Theory Appl"},{"key":"8379_CR21","doi-asserted-by":"crossref","unstructured":"Laporte G, Louveaux F (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper Res Lett 13:133\u2013142","DOI":"10.1016\/0167-6377(93)90002-X"},{"key":"8379_CR22","doi-asserted-by":"crossref","unstructured":"Liu J, Fan Y, Chen Z, Zheng Y (2018) Pessimistic bilevel optimization: a survey. Int J Comput Intell Syst 11:725\u2013736","DOI":"10.2991\/ijcis.11.1.56"},{"key":"8379_CR23","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1016\/j.ejor.2020.10.002","volume":"291","author":"S Liu","year":"2021","unstructured":"Liu S, Wang M, Kong N, Hu X (2021) An enhanced branch-and-bound algorithm for bilevel integer linear programming. Eur J Oper Res 291:661\u2013679","journal-title":"Eur J Oper Res"},{"key":"8379_CR24","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s10107-013-0700-x","volume":"146","author":"A Lodi","year":"2014","unstructured":"Lodi A, Ralphs TK, Woeginger GJ (2014) Bilevel programming and the separation problem. Math Program 146:437\u2013458","journal-title":"Math Program"},{"key":"8379_CR25","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1287\/opre.2017.1589","volume":"65","author":"L Lozano","year":"2017","unstructured":"Lozano L, Smith JC (2017) A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper Res 65:768\u2013786","journal-title":"Oper Res"},{"issue":"6","key":"8379_CR26","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.orl.2012.09.009","volume":"40","author":"S Mattia","year":"2012","unstructured":"Mattia S (2012) Separating tight metric inequalities by bilevel programming. Oper Res Lett 40(6):568\u2013572","journal-title":"Oper Res Lett"},{"issue":"3","key":"8379_CR27","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10589-012-9500-0","volume":"54","author":"S Mattia","year":"2013","unstructured":"Mattia S (2013) The robust network loading problem with dynamic routing. Comput Optim Appl 54(3):619\u2013643","journal-title":"Comput Optim Appl"},{"key":"8379_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.06.008","author":"S Mattia","year":"2021","unstructured":"Mattia S (2021) Reformulations and complexity of the clique interdiction problem by graph mapping. Discrete Appl Math in press. https:\/\/doi.org\/10.1016\/j.dam.2021.06.008","journal-title":"Discrete Appl Math in press"},{"key":"8379_CR29","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems. SIAM Rev 33:60\u2013100","journal-title":"SIAM Rev"},{"key":"8379_CR30","unstructured":"Passmark Software: http:\/\/www.cpubenchmark.net"},{"key":"8379_CR31","first-page":"37","volume":"2","author":"JS Roy","year":"2007","unstructured":"Roy JS (2007) Binarize and Project to generate cuts for general mixed-integer programs. Algorithmic Oper Res 2:37\u201351","journal-title":"Algorithmic Oper Res"},{"key":"8379_CR32","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1016\/j.ejor.2019.06.024","volume":"283","author":"J Smith","year":"2020","unstructured":"Smith J, Song Y (2020) A survey of network interdiction models and algorithms. Eur J Oper Res 283:797\u2013811","journal-title":"Eur J Oper Res"},{"key":"8379_CR33","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s12532-020-00183-6","volume":"12","author":"S Tahernejad","year":"2020","unstructured":"Tahernejad S, Ralphs T, DeNegre S (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math Program Comput 12:529\u2013568","journal-title":"Math Program Comput"},{"key":"8379_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 JP, Smith JC (2016) A class of algorithms for mixed-integer bilevel min-max optimization. J Global Optim 66:225\u2013262","journal-title":"J Global Optim"},{"key":"8379_CR35","unstructured":"Tang Y, Richard JPP, Smith J (2019) http:\/\/jcsmith.people.clemson.edu\/Test_Instances.html. Accessed Jan 2019"},{"key":"8379_CR36","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01096458","volume":"5","author":"L Vincente","year":"1994","unstructured":"Vincente L, Calamai P (1994) Bilevel and multilevel programming: a bibiliography review. J Global Optim 5:291\u2013306","journal-title":"J Global Optim"},{"key":"8379_CR37","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1137\/15M1051592","volume":"27","author":"L Wang","year":"2017","unstructured":"Wang L, Xu P (2017) The watermelon algorithm for the bilevel integer linear programming problem. SIAM J Optim 27:1403\u20131430","journal-title":"SIAM J Optim"},{"key":"8379_CR38","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0305-0548(90)90037-8","volume":"17","author":"U Wen","year":"1990","unstructured":"Wen U, Yang Y (1990) Algorithms for solving the mixed integer two-level linear programming problem. Comput Oper Res 17:133\u2013142","journal-title":"Comput Oper Res"},{"key":"8379_CR39","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, Rustem B (2013) Pessimistic bi-level optimisation. SIAM J Optim 23:353\u2013380","journal-title":"Pessimistic bi-level optimisation. SIAM J Optim"},{"key":"8379_CR40","unstructured":"Wolsey L (1998) Integer programming. Wiley-interscience series in discrete mathematics and optimization. Wiley"},{"key":"8379_CR41","doi-asserted-by":"publisher","first-page":"308","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:308\u2013318","journal-title":"Comput Oper Res"},{"key":"8379_CR42","first-page":"1128","volume":"32","author":"B Zeng","year":"2020","unstructured":"Zeng B (2020) A practical scheme to compute the pessimistic bilevel optimization problem. INFORMS J Comput 32:1128\u20131142","journal-title":"INFORMS J Comput"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-08379-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-023-08379-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-08379-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,17]],"date-time":"2023-07-17T11:06:46Z","timestamp":1689592006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-023-08379-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,25]]},"references-count":42,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["8379"],"URL":"https:\/\/doi.org\/10.1007\/s00500-023-08379-3","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,25]]},"assertion":[{"value":"27 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no conflict of interest concerning this study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This paper does not contain any studies with human participants or animals performed the author.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal rights"}}]}}