More Web Proxy on the site http://driver.im/

research-article

Bounds and Approximations for Multistage Stochastic Programs

Authors:

Francesca Maggioni,

Georg Ch. PflugAuthors Info & Claims

SIAM Journal on Optimization, Volume 26, Issue 1

Pages 831 - 855

https://doi.org/10.1137/140971889

Published: 01 January 2016 Publication History

Abstract

Consider (typically large) multistage stochastic programs, which are defined on scenario trees as the basic data structure. It is well known that the computational complexity of the solution depends on the size of the tree, which itself increases typically exponentially fast with its height, i.e., the number of decision stages. For this reason approximations which replace the problem by a simpler one and allow bounding the optimal value are of great importance. In this paper we study several methods to obtain lower and upper bounds for multistage stochastic programs and we demonstrate their use in a multistage inventory problem.

References

[1]

K. M. Anstreicher, Linear programming in $O(n^3/ln \,n \cdot L)$ operations, SIAM J. Optim., 9 (1999), pp. 803--812.

[2]

J. R. Birge, The value of the stochastic solution in stochastic linear programs with fixed recourse, Math. Program., 24 (1982), pp. 314--325.

[3]

J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer-Verlag, New York, 1997.

[4]

D. Dentcheva and A. Ruszczyński, Optimization with stochastic dominance constraints, SIAM J. Optim., 14 (2003), pp. 548--566.

[5]

L. F. Escudero, A. Garín, M. Merino, and G. Pérez, The value of the stochastic solution in multistage problems, TOP, 15 (2007), pp. 48--64.

[6]

K. Frauendorfer and M. Schürle, Multistage stochastic programming: Barycentric approximation, in Encyclopedia of Optimization, Vol. 3, P. Pardalos, and C. A. Floudas eds., Kluwer Academic, Dordrecht, the Netherlands, 2001, pp. 576--580.

[7]

D. Kuhn, Generalized Bounds for Convex Multistage Stochastic Programs, Lecture Notes in Economi. and Math. Systems 548, Springer-Verlag, Berlin, 2005.

[8]

D. Kuhn, Aggregation and discretization in multistage stochastic programming, Math. Program. Ser. A, 113 (2008), pp. 61--94.

[9]

D. Kuhn, An information-based approximation scheme for stochastic optimization problems in continuous time, Math. Oper. Res., 34 (2009), pp. 428--444.

[10]

F. Maggioni and W. S. Wallace, Analyzing the quality of the expected value solution in stochastic programming, Ann. Oper. Res., 200 (2012), pp. 37--54.

[11]

F. Maggioni, E. Allevi, and M. Bertocchi, Bounds in multistage linear stochastic programming, J. Optim. Theory Appl., 163 (2014), pp. 200--229.

[12]

W. K. Mak, D. P. Morton, and R. K. Wood, Monte Carlo bounding techniques for determining solution quality in stochastic programs, Oper. Res. Lett., 24 (1999), pp. 47--56.

[13]

D. P. Morton and R. K. Wood, Restricted-recourse bounds for stochastic linear programming, Oper. Res., 47 (1999), pp. 943--956.

[14]

G. Ch. Pflug, A. Ruszczynski, and R. Schultz, On the Glivenko Cantelli problem in stochastic programming: Linear recourse, Math. Oper. Res., 23 (1998), pp. 204--220.

[15]

G. Ch. Pflug and W. Römisch, Modeling, Measuring and Managing Risk, World Scientific, Singapore, 2007.

[16]

G. Ch. Pflug, Version-independence and nested distributions in multistage stochastic optimization, SIAM J. Optim., 20 (2010), pp. 1406--1420.

[17]

G. Ch. Pflug and A. Pichler, A distance for multi-stage stochastic optimization model, SIAM J. Optim., 22 (2012), pp. 1--23.

[18]

B. Sandikçi, N. Kong, and A. J. Schaefer, A hierarchy of bounds for stochastic mixed-integer programs, Math. Program. Ser. A, 138 (2012), pp. 253--272.

Cited By

Chen ZMa W(2024)A Bayesian approach to data-driven multi-stage stochastic optimizationJournal of Global Optimization10.1007/s10898-024-01410-390:2(401-428)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01410-3
Lauria DConsigli GMaggioni F(2022)Optimal chance-constrained pension fund management through dynamic stochastic controlOR Spectrum10.1007/s00291-022-00673-044:3(967-1007)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s00291-022-00673-0
Bakir IBoland NDandurand BErera A(2019)Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic ProgramsINFORMS Journal on Computing10.1287/ijoc.2018.088532:1(145-163)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1287/ijoc.2018.0885

Index Terms

Bounds and Approximations for Multistage Stochastic Programs
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Guaranteed Bounds for General Nondiscrete Multistage Risk-Averse Stochastic Optimization Programs

In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such “infinite” problems are practically impossible to solve as they are formulated, and finite tree approximations ...
Bounds in Multistage Linear Stochastic Programming

Multistage stochastic programs, which involve sequences of decisions over time, are usually hard to solve in realistically sized problems. Providing bounds for optimal solution may help in evaluating whether it is worth the additional computations for ...
Stochastic Dynamic Cutting Plane for Multistage Stochastic Convex Programs
Abstract
We introduce Stochastic Dynamic Cutting Plane (StoDCuP), an extension of the Stochastic Dual Dynamic Programming (SDDP) algorithm to solve multistage stochastic convex optimization problems. At each iteration, the algorithm builds lower bounding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 26, Issue 1

DOI:10.1137/sjope8.26.1

Issue’s Table of Contents

© 2016, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2016

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen ZMa W(2024)A Bayesian approach to data-driven multi-stage stochastic optimizationJournal of Global Optimization10.1007/s10898-024-01410-390:2(401-428)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01410-3
Lauria DConsigli GMaggioni F(2022)Optimal chance-constrained pension fund management through dynamic stochastic controlOR Spectrum10.1007/s00291-022-00673-044:3(967-1007)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s00291-022-00673-0
Bakir IBoland NDandurand BErera A(2019)Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic ProgramsINFORMS Journal on Computing10.1287/ijoc.2018.088532:1(145-163)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1287/ijoc.2018.0885

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents