TY - JOUR
T1 - Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs
AU - Büyüktahtakın, I. Esra
N1 - Funding Information:
The author gratefully acknowledges the partial support of the National Science Foundation CAREER Award co-funded by the CBET/ENG Environmental Sustainability program and the Division of Mathematical Sciences in MPS/NSF Under CMMI-1100765 and Grant # CBET-1554018. We thank the Academic Research and Computing Systems (ARCS) center of NJIT for their support with the NJIT ARCS Kong cluster, which is used to perform our computational testing. We thank three anonymous referees, the associate editor, and the editor, whose remarks helped to improve the content and clarity of our exposition. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/ ), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Funding Information:
The author gratefully acknowledges the partial support of the National Science Foundation CAREER Award co-funded by the CBET/ENG Environmental Sustainability program and the Division of Mathematical Sciences in MPS/NSF Under CMMI-1100765 and Grant # CBET-1554018. We thank the Academic Research and Computing Systems (ARCS) center of NJIT for their support with the NJIT ARCS Kong cluster, which is used to perform our computational testing. We thank three anonymous referees, the associate editor, and the editor, whose remarks helped to improve the content and clarity of our exposition.
Publisher Copyright:
© 2022, The Author(s).
PY - 2022/2
Y1 - 2022/2
N2 - This 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.
AB - This 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.
KW - Bounds
KW - Conditional value-at-risk (CVaR)
KW - Cutting planes
KW - Partial ordering of scenarios
KW - Risk-averse
KW - Stage-t scenario dominance
KW - Stochastic dynamic knapsack problem
KW - Time-consistent mean-risk multi-stage stochastic mixed-integer programs
UR - http://www.scopus.com/inward/record.url?scp=85120374826&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120374826&partnerID=8YFLogxK
U2 - 10.1007/s10479-021-04388-3
DO - 10.1007/s10479-021-04388-3
M3 - Article
AN - SCOPUS:85120374826
SN - 0254-5330
VL - 309
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 1
ER -