×

Monte Carlo bounding techniques for determinig solution quality in stochastic programs. (English) Zbl 0956.90022

Summary: A Stochastic Program (SP) with solution value \(z^*\) can be approximately solved by sampling \(n\) realizations of the program’s stochastic parameters, and by solving the resulting “approximating problem” for \((x_n^*, z_n^*)\). We show that, in expectation, \(z_n^*\) is a lower bound on \(z^*\) and that this bound monotonically improves as \(n\) increases. The first result is used to construct confidence intervals on the optimality gap for any candidate solution \(\widehat{x}\) to SP, e.g., \(\widehat{x}= x_n^*\). A sampling procedure based on common random numbers ensures nonnegative gap estimates and provides significant variance reduction over naive sampling on four test problems.

MSC:

90C15 Stochastic programming

Software:

OSL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birge, J. R., The value of the stochastic solution in stochastic linear programs with fixed recourse, Math. Program., 24, 314-325 (1982) · Zbl 0502.90065
[2] Broadie, M.; Glasserman, P., Pricing American-style options using simulation, J. Econom. Dyn. Control, 21, 1323-1352 (1997) · Zbl 0901.90009
[3] Dantzig, G. B., Linear programming under uncertainty, Manag. Sci., 1, 197-206 (1955) · Zbl 0995.90589
[4] Dantzig, G. B.; Glynn, P. W., Parallel processors for planning under uncertainty, Ann. Oper. Res., 22, 1-21 (1990) · Zbl 0714.90074
[8] Dupačová, J., On non-normal asymptotic behavior of optimal solutions for stochastic programming problems and on related problems of mathematical statistics, Kybernetika, 27, 38-52 (1991) · Zbl 0733.90048
[9] Dupačová, J.; Wets, R. J.-B., Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Statist., 16, 1517-1549 (1988) · Zbl 0667.62018
[10] Ermoliev, Y., Stochastic quasigradient methods and their applications to systems optimization, Stochastics, 9, 1-36 (1983) · Zbl 0512.90079
[14] Higle, J. L.; Sen, S., Stochastic decomposition: an algorithm for two-stage linear programs with recourse, Math. Oper. Res., 16, 650-669 (1991) · Zbl 0746.90045
[15] Higle, J. L.; Sen, S., Statistical verification of optimality conditions for stochastic programs with recourse, Ann. Oper. Res., 30, 215-240 (1991) · Zbl 0762.90060
[17] Higle, J. L.; Sen, S., Duality and statistical tests of optimality for two stage stochastic programs, Math. Programm., 75, 257-275 (1996) · Zbl 0874.90146
[19] Infanger, G., Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs, Ann. Oper. Res., 39, 69-95 (1992) · Zbl 0773.90054
[21] King, A. J.; Rockafellar, R. T., Asymptotic theory for solutions in statistical estimation and stochastic programming, Math. Oper. Res., 18, 148-162 (1993) · Zbl 0798.90115
[22] King, A. J.; Wets, R. J.-B., Epi-consistency of convex stochastic programs, Stochastics, 34, 83-91 (1991) · Zbl 0733.90049
[25] Madansky, A., Inequalities for stochastic linear programming problems, Manag. Sci., 6, 197-204 (1960) · Zbl 0995.90601
[29] Ruszczyński, A., A regularized decomposition method for minimizing a sum of polyhedral functions, Math. Programm., 35, 309-333 (1986) · Zbl 0599.90103
[31] Sen, S.; Doverspike, R. D.; Cosares, S., Network planning with random demand, Telecommun. Systems, 3, 11-30 (1994)
[32] Shapiro, A., Asymptotic properties of statistical estimators in stochastic programming, Ann. Statist., 17, 841-858 (1989) · Zbl 0688.62025
[33] Shapiro, A., Asymptotic analysis of stochastic programs, Ann. Oper. Res., 30, 169-186 (1991) · Zbl 0745.90057
[34] Shapiro, A.; Homem-de-Mello, T., A simulation-based approach to two-stage stochastic programming with recourse, Math. Programm., 81, 301-325 (1998) · Zbl 0919.90120
[35] Van Slyke, R. M.; Wets, R. J.-B., L-Shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math., 17, 638-663 (1969) · Zbl 0197.45602
[36] Wets, R. J.-B., Stochastic programs with fixed recourse: the equivalent deterministic program, SIAM Rev., 16, 309-339 (1974) · Zbl 0311.90056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.