On the number of stages in multistage stochastic programs

Giovanni Pantuso () and Trine K. Boomsma ()
Additional contact information
Giovanni Pantuso: University of Copenhagen
Trine K. Boomsma: University of Copenhagen

Annals of Operations Research, 2020, vol. 292, issue 2, No 2, 603 pages

Abstract: Abstract 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.

Keywords: Multistage stochastic programming; Value of the stochastic solution; Bounds; Optimization under uncertainty (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03181-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:292:y:2020:i:2:d:10.1007_s10479-019-03181-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03181-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().