On the number of stages in multistage stochastic programs

TY - JOUR

T1 - On the number of stages in multistage stochastic programs

AU - Pantuso, Giovanni

AU - Boomsma, Trine K.

PY - 2020/9/1

Y1 - 2020/9/1

N2 - Multistage stochastic programs serve to make sequential decisions conditional on a gradual realization of some stochastic process. The progressive arrival of new information divides a problem into stages. As the number of stages increases, however, the applicability of stochastic programming is halted by the curse of dimensionality. A commonly used approximation is obtained by replacing the random parameters by their expected values, which results in a problem with fewer stages. The present paper suggests metrics to support the choice of the number of stages: The value of an extended expected value (EV) problem which accounts for stochastic approximations, the Expected result of using the expected value solution (EEV), the value of the stochastic solution, and the values of two Wait-and-See (WS) approximations. We show that for linear minimization problems with random right-hand-side, the value of the EV problem provides a lower bound that improves with the number of stages. The same holds for the WS approximations for general linear minimization problems and with one of the approximations improving the EV bound. In contrast, we show that the upper bound provided by the EV solution may not improve with the number of stages. Finally, we define the marginal benefit of including an additional stage in an EV approximation and demonstrate how to use it in a heuristic. We apply our approach to a hedging problem and confirm that increasing the number of stages does not necessarily foster better decisions.

AB - Multistage stochastic programs serve to make sequential decisions conditional on a gradual realization of some stochastic process. The progressive arrival of new information divides a problem into stages. As the number of stages increases, however, the applicability of stochastic programming is halted by the curse of dimensionality. A commonly used approximation is obtained by replacing the random parameters by their expected values, which results in a problem with fewer stages. The present paper suggests metrics to support the choice of the number of stages: The value of an extended expected value (EV) problem which accounts for stochastic approximations, the Expected result of using the expected value solution (EEV), the value of the stochastic solution, and the values of two Wait-and-See (WS) approximations. We show that for linear minimization problems with random right-hand-side, the value of the EV problem provides a lower bound that improves with the number of stages. The same holds for the WS approximations for general linear minimization problems and with one of the approximations improving the EV bound. In contrast, we show that the upper bound provided by the EV solution may not improve with the number of stages. Finally, we define the marginal benefit of including an additional stage in an EV approximation and demonstrate how to use it in a heuristic. We apply our approach to a hedging problem and confirm that increasing the number of stages does not necessarily foster better decisions.

KW - Bounds

KW - Multistage stochastic programming

KW - Optimization under uncertainty

KW - Value of the stochastic solution

UR - http://www.scopus.com/inward/record.url?scp=85062612915&partnerID=8YFLogxK

U2 - 10.1007/s10479-019-03181-7

DO - 10.1007/s10479-019-03181-7

M3 - Journal article

AN - SCOPUS:85062612915

SN - 0254-5330

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -