Sample approximation technique for mixed-integer stochastic programming problems with several chance constraints. (English) Zbl 1245.90073

Summary: The paper deals with sample approximation applied to stochastic programming problems with chance constraints. We extend results on rates of convergence for problems with mixed-integer bounded sets of feasible solutions and several chance constraints. We derive estimates on the sample size necessary to get a feasible solution of the original problem using sample approximation. We present an application to a vehicle routing problem with time windows, random travel times, and random demand.


90C15 Stochastic programming
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] M. Branda, Nonconvex stochastic programming problems: formulations, sample approximations and stability. Ph.D. Thesis, Faculty of Mathematics and Physics, Charles University in Prague, 2010.
[2] M. Branda, Stochastic programming problems with generalized integrated chance constraints, Accepted to Optimization, doi:10.1080/02331934.2011.587007. · Zbl 1252.90056
[3] Branda, M.; Dupačová, J., Approximations and contamination bounds for probabilistic programs, Annals of operations research, 193, 3-19, (2012), See also SPEPS 2008, 13 · Zbl 1254.90133
[4] Calafiore, G.; Campi, M.C., Uncertain convex programs: randomized solutions and confidence levels, Mathematical programming, series A, 102, 25-46, (2008) · Zbl 1177.90317
[5] Charnes, A.; Cooper, W.W.; Symonds, G.H., Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil, Management science, 4, 235-263, (1958)
[6] J. Dupačová, M. Kopa, Robustness in stochastic programs with risk constraints, Accepted to Annals of Operations Research. doi:10.1007/s10479-010-0824-9.
[7] Hoeffding, W., Probability inequalities for sums of bounded random variables, Journal of the American statistical association, 58, 301, 13-30, (1963) · Zbl 0127.10602
[8] Kaňková, V., On the convergence rate of empirical estimates in chance constrained stochastic programming, Kybernetika, 26, 6, 449-461, (1990) · Zbl 0721.90057
[9] Kenyon, A.S.; Morton, D.P., Stochastic vehicle routing with random travel times, Transportation science, 37, 1, 69-82, (2003)
[10] Li, X.; Tian, P.; Leung, S.C.H., Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm, International journal of production economics, 125, 137-145, (2010)
[11] Luedtke, J.; Ahmed, S., A sample approximation approach for optimization with probabilistic constraints, SIAM journal on optimization, 19, 674-699, (2008) · Zbl 1177.90301
[12] Pagnoncelli, B.; Ahmed, S.; Shapiro, A., Computational study of a chance constrained portfolio selection problem, Optimization online, (2008)
[13] Pagnoncelli, B.; Ahmed, S.; Shapiro, A., Sample average approximation method for chance constrained programming: theory and applications, Journal optimization theory and applications, 142, 399-416, (2009) · Zbl 1175.90306
[14] Prékopa, A., Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution, Mathematical methods of operations research, 34, 441-461, (1990) · Zbl 0724.90048
[15] Prékopa, A., Stochastic programming, (1995), Kluwer Dordrecht and Académiai Kiadó, Budapest · Zbl 0834.90098
[16] Prékopa, A., Probabilistic programming, (), 267-352
[17] Shapiro, A., Monte Carlo sampling methods, (), 353-426
[18] Shen, Z.; Ordonez, F.; Dessouky, M.M., The stochastic vehicle routing problem for minimum unmet demand, optimization and logistics challenges in the enterprise, Springer optimization and its applications, 30, 349-371, (2009) · Zbl 1172.90342
[19] Wang, W.; Ahmed, S., Sample average approximation of expected value constrained stochastic programs, Operations research letters, 36, 515-519, (2008) · Zbl 1210.90131
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.