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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahmed, S., Shapiro, A.: The sample average approximation method for stochastic programs with integer recourse. Optimization Online. http://www.optimization-online.org/ (2002)
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
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
Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. Roy. Stat. Soc. 17B, 173–184 (1955)
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)
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer-Verlag, New York, 1997
Birge, J.R., Louveaux, F.V.: A multicut algorithm for two-stage stochastic linear programs. European J. Oper. Res. 34, 384–392 (1988)
Casella, G., Berger, R.L.: Statistical Inference. Duxbury Press, Belmont, California, 1990
Dantzig, G.B.: Linear programming under uncertainty. Manage. Sci. 1, 197–206 (1955)
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
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)
Higle, J.L., Sen, S.: Statistical verification of optimality conditions for stochastic programs with recourse. Ann. Oper. Res. 30, 215–240 (1991)
Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650–669 (1991)
Higle, J.L., Sen, S.: Duality and statistical tests of optimality for two stage stochastic programs. Math. Program. 75, 257–275 (1996)
Higle, J.L., Sen, S.: Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming. Kluwer Academic Publishers, Dordrecht, 1996
Higle, J.L., Sen, S.: Statistical approximations for stochastic linear programming problems. Ann. Oper. Res. 85, 173–192 (1999)
Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39, 69–95 (1992)
Kenyon, A.S., Morton, D.P.: Stochastic vehicle routing with random travel times. Transport. Sci. 37, 69–82 (2003)
King, A.J., Rockafellar, R.T.: Asymptotic theory for solutions in statistical estimation and stochastic programming. Math. Oper. Res. 18, 148–162 (1993)
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)
Law, A.M., Kelton, W.D.: Simulation Modeling and Analysis, 3rd Edition. McGraw-Hill, Boston, 2000
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)
Norkin, V.I., Pflug, G.Ch., Ruszczyński, A.: A branch and bound method for stochastic global optimization. Math. Program. 83, 425–450 (1998)
Rubinstein, R.Y., Shapiro, A.: Discrete Event Systems: Sensitivity and Stochastic Optimization by the Score Function Method. John Wiley & Sons, Chichester, 1993
Ruszczyński, A.: A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35, 309–333 (1986)
Ruszczyński, A., Świetanowski, A.: Accelerating the regularized decomposition method for two stage stochastic linear problems. European J. Oper. Res. 101, 328–342 (1997)
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)
Shapiro, A.: Asymptotic analysis of stochastic programs. Ann. Oper. Res. 30, 169–186 (1991)
Shapiro, A., Homem-de-Mello, T.: A simulation-based approach to two-stage stochastic programming with recourse. Math. Program. 81, 301–325 (1998)
Shapiro, A., Homem-de-Mello, T.: On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM J. Optim. 11, 70–86 (2001)
Shapiro, A., Homem-de-Mello, T., Kim, J.: Conditioning of convex piecewise linear stochastic programs. Math. Program. 94, 1–19 (2002)
Wallace, S.W., Ziemba, W.T., (eds.): Applications of Stochastic Programming. MPS-SIAM Series in Optimization, Philadelphia, 2005
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0720-x