{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:58:29Z","timestamp":1760299109443},"reference-count":21,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2015,3,20]],"date-time":"2015-03-20T00:00:00Z","timestamp":1426809600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>In this article, we investigate the stochastic maximum weight forest problem. We present two mathematical formulations for the problem: a polynomial sized one based on the characterization of forests in graphs and a formulation with an exponential number of constraints. We give a proof of the correctness of the new formulation and present a polynomial reduction from the set cover problem to give some insight about the complexity of this problem. We introduce an L\u2010shaped decomposition approach for the polynomial formulation, thus allowing the optimal solution of large scale instances with up to 90 nodes. Finally, we propose a Kruskal based variable neighborhood search (VNS) metaheuristic to compute near optimal solutions with significantly less computational effort. Our numerical results show that the VNS approach provides tight near optimal solutions with a gap less than 1% for most of the instances. \u00a9 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 289\u2013305 2015<\/jats:p>","DOI":"10.1002\/net.21610","type":"journal-article","created":{"date-parts":[[2015,3,20]],"date-time":"2015-03-20T17:18:43Z","timestamp":1426871923000},"page":"289-305","source":"Crossref","is-referenced-by-count":12,"title":["Stochastic maximum weight forest problem"],"prefix":"10.1002","volume":"65","author":[{"given":"Pablo","family":"Adasme","sequence":"first","affiliation":[{"name":"Departamento de Ingenier\u00eda El\u00e9ctrica Universidad de Santiago de Chile Avenida Ecuador 3519 Santiago Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael","family":"Andrade","sequence":"additional","affiliation":[{"name":"Departamento de Estat\u00edstica e Matem\u00e1tica Aplicada Universidade Federal do Cear\u00e1 Campus do Pici \u2010 Bloco 910 CEP 60440\u2010900 Fortaleza Cear\u00e1 Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Letournel","sequence":"additional","affiliation":[{"name":"Laboratoire de Recherche en Informatique Universit\u00e9 de Paris\u2010Sud XI B\u00e2t. 650 91405 Orsay Cedex France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdel","family":"Lisser","sequence":"additional","affiliation":[{"name":"Laboratoire de Recherche en Informatique Universit\u00e9 de Paris\u2010Sud XI B\u00e2t. 650 91405 Orsay Cedex France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2015,3,20]]},"reference":[{"key":"e_1_2_8_2_1","first-page":"29","article-title":"A polynomial formulation for the stochastic maximum weight forest problem","volume":"41","author":"Adasme P.","year":"2013","journal-title":"ENDM"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0440"},{"key":"e_1_2_8_4_1","volume-title":"L\u2010shaped method for two stage problems of stochastic convex programming, Technical Report 93\u201322","author":"Birge J.","year":"1993"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-010-0122-z"},{"key":"e_1_2_8_6_1","volume-title":"Introduction to algorithms","author":"Cormen T.H.","year":"2009"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.12.004"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20079"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-010-9566-0"},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00100-4"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(93)90002-X"},{"key":"e_1_2_8_13_1","volume-title":"Is the polytope associated with a two stage stochastic level problem TDI ?, Technical Report LRI\u20101546","author":"Letournel M.","year":"2010"},{"key":"e_1_2_8_14_1","volume-title":"Laboratoire de Recherche en Informatique","author":"Letournel M.","year":"2013"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90028-N"},{"key":"e_1_2_8_16_1","unstructured":"Mathworks documentation webpage. Available at:http:\/\/ www.mathworks.com\/help\/bioinfo\/ref\/graphtraverse.html."},{"key":"e_1_2_8_17_1","unstructured":"Mathworks documentation webpage. Available at:http:\/\/ www.mathworks.com\/help\/bioinfo\/ref\/graphpred2path.html."},{"key":"e_1_2_8_18_1","first-page":"371","volume-title":"Handbooks in operations research and management science","author":"Pulleyblank W.","year":"1989"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718751"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117061"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21610","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T01:50:11Z","timestamp":1694569811000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,20]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["10.1002\/net.21610"],"URL":"https:\/\/doi.org\/10.1002\/net.21610","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,20]]}}}