Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs

dc.contributor.authorBüyüktahtakın, İ. Esraen
dc.date.accessioned2025-03-14T14:00:42Zen
dc.date.available2025-03-14T14:00:42Zen
dc.date.issued2021-12-01en
dc.description.abstractThis paper presents a new and general approach, named “Stage-t Scenario Dominance,” to solve the risk-averse multi-stage stochastic mixed-integer programs (M-SMIPs). Given a monotonic objective function, our method derives a partial ordering of scenarios by pairwise comparing the realization of uncertain parameters at each time stage under each scenario. Specifically, we derive bounds and implications from the “Stage-t Scenario Dominance” by using the partial ordering of scenarios and solving a subset of individual scenario sub-problems up to stage t. Using these inferences, we generate new cutting planes to tackle the computational difficulty of risk-averse M-SMIPs. We also derive results on the minimum number of scenario-dominance relations generated. We demonstrate the use of this methodology on a stochastic version of the mean-conditional value-at-risk (CVaR) dynamic knapsack problem. Our computational experiments address those instances that have uncertainty, which correspond to the objective, left-hand side, and right-hand side parameters. Computational results show that our “scenario dominance"-based method can reduce the solution time for mean-risk, stochastic, multi-stage, and multi-dimensional knapsack problems with both integer and continuous variables, whose structure is similar to the mean-risk M-SMIPs, with varying risk characteristics by one-to-two orders of magnitude for varying numbers of random variables in each stage. Computational results also demonstrate that strong dominance cuts perform well for those instances with ten random variables in each stage, and ninety random variables in total. The proposed scenario dominance framework is general and can be applied to a wide range of risk-averse and risk-neutral M-SMIP problems.en
dc.description.versionPublished versionen
dc.format.extentPages 1-35en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1007/s10479-021-04388-3en
dc.identifier.eissn1572-9338en
dc.identifier.issn0254-5330en
dc.identifier.issue1en
dc.identifier.orcidBuyuktahtakin Toy, Esra [0000-0001-8928-2638]en
dc.identifier.urihttps://hdl.handle.net/10919/124867en
dc.identifier.volume309en
dc.language.isoenen
dc.publisherSpringeren
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.titleStage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programsen
dc.title.serialAnnals of Operations Researchen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
dc.type.otherJournal Articleen
pubs.organisational-groupVirginia Techen
pubs.organisational-groupVirginia Tech/Engineeringen
pubs.organisational-groupVirginia Tech/Engineering/Industrial and Systems Engineeringen
pubs.organisational-groupVirginia Tech/All T&R Facultyen
pubs.organisational-groupVirginia Tech/Engineering/COE T&R Facultyen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
1. Buyuktahtakin2022_ANOR_ScenarioDominance.pdf
Size:
688.33 KB
Format:
Adobe Portable Document Format
Description:
Published version
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Plain Text
Description: