{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T02:56:12Z","timestamp":1764212172579,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:00:00Z","timestamp":1599436800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T00:00:00Z","timestamp":1599436800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["451-17-034 4043"],"award-info":[{"award-number":["451-17-034 4043"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.<\/jats:p>","DOI":"10.1007\/s10107-020-01559-1","type":"journal-article","created":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T15:03:47Z","timestamp":1599491027000},"page":"761-794","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models"],"prefix":"10.1007","volume":"190","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8045-4517","authenticated-orcid":false,"given":"Niels","family":"van der Laan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ward","family":"Romeijnders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,7]]},"reference":[{"issue":"6","key":"1559_CR1","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/j.orl.2013.07.009","volume":"41","author":"S Ahmed","year":"2013","unstructured":"Ahmed, S.: A scenario decomposition algorithm for 0\u20131 stochastic programs. Oper. Res. Lett. 41(6), 565\u2013569 (2013)","journal-title":"Oper. Res. Lett."},{"key":"1559_CR2","unstructured":"Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G., Qiu, F., Sen, S.: SIPLIB: a stochastic integer programming test problem library. https:\/\/www2.isye.gatech.edu\/~sahmed\/siplib (2015)"},{"key":"1559_CR3","unstructured":"Ahmed, S., Shapiro, A.: The sample average approximation method for stochastic programs with integer recourse. Preprint available from https:\/\/www.optimization-online.org (2002)"},{"issue":"1","key":"1559_CR4","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1137\/16M1083955","volume":"28","author":"M Bansal","year":"2018","unstructured":"Bansal, M., Huang, K.L., Mehrotra, S.: Tight second stage formulations in two-stage stochastic mixed integer programs. SIAM J. Optim. 28(1), 788\u2013819 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2\u20133","key":"1559_CR5","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10107-006-0720-x","volume":"108","author":"G Bayraksan","year":"2006","unstructured":"Bayraksan, G., Morton, D.P.: Assessing solution quality in stochastic programs. Math. Program. 108(2\u20133), 495\u2013514 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"1559_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01386316","volume":"4","author":"JF Benders","year":"1962","unstructured":"Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238\u2013252 (1962)","journal-title":"Numer. Math."},{"issue":"3","key":"1559_CR7","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0377-2217(88)90159-2","volume":"34","author":"JR Birge","year":"1988","unstructured":"Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3), 384\u2013392 (1988)","journal-title":"Eur. J. Oper. Res."},{"issue":"1\u20132","key":"1559_CR8","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, C.C., Schultz, R.: Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1\u20132), 37\u201345 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"1559_CR9","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.: Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Math. Program. 144(1\u20132), 39\u201364 (2014)","journal-title":"Math. Program."},{"key":"1559_CR10","doi-asserted-by":"crossref","unstructured":"Gassmann, H.I., Ziemba, W.T. (eds.): Stochastic programming: applications in finance, energy, planning and logistics, World Scientific Series in Finance, vol. 4. World Scientific (2013)","DOI":"10.1142\/8497"},{"issue":"4","key":"1559_CR11","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0024-3795(69)90017-2","volume":"2","author":"R Gomory","year":"1969","unstructured":"Gomory, R.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2(4), 451\u2013558 (1969)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"1559_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.orl.2015.03.008","volume":"43","author":"G Guo","year":"2015","unstructured":"Guo, G., Hackebeil, G., Ryan, S.M., Watson, J.P., Woodruff, D.L.: Integration of progressive hedging and dual decomposition in stochastic integer programs. Oper. Res. Lett. 43(3), 311\u2013316 (2015)","journal-title":"Oper. Res. Lett."},{"issue":"16","key":"1559_CR13","doi-asserted-by":"publisher","first-page":"3697","DOI":"10.1080\/002075499189998","volume":"37","author":"S Jorjani","year":"1999","unstructured":"Jorjani, S., Scott, C.H., Woodruff, D.L.: Selection of an optimal subset of sizes. Int. J. Prod. Res. 37(16), 3697\u20133710 (1999)","journal-title":"Int. J. Prod. Res."},{"issue":"2\u20133","key":"1559_CR14","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-006-0718-4","volume":"108","author":"WK Klein Haneveld","year":"2006","unstructured":"Klein Haneveld, W.K., Stougie, L., van der Vlerk, M.H.: Simple integer recourse models: convexity and convex approximations. Math. Program. 108(2\u20133), 435\u2013473 (2006)","journal-title":"Math. Program."},{"issue":"3","key":"1559_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0167-6377(93)90002-X","volume":"13","author":"G Laporte","year":"1993","unstructured":"Laporte, G., Louveaux, F.V.: The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3), 133\u2013142 (1993)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"1559_CR16","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0167-6377(98)00054-6","volume":"24","author":"WK Mak","year":"1999","unstructured":"Mak, W.K., Morton, D.P., Wood, R.K.: Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24(1\u20132), 47\u201356 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1559_CR17","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10898-011-9817-8","volume":"55","author":"L Ntaimo","year":"2013","unstructured":"Ntaimo, L.: Fenchel decomposition for stochastic mixed-integer programming. J. Glob. Optim. 55(1), 141\u2013163 (2013)","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1559_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s10898-004-5910-6","volume":"32","author":"L Ntaimo","year":"2005","unstructured":"Ntaimo, L., Sen, S.: The million-variable march for stochastic combinatorial optimization. J. Glob. Optim. 32(3), 385\u2013400 (2005)","journal-title":"J. Glob. Optim."},{"issue":"1\u20132","key":"1559_CR19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10107-016-1006-6","volume":"161","author":"Y Qi","year":"2017","unstructured":"Qi, Y., Sen, S.: The ancestral benders\u2019 cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming. Math. Program. 161(1\u20132), 193\u2013235 (2017)","journal-title":"Math. Program."},{"key":"1559_CR20","doi-asserted-by":"crossref","unstructured":"Rinnooy\u00a0Kan, A.H.G., Stougie, L.: Stochastic integer programming. In: Y.\u00a0Ermoliev, R.J.B. Wets (eds.) Numerical Techniques for Stochastic Optimization, Springer Series in Computational Mathematics, vol.\u00a010, pp. 201\u2013213. Springer (1988)","DOI":"10.1007\/978-3-642-61370-8_8"},{"key":"1559_CR21","doi-asserted-by":"crossref","unstructured":"Romeijnders, W., van der Laan, N.: Pseudo-valid cutting planes for two-stage mixed-integer stochastic programs with right-hand-side uncertainty. Operations Research (2020)","DOI":"10.1287\/opre.2019.1905"},{"issue":"2","key":"1559_CR22","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1287\/ijoc.2016.0725","volume":"29","author":"W Romeijnders","year":"2017","unstructured":"Romeijnders, W., Morton, D.P., van der Vlerk, M.H.: Assessing the quality of convex approximations for two-stage totally unimodular integer recourse models. INFORMS J. Comput. 29(2), 211\u2013231 (2017)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1559_CR23","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1137\/140986244","volume":"26","author":"W Romeijnders","year":"2016","unstructured":"Romeijnders, W., Schultz, R., van der Vlerk, M.H., Klein Haneveld, W.K.: A convex approximation for two-stage mixed-integer recourse models with a uniform error bound. SIAM J. Optim. 26(1), 426\u2013447 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1559_CR24","first-page":"17","volume":"19","author":"W Romeijnders","year":"2014","unstructured":"Romeijnders, W., Stougie, L., van der Vlerk, M.H.: Approximation in two-stage stochastic integer programming. Surv. Oper. Res. Manag. Sci. 19(1), 17\u201333 (2014)","journal-title":"Surv. Oper. Res. Manag. Sci."},{"issue":"1","key":"1559_CR25","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1137\/130945703","volume":"25","author":"W Romeijnders","year":"2015","unstructured":"Romeijnders, W., van der Vlerk, M.H., Klein Haneveld, W.K.: Convex approximations of totally unimodular integer recourse models: a uniform error bound. SIAM J. Optim. 25(1), 130\u2013158 (2015)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1559_CR26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-014-0829-2","volume":"157","author":"W Romeijnders","year":"2016","unstructured":"Romeijnders, W., van der Vlerk, M.H., Klein Haneveld, W.K.: Total variation bounds on the expectation of periodic functions with applications to recourse approximations. Math. Program. 157(1), 3\u201346 (2016)","journal-title":"Math. Program."},{"issue":"3","key":"1559_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF01580883","volume":"35","author":"A Ruszczy\u0144ski","year":"1986","unstructured":"Ruszczy\u0144ski, A.: A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35(3), 309\u2013333 (1986)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1559_CR28","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10107-003-0445-z","volume":"97","author":"R Schultz","year":"2003","unstructured":"Schultz, R.: Stochastic programming with integer variables. Math. Program. 97(1\u20132), 285\u2013309 (2003)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"1559_CR29","first-page":"229","volume":"83","author":"R Schultz","year":"1998","unstructured":"Schultz, R., Stougie, L., van der Vlerk, M.H.: Solving stochastic programs with integer recourse by enumeration: a framework using Gr\u00f6bner basis reductions. Math. Program. 83(1\u20133), 229\u2013252 (1998)","journal-title":"Math. Program."},{"key":"1559_CR30","first-page":"515","volume":"12","author":"S Sen","year":"2005","unstructured":"Sen, S.: Algorithms for stochastic mixed-integer programming models. Handb. Oper. Res. Manag. Sci. 12, 515\u2013558 (2005)","journal-title":"Handb. Oper. Res. Manag. Sci."},{"issue":"1","key":"1559_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, J.L.: The $$C^3$$ theorem and a $$D^2$$ algorithm for large scale stochastic mixed-integer programming: set convexification. Math. Program. 104(1), 1\u201320 (2005)","journal-title":"Math. Program."},{"issue":"4","key":"1559_CR32","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1137\/0117061","volume":"17","author":"RM Van Slyke","year":"1969","unstructured":"Van Slyke, R.M., Wets, R.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4), 638\u2013663 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"1559_CR33","unstructured":"van \u00a0der Vlerk, M.H.: Stochastic programming with integer recourse. Ph.D. thesis, University of Groningen, The Netherlands (1995)"},{"issue":"2","key":"1559_CR34","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s10107-003-0434-2","volume":"99","author":"MH van der Vlerk","year":"2004","unstructured":"van der Vlerk, M.H.: Convex approximations for complete integer recourse models. Math. Program. 99(2), 297\u2013310 (2004)","journal-title":"Math. Program."},{"issue":"1","key":"1559_CR35","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s10479-009-0591-7","volume":"177","author":"MH Van der Vlerk","year":"2010","unstructured":"Van der Vlerk, M.H.: Convex approximations for a class of mixed-integer recourse models. Ann. Oper. Res. 177(1), 139\u2013150 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"1559_CR36","doi-asserted-by":"publisher","first-page":"465","DOI":"10.2140\/pjm.1969.28.465","volume":"28","author":"DW Walkup","year":"1969","unstructured":"Walkup, D.W., Wets, R.J.B.: Lifting projections of convex polyhedra. Pac. J. Math. 28(2), 465\u2013475 (1969)","journal-title":"Pac. J. Math."},{"key":"1559_CR37","doi-asserted-by":"crossref","unstructured":"Wallace, S.W., Ziemba, W.T. (eds.): Applications of Stochastic Programming. MPS-SIAM Series on Optimization (2005)","DOI":"10.1137\/1.9780898718799"},{"issue":"4","key":"1559_CR38","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.: Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24(4), 1933\u20131951 (2014)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01559-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01559-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01559-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:55:58Z","timestamp":1633834558000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01559-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,7]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1559"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01559-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,9,7]]},"assertion":[{"value":"3 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}