{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T13:57:44Z","timestamp":1790431064926,"version":"4.1.0"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>This paper describes a Benders decomposition algorithm capable of efficiently solving large-scale instances of the well-known multicommodity capacitated network design problem with demand uncertainty. The problem is important because it models many applications, including telecommunications, transportation, and logistics. This problem has been tackled in the literature with meta-heuristics and exact methods, but many benchmark instances, even though of moderate size, remain unsolved. To successfully apply the Benders method to these instances, we propose various acceleration techniques, including the use of cutting planes, partial decomposition, heuristics, stronger cuts, reduction and warm-start strategies. Extensive computational experiments on benchmark instances were conducted to evaluate the efficiency and robustness of the algorithm as well as of the proposed strategies. The numerical results confirm the superiority of the proposed algorithm over existing ones.<\/jats:p>","DOI":"10.1137\/17m1128204","type":"journal-article","created":{"date-parts":[[2018,3,27]],"date-time":"2018-03-27T12:45:59Z","timestamp":1522154759000},"page":"875-903","source":"Crossref","is-referenced-by-count":72,"title":["Accelerating the Benders Decomposition Method: Application to Stochastic Network Design Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Ragheb","family":"Rahmaniani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Teodor Gabriel","family":"Crainic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michel","family":"Gendreau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter","family":"Rei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.07.009"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386316"},{"key":"atypb3","unstructured":"J. R. Birge and F. Louveaux,\n                      Introduction to Stochastic Programming\n                      , Springer, New York, 1997."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90159-2"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2016.0717"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-015-9306-1"},{"key":"atypb7","unstructured":"M. Chouman, T. G. Crainic, and B. Gendron,\n                      The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design\n                      , Publication CIRRELT-2014-35, Centre interuniversitaire de recherche sur les re\u0301seaux d'entreprise, la logistique et le transport, Universite\u0301 de Montre\u0301al, 2014."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2015.0665"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0286"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2003.11.012"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90287-X"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00233-7"},{"key":"atypb13","first-page":"299","volume":"46","author":"Crainic T. G.","year":"2008","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00310-3"},{"key":"atypb15","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1002\/net.20456","volume":"58","author":"Crainic T. G.","year":"2011","journal-title":"Networks"},{"key":"atypb16","unstructured":"T. G. Crainic, M. Hewitt, and W. Rei,\n                      Partial decomposition strategies for two-stage stochastic integer programs\n                      , Publication CIRRELT-2014-13, Centre interuniversitaire de recherche sur les re\u0301seaux d'entreprise, la logistique et le transport, Universite\u0301 de Montre\u0301al, 2014."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.08.020"},{"key":"atypb18","unstructured":"T. G. Crainic, M. Hewitt, and W. Rei,\n                      Partial Benders decomposition strategies for two-stage stochastic integer programs\n                      , Publication CIRRELT-2016-37, Centre interuniversitaire de recherche sur les re\u0301seaux d'entreprise, la logistique et le transport, Universite\u0301 de Montre\u0301al, 2016."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(06)14008-6"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10287-006-0026-8"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2016.2461"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"B. Gendron, T. G. Crainic, and A. Frangioni,\n                      Multicommodity capacitated network design\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4615-5087-7_1"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.04.058"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.16.11.652"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.822"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2262153"},{"key":"atypb27","unstructured":"C. Luong,\n                      An examination of Benders decomposition approaches in large-scale healthcare optimization problems\n                      , Master's thesis, University of Toronto, 2015."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1287\/opre.29.3.464"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.24.3.312"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014554606793"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00118-0"},{"key":"atypb33","unstructured":"R. Pacqueau, S. Francois, and H. Le Nguyen,\n                      A fast and accurate algorithm for stochastic integer programming, appllied to stochastic shift scheduling\n                      , Publication G-2012-29, Groupe d'e\u0301tudes et de recherche en analyse des de\u0301cisions (GERAD), Universite\u0301 de Montre\u0301al, 2012."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.01.005"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.10.033"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.12.005"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s00170-013-5602-9"},{"key":"atypb38","first-page":"183","author":"Raidl G. R.","year":"2014","journal-title":"New York"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0296"},{"key":"atypb40","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton Math. Ser. 28, Princeton University Press, Princeton, 1970,https:\/\/www.math.washington.edu\/~rtr\/papers.html."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018965626303"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(96)00401-8"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2010.11.075"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.compchemeng.2009.10.002"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.01.046"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0883-6"},{"key":"atypb47","unstructured":"X. Wang, T. G. Crainic, and S. Wallace,\n                      Stochastic scheduled service network design: The value of deterministic solutions\n                      , Publication CIRRELT-2016-14, Centre interuniversitaire de recherche sur les re\u0301seaux d'entreprise, la logistique et le transport, Universite\u0301 de Montre\u0301al, 2016."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497318700"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1128204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:59Z","timestamp":1787336159000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1128204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1128204"],"URL":"https:\/\/doi.org\/10.1137\/17m1128204","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}