close
Skip to main content
Springer Nature Link
Log in

Simulation-based confidence bounds for two-stage stochastic programs

  • Full Length Paper
  • Series A
  • Published:
Save article
View saved research
Mathematical Programming Submit manuscript

Abstract

This paper provides a rigorous asymptotic analysis and justification of upper and lower confidence bounds proposed by Dantzig and Infanger (A probabilistic lower bound for two-stage stochastic programs, Stanford University, CA, 1995) for an iterative sampling-based decomposition algorithm, introduced by Dantzig and Glynn (Ann. Oper. Res. 22:1–21, 1990) and Infanger (Ann. Oper. Res. 39:41–67, 1992), for solving two-stage stochastic programs. The paper provides confidence bounds in the presence of both independent sampling across iterations, and when common samples are used across different iterations. Confidence bounds for sample-average approximation then follow as a special case. Extensions of the theory to cover use of variance reduction and the dropping of cuts are also presented. An extensive empirical investigation of the performance of these bounds establishes that the bounds perform reasonably on realistic problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Asmussen, S., Glynn, P.W.: Stochastic Simulation: Algorithms and Analysis. Springer, New York (2007)

    MATH  Google Scholar 

  2. Bayraksan, G., Morton, D.P.: Assessing solution quality in stochastic programs. Math. Program. Series B 108, 495–514 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bayraksan, G., Morton, D.P., Partani, A.: Simulation-based optimality tests for stochastic programs. In: Infanger, G. (ed.) Stochastic Programming, pp. 37–55. Springer, New York (2011)

  4. Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. R. Stat. Soc. 17b, 173–184 (1955)

    MathSciNet  Google Scholar 

  5. Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968)

    MATH  Google Scholar 

  6. Dantzig, G.B., Infanger, G.: A probabilistic lower bound for two-stage stochastic programs, Report SOL 95–6. Stanford University, CA, Department of Operations Research (1995)

  7. Dantzig, G.B., Madansky, M.: On the solution of two-staged linear programs under uncertainty. In: Proceedings 4th Berkeley Symposium on Mathematical Statistics and Probability. I, Neyman, J. (ed.), pp. 165–176 (1961)

  8. Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1, 197–206 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)

    MATH  Google Scholar 

  10. Dantzig, G.B., Glynn, P.W.: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22, 1–21 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dupačová, J., Wets, R.J.-B.: Asymptotic behavior of statistical estimation and of optimal solutions of stochastic optimization problems. Ann. Stat. 16, 1517–1549 (1988)

    Article  MATH  Google Scholar 

  12. Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, New York (1971)

    MATH  Google Scholar 

  13. Glynn, P.W., Iglehart, D.L.: Importance sampling for stochastic simulations. Manag. Sci. 35, 1367–1392 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  14. Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650–669 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  15. Higle, J.L., Sen, S.: Finite master programs in stochastic decomposition. Math. Program. 67, 143–168 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  16. Higle, J.L., Sen, S.: Stochastic Decomposition: A statistical Method for Large-Scale Stochastic Linear Programming. Kluwer, Dordrecht (1996)

    MATH  Google Scholar 

  17. Higle, J.L., Sen, S.: Statistical approximations for stochastic linear programming problems. Ann. Oper. Res. 85, 173–192 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  18. Ho, J.K.: A successive linear optimization approach to the dynamic traffic assignment problem. Transp. Sci. 14(4), 295–305 (1980)

    Article  Google Scholar 

  19. Infanger, G.: DECIS User’s Guide. Infanger Investment Technology, LLC., Mountain View, CA (1997)

  20. Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39, 41–67 (1992)

    Article  MathSciNet  Google Scholar 

  21. Infanger, G., Morton, D.: Cut sharing for multistage stochastic linear programs with interstage dependency. Math. Program. 75, 241–256 (1996)

    MathSciNet  MATH  Google Scholar 

  22. Kall, P.: Stochastic Linear Programming. Springer, Berlin (1976)

    Book  MATH  Google Scholar 

  23. Karlin, S., Taylor, H.M.: Stochastic Processes. Academic Press, New York (1975)

    MATH  Google Scholar 

  24. King, A.J., Wets, R.J.-B.: Epi-consistency of convex stochastic programs. Stoch. Stoch. Reports 34, 83–92 (1991)

    Google Scholar 

  25. King, A.J., Rockafellar, R.T.: Asymptotic theory for solutions in statistical estimation and stochastic programming. Math. Oper. Res. 18, 148–162 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  26. Kushner, H.J., Yin, G.: Stoch. Approx. Springer, New York (1997)

    Google Scholar 

  27. Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Ann. Oper. Res. 142, 215–241 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Louveaux, F.V., Smeers, Y.: Optimal investment for electricity generation: a stochastic model and a test problem. In: Ermoliev, Y., Wets, R.J.-B. (eds.) Numerical Techniques for Stochastic Optimization. Springer, Berlin (1988)

    Google Scholar 

  29. Lustig, I.L., Mulvey, J.M., Carpenter, T.J.: Formulating two-stage stochastic programs for interior point methods. Oper. Res. 39, 757–770 (1991)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  31. Mulvey, J., Ruszczyński, A.: A new scenario decomposition method for large scale stochastic optimization. Oper. Res. 43, 477–490 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  32. Resnick, S.I.: Extreme Values, Regular Variation and Point Processes. Springer, New York (1987)

    MATH  Google Scholar 

  33. Robinson, S.M.: Analysis of sample path optimization. Math. Oper. Res. 21, 513–528 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  34. Rockafellar, R.T., Wets, R.J.-B.: Scenario and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16, 119–147 (1989)

    Article  MathSciNet  Google Scholar 

  35. Ruszczyński, A.: A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35, 309–333 (1986)

    Article  MATH  Google Scholar 

  36. Ruszczyński, A., Śvetanowski, A.: Accelerating the regularized decomposition method for two-stage stochastic linear programs. Eur. J. Oper. Res. 101, 328–342 (1997)

    Article  MATH  Google Scholar 

  37. Sen, S., Doverspike, R.D., Cosares, S.: Network planning with random demand. Telecommun. Syst. 3, 11–30 (1994)

    Article  Google Scholar 

  38. Sen, S., Zhou, Z., Huang, K.: Enhancements of two-stage stochastic decomposition. Comput. Oper. Res. 36(8), 2434–2439 (2009)

    Article  MATH  Google Scholar 

  39. Shapiro, A., Homem-de-Mello, T.: A simulation-based approach to two-stage stochastic programs with recourse. Math. Program. 81, 301–325 (1998)

    MathSciNet  MATH  Google Scholar 

  40. Shapiro, A., Homem-de-Mello, T.: On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs. SIAM J. Optim. 11, 70–86 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  41. Shapiro, A., Homem-de-Mello, T., Kim, J.: Conditioning of convex piecewise linear stochastic programs. Math. Program. 94, 1–19 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  42. Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programing. Elsevier, Amsterdam (2003)

    Google Scholar 

  43. Smith, R.L.: Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32, 1296–1308 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  44. Van Slyke, R.M., Wets, R.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17, 638–663 (1969)

    Google Scholar 

  45. Wets, R.J.-B.: On the continuity of the value of a linear program and of related polyhedral-valued multifunctions. Math. Program. Study 14, 14–29 (1985)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors wish to thank the referees and Associate Editor for their very helpful and insightful comments and suggestions, which have served to greatly improve both the content and exposition of this paper.

Author information

Authors and Affiliations

  1. Stanford, CA, USA

    Peter W. Glynn & Gerd Infanger

Authors
  1. Peter W. Glynn
    View author publications

    Search author on:PubMed Google Scholar

  2. Gerd Infanger
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Gerd Infanger.

Additional information

Dedicated to the memory of George B. Dantzig.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Glynn, P.W., Infanger, G. Simulation-based confidence bounds for two-stage stochastic programs. Math. Program. 138, 15–42 (2013). https://doi.org/10.1007/s10107-012-0621-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10107-012-0621-0

Mathematics Subject Classification