{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T18:22:07Z","timestamp":1764872527633,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T00:00:00Z","timestamp":1651708800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T00:00:00Z","timestamp":1651708800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"hungarian government and the european social fund","award":["EFOP-3.6.1-16-2016-00006"],"award-info":[{"award-number":["EFOP-3.6.1-16-2016-00006"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Lift-and-project (L &amp;P) cuts are well-known general 0\u20131 programming cuts which are typically deployed in branch-and-cut methods to solve MILP problems. In this article, we discuss ways to use these cuts within the framework of Benders\u2019 decomposition algorithms for solving two-stage mixed-binary stochastic problems with binary first-stage variables and continuous recourse. In particular, we show how L &amp;P cuts derived for the master problem can be strengthened with the second-stage information. An adapted L-shaped algorithm and its computational efficiency analysis is presented. We show that the strengthened L &amp;P cuts can significantly reduce the number of iterations and the solution time.<\/jats:p>","DOI":"10.1007\/s10287-022-00426-y","type":"journal-article","created":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T12:11:12Z","timestamp":1651752672000},"page":"539-565","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An L-shaped method with strengthened lift-and-project cuts"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7095-5847","authenticated-orcid":false,"given":"Pavlo","family":"Glushko","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9446-1566","authenticated-orcid":false,"given":"Csaba I.","family":"F\u00e1bi\u00e1n","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9648-3013","authenticated-orcid":false,"given":"Achim","family":"Koberstein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,5]]},"reference":[{"key":"426_CR1","unstructured":"Achterberg T (2007) Constraint integer programming. PhD thesis, Technische Universit\u00e4t Berlin"},{"issue":"4","key":"426_CR2","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/opre.2015.1401","volume":"63","author":"Y Adulyasak","year":"2015","unstructured":"Adulyasak Y, Cordeau JF, Jans R (2015) Benders decomposition for production routing under demand uncertainty. Oper Res 63(4):851\u2013867","journal-title":"Oper Res"},{"issue":"3","key":"426_CR3","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1287\/ijoc.2016.0695","volume":"28","author":"G Angulo","year":"2016","unstructured":"Angulo G, Ahmed S, Dey SS (2016) Improving the integer l-shaped method. INFORMS J Comput 28(3):483\u2013499","journal-title":"INFORMS J Comput"},{"key":"426_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E Balas","year":"1979","unstructured":"Balas E (1979) Disjunctive programming. Ann Discrete Math 5:3\u201351","journal-title":"Ann Discrete Math"},{"issue":"1","key":"426_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas E, Ceria S, Cornu\u00e9jols G (1993) A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math Progr 58(1):295\u2013324","journal-title":"Math Progr"},{"issue":"9","key":"426_CR6","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1287\/mnsc.42.9.1229","volume":"42","author":"E Balas","year":"1996","unstructured":"Balas E, Ceria S, Cornu\u00e9jols G (1996) Mixed 0\u20131 programming by lift-and-project in a branch-and-cut framework. Manag Sci 42(9):1229\u20131246","journal-title":"Manag Sci"},{"issue":"1","key":"426_CR7","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"JF Benders","year":"1962","unstructured":"Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238\u2013252","journal-title":"Numer Math"},{"issue":"2","key":"426_CR8","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00291-008-0147-2","volume":"31","author":"R Bihlmaier","year":"2009","unstructured":"Bihlmaier R, Koberstein A, Obst R (2009) Modeling and optimizing of strategic and tactical production planning in the automotive industry under uncertainty. OR Spectr 31(2):311","journal-title":"OR Spectr"},{"key":"426_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0237-4","volume-title":"Introduction to stochastic programming","author":"JR Birge","year":"2011","unstructured":"Birge JR, Louveaux F (2011) Introduction to stochastic programming, 2nd edn. Springer, Berlin","edition":"2"},{"issue":"3","key":"426_CR10","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0377-2217(88)90159-2","volume":"34","author":"JR Birge","year":"1988","unstructured":"Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. Eur J Oper Res 34(3):384\u2013392","journal-title":"Eur J Oper Res"},{"issue":"7","key":"426_CR11","doi-asserted-by":"publisher","first-page":"2073","DOI":"10.1287\/mnsc.2016.2455","volume":"63","author":"M Bodur","year":"2016","unstructured":"Bodur M, Luedtke JR (2016) Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Manag Sci 63(7):2073\u20132091","journal-title":"Manag Sci"},{"issue":"1","key":"426_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/ijoc.2016.0717","volume":"29","author":"M Bodur","year":"2017","unstructured":"Bodur M, Dash S, G\u00fcnl\u00fck O, Luedtke J (2017) Strengthened benders cuts for stochastic integer programs with continuous recourse. INFORMS J Comput 29(1):77\u201391","journal-title":"INFORMS J Comput"},{"issue":"1","key":"426_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0167-6377(98)00050-9","volume":"24","author":"CC Car\u00f8e","year":"1999","unstructured":"Car\u00f8e CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper Res Lett 24(1):37\u201345","journal-title":"Oper Res Lett"},{"issue":"2","key":"426_CR14","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/S0377-2217(96)00399-2","volume":"101","author":"CC Car\u00f8e","year":"1997","unstructured":"Car\u00f8e CC, Tind J (1997) A cutting-plane approach to mixed 0\u20131 stochastic integer programs. Eur J Oper Res 101(2):306\u2013316","journal-title":"Eur J Oper Res"},{"issue":"1","key":"426_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10479-006-0001-3","volume":"144","author":"JF Cordeau","year":"2006","unstructured":"Cordeau JF, Pasin F, Solomon MM (2006) An integrated model for logistics network design. Ann Oper Res 144(1):59\u201382","journal-title":"Ann Oper Res"},{"issue":"6","key":"426_CR16","doi-asserted-by":"publisher","first-page":"1429","DOI":"10.1016\/j.cor.2003.11.012","volume":"32","author":"AM Costa","year":"2005","unstructured":"Costa AM (2005) A survey on benders decomposition applied to fixed-charge network design problems. Comput Oper Res 32(6):1429\u20131450","journal-title":"Comput Oper Res"},{"issue":"1","key":"426_CR17","doi-asserted-by":"publisher","first-page":"03","DOI":"10.1590\/S0101-74382012005000005","volume":"32","author":"AM Costa","year":"2012","unstructured":"Costa AM, Cordeau JF, Gendron B, Laporte G (2012) Accelerating benders decomposition with heuristicmaster problem solutions. Pesquisa Operacional 32(1):03\u201320","journal-title":"Pesquisa Operacional"},{"key":"426_CR18","volume-title":"Partial Benders decomposition strategies for two-stage stochastic integer programs","author":"TG Crainic","year":"2016","unstructured":"Crainic TG, Hewitt M, Maggioni F, Rei W (2016) Partial Benders decomposition strategies for two-stage stochastic integer programs. Universit\u00e9 du Qu\u00e9bec \u00e0 Montr\u00e9al, Iteruniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT)"},{"issue":"1","key":"426_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s10107-009-0300-y","volume":"128","author":"M Fischetti","year":"2011","unstructured":"Fischetti M, Lodi A, Tramontani A (2011) On the separation of disjunctive cuts. Math Prog 128(1):205\u2013230","journal-title":"Math Prog"},{"issue":"1","key":"426_CR20","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s10107-012-0615-y","volume":"144","author":"D Gade","year":"2014","unstructured":"Gade D, K\u00fc\u00e7\u00fckyavuz S, Sen S (2014) Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math Prog 144(1):39\u201364","journal-title":"Math Prog"},{"issue":"1","key":"426_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.ejor.2016.04.058","volume":"255","author":"B Gendron","year":"2016","unstructured":"Gendron B, Scutell\u00e0 MG, Garroppo RG, Nencioni G, Tavanti L (2016) A branch-and-benders-cut method for nonlinear power design in green wireless local area networks. Eur J Oper Res 255(1):151\u2013162","journal-title":"Eur J Oper Res"},{"issue":"4","key":"426_CR22","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s12532-017-0118-1","volume":"9","author":"MR K\u0131l\u0131n\u00e7","year":"2017","unstructured":"K\u0131l\u0131n\u00e7 MR, Linderoth J, Luedtke J (2017) Lift-and-project cuts for convex mixed integer nonlinear programs. Math Programm Comput 9(4):499\u2013526. https:\/\/doi.org\/10.1007\/s12532-017-0118-1","journal-title":"Math Programm Comput"},{"issue":"3","key":"426_CR23","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1287\/mnsc.24.3.312","volume":"24","author":"D McDaniel","year":"1977","unstructured":"McDaniel D, Devine M (1977) A modified benders\u2019 partitioning algorithm for mixed integer programming. Manag Sci 24(3):312\u2013319","journal-title":"Manag Sci"},{"key":"426_CR24","unstructured":"Ntaimo L (2004) Decomposition algorithms for stochastic combinatorial optimization: Computational experiments and extensions. PhD thesis, The University of Arizona"},{"issue":"1","key":"426_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10898-011-9817-8","volume":"55","author":"L Ntaimo","year":"2013","unstructured":"Ntaimo L (2013) Fenchel decomposition for stochastic mixed-integer programming. J Global Optim 55(1):141\u2013163","journal-title":"J Global Optim"},{"key":"426_CR26","first-page":"555","volume-title":"Handbooks in operations research and management science stochastic programming","author":"WB Powell","year":"2003","unstructured":"Powell WB, Topaloglu H (2003) Stochastic programming in transportation and logistics. Handbooks in operations research and management science stochastic programming. Elsevier, Amsterdam, pp 555\u2013635"},{"key":"426_CR27","doi-asserted-by":"crossref","unstructured":"Qi Y, Sen S (2017) The Ancestral Benders\u2019 cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math Programm Ser A and B 161(1-2)","DOI":"10.1007\/s10107-016-1006-6"},{"key":"426_CR28","doi-asserted-by":"crossref","unstructured":"Rahmaniani R, Crainic T, Gendreau M, Rei W (2017a) A Benders decomposition method for two-stage stochastic network design problems. CIRRELT, Centre interuniversitaire de recherche sur les r\u00e9seaux d\u2019entreprise","DOI":"10.1137\/17M1128204"},{"issue":"3","key":"426_CR29","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1016\/j.ejor.2016.12.005","volume":"259","author":"R Rahmaniani","year":"2017","unstructured":"Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The benders decomposition algorithm: a literature review. Eur J Oper Res 259(3):801\u2013817","journal-title":"Eur J Oper Res"},{"issue":"6","key":"426_CR30","doi-asserted-by":"publisher","first-page":"6627","DOI":"10.1016\/j.eswa.2010.11.075","volume":"38","author":"GK Saharidis","year":"2011","unstructured":"Saharidis GK, Boile M, Theofanis S (2011) Initialization of the benders master problem using valid inequalities applied to fixed-charge network problems. Expert Syst Appl 38(6):6627\u20136636","journal-title":"Expert Syst Appl"},{"issue":"1","key":"426_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-004-0566-z","volume":"104","author":"S Sen","year":"2005","unstructured":"Sen S, Higle JL (2005) The c3 theorem and a d2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math Program 104(1):1\u201320","journal-title":"Math Program"},{"issue":"2","key":"426_CR32","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10107-005-0592-5","volume":"106","author":"S Sen","year":"2006","unstructured":"Sen S, Sherali HD (2006) Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Math Program 106(2):203\u2013223","journal-title":"Math Program"},{"issue":"1","key":"426_CR33","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10479-011-1050-9","volume":"210","author":"L Tang","year":"2013","unstructured":"Tang L, Jiang W, Saharidis GKD (2013) An improved benders decomposition algorithm for the logistics facility location problem with capacity expansions. Ann Oper Res 210(1):165\u2013190","journal-title":"Ann Oper Res"},{"key":"426_CR34","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.cor.2018.02.020","volume":"95","author":"S Vadlamani","year":"2018","unstructured":"Vadlamani S, Schweitzer D, Medal H, Nandi A, Eksioglu B (2018) A mixed-integer programming approach for locating jamming devices in a flow-jamming attack. Comput Oper Res 95:83\u201396","journal-title":"Comput Oper Res"},{"issue":"4","key":"426_CR35","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1137\/0117061","volume":"17","author":"R Van Slyke","year":"1969","unstructured":"Van Slyke R, Wets R (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J Appl Math 17(4):638\u2013663","journal-title":"SIAM J Appl Math"},{"key":"426_CR36","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.omega.2018.02.008","volume":"83","author":"C Weskamp","year":"2019","unstructured":"Weskamp C, Koberstein A, Schwartz F, Suhl L, Vo\u00df S (2019) A two-stage stochastic programming approach for identifying optimal postponement strategies in supply chains with uncertain demand. Omega 83:123\u2013138","journal-title":"Omega"},{"key":"426_CR37","unstructured":"Wesselman F (2010) Generating general-purpose cutting planes for mixed-integer programs. phdthesis, Universit\u00e4t Padeborn"},{"issue":"1","key":"426_CR38","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ejor.2013.04.017","volume":"230","author":"C Wolf","year":"2013","unstructured":"Wolf C, Koberstein A (2013) Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested l-shaped method. Eur J Oper Res 230(1):143\u2013156","journal-title":"Eur J Oper Res"},{"key":"426_CR39","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.ejor.2014.05.010","volume":"239","author":"C Wolf","year":"2014","unstructured":"Wolf C, F\u00e1bi\u00e1n CI, Koberstein A, Suhl L (2014) Applying oracles of on-demand accuracy in two-stage stochastic programming: a computational study. Eur J Oper Res 239:437\u2013448","journal-title":"Eur J Oper Res"},{"key":"426_CR40","unstructured":"Zarandi MMF (2010) Using decomposition to solve facility location\/fleet management problems. PhD thesis, University of Toronto"},{"issue":"4","key":"426_CR41","doi-asserted-by":"publisher","first-page":"1933","DOI":"10.1137\/13092678X","volume":"24","author":"M Zhang","year":"2014","unstructured":"Zhang M, K\u00fc\u00e7\u00fckyavuz S (2014) Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J Optim 24(4):1933\u20131951","journal-title":"SIAM J Optim"}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-022-00426-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10287-022-00426-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-022-00426-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T01:06:23Z","timestamp":1668474383000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10287-022-00426-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,5]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["426"],"URL":"https:\/\/doi.org\/10.1007\/s10287-022-00426-y","relation":{},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"type":"print","value":"1619-697X"},{"type":"electronic","value":"1619-6988"}],"subject":[],"published":{"date-parts":[[2022,5,5]]},"assertion":[{"value":"7 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest (such as honoraria; educational grants; participation in speakers\u2019 bureaus; membership, employment, consultancies, stock ownership, or other equity interest; and expert testimony or patent-licensing arrangements), or non-financial interest (such as personal or professional relationships, affiliations, knowledge or beliefs) in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}