Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse

We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2018-01, Vol.30 (1), p.57-70
Main Authors: van Ackooij, Wim, de Oliveira, Welington, Song, Yongjia
Format: Article
Language:English
Subjects:
Decomposition (Mathematics)
level decomposition
Linear programming
Methods
Problem solving
scenario reduction
Stochastic models
Stochastic programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3
cites cdi_FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3
container_end_page 70
container_issue 1
container_start_page 57
container_title INFORMS journal on computing
container_volume 30
creator van Ackooij, Wim
de Oliveira, Welington
Song, Yongjia
description We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors computed at certain first-stage solutions. The proposed approaches rely on the level decomposition with on-demand accuracy to dynamically adjust partitions until an optimal solution is found. Numerical experiments on a large set of test problems including instances with up to one hundred thousand scenarios show the effectiveness of the proposed approaches. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0765 .
doi_str_mv 10.1287/ijoc.2017.0765
format article
fullrecord <record><control><sourceid>gale_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1287_ijoc_2017_0765</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A532528372</galeid><sourcerecordid>A532528372</sourcerecordid><originalsourceid>FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3</originalsourceid><addsrcrecordid>eNqFktFrFDEQxhdRsFZffQ4IPrlnkr3sbh7P1trCicWrzyGbTPZy7G7OTO5a_3tzVqgHBxJIhuT3zUyGryjeMjpjvG0--k0wM05ZM6NNLZ4VZ0zwuhSCt89zTCUrZSvql8UrxA2ldF7N5VkRF1Zvk98DudUx-eTDVH7SCJYsYQ8DuQQTxm3APy_kK6R1sEhciGQVhr2fenJ3H8pV0j2QVQpmrTF5Q25j6KMekdz7tCZX_iEn_J5T7SLC6-KF0wPCm7_nefHj6vPdxXW5_Pbl5mKxLI1gNJVWaudYA8LZem5bUdFWyIp3Bhpb69p1RtRaUO1kZ7vGia6tZT1nknFps8ZW58W7x7zbGH7uAJPa5PpTLqk4qxjPE2nlE9XrAZSfXEhRm9GjUQtR8Ty9quGZKk9QPUwQ9RAmcD5fH_GzE3xeFkZvTgreHwkyk-Ah9XqHqI7BD_-A3Q79BJg39P064SN_qhETA2IEp7bRjzr-Uoyqg23UwTbqYBt1sM3TTw9NxxH_x_8G0EHDoQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2131209189</pqid></control><display><type>article</type><title>Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse</title><source>Business Source Ultimate</source><creator>van Ackooij, Wim ; de Oliveira, Welington ; Song, Yongjia</creator><creatorcontrib>van Ackooij, Wim ; de Oliveira, Welington ; Song, Yongjia</creatorcontrib><description>We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors computed at certain first-stage solutions. The proposed approaches rely on the level decomposition with on-demand accuracy to dynamically adjust partitions until an optimal solution is found. Numerical experiments on a large set of test problems including instances with up to one hundred thousand scenarios show the effectiveness of the proposed approaches. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0765 .</description><identifier>ISSN: 1091-9856</identifier><identifier>EISSN: 1526-5528</identifier><identifier>EISSN: 1091-9856</identifier><identifier>DOI: 10.1287/ijoc.2017.0765</identifier><language>eng</language><publisher>Linthicum: INFORMS</publisher><subject>Decomposition (Mathematics) ; level decomposition ; Linear programming ; Methods ; Problem solving ; scenario reduction ; Stochastic models ; Stochastic programming</subject><ispartof>INFORMS journal on computing, 2018-01, Vol.30 (1), p.57-70</ispartof><rights>COPYRIGHT 2018 Institute for Operations Research and the Management Sciences</rights><rights>Copyright Institute for Operations Research and the Management Sciences Winter 2018</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3</citedby><cites>FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3</cites><orcidid>0000-0002-9943-3572 ; 0000-0001-6839-522X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27923,27924</link.rule.ids></links><search><creatorcontrib>van Ackooij, Wim</creatorcontrib><creatorcontrib>de Oliveira, Welington</creatorcontrib><creatorcontrib>Song, Yongjia</creatorcontrib><title>Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse</title><title>INFORMS journal on computing</title><description>We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors computed at certain first-stage solutions. The proposed approaches rely on the level decomposition with on-demand accuracy to dynamically adjust partitions until an optimal solution is found. Numerical experiments on a large set of test problems including instances with up to one hundred thousand scenarios show the effectiveness of the proposed approaches. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0765 .</description><subject>Decomposition (Mathematics)</subject><subject>level decomposition</subject><subject>Linear programming</subject><subject>Methods</subject><subject>Problem solving</subject><subject>scenario reduction</subject><subject>Stochastic models</subject><subject>Stochastic programming</subject><issn>1091-9856</issn><issn>1526-5528</issn><issn>1091-9856</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNqFktFrFDEQxhdRsFZffQ4IPrlnkr3sbh7P1trCicWrzyGbTPZy7G7OTO5a_3tzVqgHBxJIhuT3zUyGryjeMjpjvG0--k0wM05ZM6NNLZ4VZ0zwuhSCt89zTCUrZSvql8UrxA2ldF7N5VkRF1Zvk98DudUx-eTDVH7SCJYsYQ8DuQQTxm3APy_kK6R1sEhciGQVhr2fenJ3H8pV0j2QVQpmrTF5Q25j6KMekdz7tCZX_iEn_J5T7SLC6-KF0wPCm7_nefHj6vPdxXW5_Pbl5mKxLI1gNJVWaudYA8LZem5bUdFWyIp3Bhpb69p1RtRaUO1kZ7vGia6tZT1nknFps8ZW58W7x7zbGH7uAJPa5PpTLqk4qxjPE2nlE9XrAZSfXEhRm9GjUQtR8Ty9quGZKk9QPUwQ9RAmcD5fH_GzE3xeFkZvTgreHwkyk-Ah9XqHqI7BD_-A3Q79BJg39P064SN_qhETA2IEp7bRjzr-Uoyqg23UwTbqYBt1sM3TTw9NxxH_x_8G0EHDoQ</recordid><startdate>20180101</startdate><enddate>20180101</enddate><creator>van Ackooij, Wim</creator><creator>de Oliveira, Welington</creator><creator>Song, Yongjia</creator><general>INFORMS</general><general>Institute for Operations Research and the Management Sciences</general><scope>AAYXX</scope><scope>CITATION</scope><scope>N95</scope><scope>XI7</scope><scope>JQ2</scope><orcidid>https://orcid.org/0000-0002-9943-3572</orcidid><orcidid>https://orcid.org/0000-0001-6839-522X</orcidid></search><sort><creationdate>20180101</creationdate><title>Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse</title><author>van Ackooij, Wim ; de Oliveira, Welington ; Song, Yongjia</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Decomposition (Mathematics)</topic><topic>level decomposition</topic><topic>Linear programming</topic><topic>Methods</topic><topic>Problem solving</topic><topic>scenario reduction</topic><topic>Stochastic models</topic><topic>Stochastic programming</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>van Ackooij, Wim</creatorcontrib><creatorcontrib>de Oliveira, Welington</creatorcontrib><creatorcontrib>Song, Yongjia</creatorcontrib><collection>CrossRef</collection><collection>Gale Business: Insights</collection><collection>Business Insights: Essentials</collection><collection>ProQuest Computer Science Collection</collection><jtitle>INFORMS journal on computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>van Ackooij, Wim</au><au>de Oliveira, Welington</au><au>Song, Yongjia</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse</atitle><jtitle>INFORMS journal on computing</jtitle><date>2018-01-01</date><risdate>2018</risdate><volume>30</volume><issue>1</issue><spage>57</spage><epage>70</epage><pages>57-70</pages><issn>1091-9856</issn><eissn>1526-5528</eissn><eissn>1091-9856</eissn><abstract>We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors computed at certain first-stage solutions. The proposed approaches rely on the level decomposition with on-demand accuracy to dynamically adjust partitions until an optimal solution is found. Numerical experiments on a large set of test problems including instances with up to one hundred thousand scenarios show the effectiveness of the proposed approaches. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0765 .</abstract><cop>Linthicum</cop><pub>INFORMS</pub><doi>10.1287/ijoc.2017.0765</doi><tpages>14</tpages><orcidid>https://orcid.org/0000-0002-9943-3572</orcidid><orcidid>https://orcid.org/0000-0001-6839-522X</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 1091-9856
ispartof INFORMS journal on computing, 2018-01, Vol.30 (1), p.57-70
issn 1091-9856
1526-5528
1091-9856
language eng
recordid cdi_crossref_primary_10_1287_ijoc_2017_0765
source Business Source Ultimate
subjects Decomposition (Mathematics)
level decomposition
Linear programming
Methods
Problem solving
scenario reduction
Stochastic models
Stochastic programming
title Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T17%3A26%3A17IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Adaptive%20Partition-Based%20Level%20Decomposition%20Methods%20for%20Solving%20Two-Stage%20Stochastic%20Programs%20with%20Fixed%20Recourse&rft.jtitle=INFORMS%20journal%20on%20computing&rft.au=van%20Ackooij,%20Wim&rft.date=2018-01-01&rft.volume=30&rft.issue=1&rft.spage=57&rft.epage=70&rft.pages=57-70&rft.issn=1091-9856&rft.eissn=1526-5528&rft_id=info:doi/10.1287/ijoc.2017.0765&rft_dat=%3Cgale_cross%3EA532528372%3C/gale_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c510t-d9aff17e5fd64d853085932bce7d6a6fbc56a50af9bdb7f5b8696419129d5fdd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2131209189&rft_id=info:pmid/&rft_galeid=A532528372&rfr_iscdi=true