Skip to main content
SpringerLink
Log in

Assessing solution quality in stochastic programs

  • Published:
Mathematical Programming Submit manuscript

Abstract

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.

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

Access this article

Log in via an institution

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

References

  1. Ahmed, S., Shapiro, A.: The sample average approximation method for stochastic programs with integer recourse. Optimization Online. http://www.optimization-online.org/ (2002)

  2. Attouch, H., Wets, R.J.-B.: Approximation and convergence in nonlinear optimization. In: Mangasarian O., Meyer R., Robinson S. (eds.), Nonlinear Programming, 4, Academic Press, New York, 1981, pp. 367–394

  3. Bayraksan, G., Morton, D.P.: Testing solution quality in stochastic programming: a single replication procedure. In: Proceedings of the 16th Symposium of IASC on Computational Statistics. Physica-Verlag/Springer, Prague, Czech Republic, 2004

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

    MATH  MathSciNet  Google Scholar 

  5. Bertocchi, M., Dupačová, J., Moriggia, V.: Sensitivity of bond portfolio's behavior with respect to random movements in yield curve: a simulation study. Ann. Oper. Res. 99, 267–286 (2000)

    Article  MATH  MathSciNet  Google Scholar 

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

  7. Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. European J. Oper. Res. 34, 384–392 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  8. Casella, G., Berger, R.L.: Statistical Inference. Duxbury Press, Belmont, California, 1990

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

    MATH  MathSciNet  Google Scholar 

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

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

    MATH  Google Scholar 

  12. Higle, J.L., Sen, S.: Statistical verification of optimality conditions for stochastic programs with recourse. Ann. Oper. Res. 30, 215–240 (1991)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  MathSciNet  Google Scholar 

  14. Higle, J.L., Sen, S.: Duality and statistical tests of optimality for two stage stochastic programs. Math. Program. 75, 257–275 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  15. Higle, J.L., Sen, S.: Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming. Kluwer Academic Publishers, Dordrecht, 1996

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  18. Kenyon, A.S., Morton, D.P.: Stochastic vehicle routing with random travel times. Transport. Sci. 37, 69–82 (2003)

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  20. Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12, 479–502 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  21. Law, A.M., Kelton, W.D.: Simulation Modeling and Analysis, 3rd Edition. McGraw-Hill, Boston, 2000

  22. 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  MATH  MathSciNet  Google Scholar 

  23. Norkin, V.I., Pflug, G.Ch., Ruszczyński, A.: A branch and bound method for stochastic global optimization. Math. Program. 83, 425–450 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  24. Rubinstein, R.Y., Shapiro, A.: Discrete Event Systems: Sensitivity and Stochastic Optimization by the Score Function Method. John Wiley & Sons, Chichester, 1993

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

    Article  MATH  Google Scholar 

  26. Ruszczyński, A., Świetanowski, A.: Accelerating the regularized decomposition method for two stage stochastic linear problems. European J. Oper. Res. 101, 328–342 (1997)

    Article  MATH  Google Scholar 

  27. Santoso, T., Ahmed, S., Goetschalckx, M., Shapiro, A.: A stochastic programming approach for supply chain network design under uncertainty. European J. Oper. Res. 167, 96–115 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  28. Shapiro, A.: Asymptotic analysis of stochastic programs. Ann. Oper. Res. 30, 169–186 (1991)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  32. Wallace, S.W., Ziemba, W.T., (eds.): Applications of Stochastic Programming. MPS-SIAM Series in Optimization, Philadelphia, 2005

Download references

Author information

Authors and Affiliations

  1. Systems and Industrial Engineering, University of Arizona, P.O. Box 210020, Tucson, AZ, 85721, USA

    Güzin Bayraksan

  2. Graduate Program in Operations Research, The University of Texas at Austin, Austin, Texas, 78712, USA

    David P. Morton

Authors
  1. Güzin Bayraksan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David P. Morton
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David P. Morton.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bayraksan, G., Morton, D. Assessing solution quality in stochastic programs. Math. Program. 108, 495–514 (2006). https://doi.org/10.1007/s10107-006-0720-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-006-0720-x

Mathematics Subject Classification (1991)

Search

Navigation