Abstract
Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Artstein Z, Wets RJ-B (1994) Stability results for stochastic programs and sensors, allowing for discontinuous objective functions. SIAM Journal on Optimization 4:537–550
Artstein Z, Wets RJ-B (1995) Consistency of minimizers and the SLLN for stochastic programs. Journal of Convex Analysis 2:1–17
Bank B, Guddat J, Klatte D, Kummer B, Tammer K (1982) Nonlinear parametric optimization. Akademie-Verlag, Berlin
Birge JR, Dempster MAH (1996) Stochastic programming approaches to stochastic scheduling. Journal of Global Optimization 9:417–451
Blair CE, Jeroslow RG (1977) The value function of a mixed integer program: I. Discrete Mathematics 19:121–138
Blair CE, Jeroslow RG (1984) Constructive characterization of the value function of a mixedinteger program I. Discrete Applied Mathematics 9:217–233
Carøe CC, Tind J (1995) L-shaped decomposition of two-stage stochastic programs with integer recourse. Technical Report, Institute of Mathematics, University of Copenhagen, Mathematical Programming, to appear
Kall P, Wallace SW (1994) Stochastic programming. J. Wiley & Sons, Chichester
Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research letters 13:133–142
Louveaux FV, van der Vlerk MH (1993) Stochastic programs with simple integer recourse. Mathematical Programming 61:301–326
Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York
Pflug GCh, Ruszczynski A, Schultz R (1996) On the Glivenko-Cantelli problem in stochastic programming: Linear recourse and extensions. Working Paper WP-96-020, International Institute for Applied Systems Analysis, Laxenburg, Mathematics of Operations Research, to appear
Pollard D (1984) Convergence of stochastic processes. Springer-Verlag, New York
Prékopa A (1995) Stochastic programming. Kmwer Academic Publishers, Dordrecht
Schultz R (1995) On structure and stability in stochastic programs with random technology matrix and complete integer recourse. Mathematical Programming 70:73–89
Schultz R (1996) Rates of convergence in stochastic programs with complete integer recourse. SIAM Journal on Optimization 6:1138–1152
Schultz R, Stougie L, van der Vlerk MH (1995) Solving stochastic programs with integer recourse by enumeration: a framework using Gröbner basis reductions. Mathematical Programming, to appear
Shorack GR, Wellner JA (1986) Empirical processes with applications to statistics. Wiley, New York
Talagrand M (1987) The Glivenko-Cantelli problem. The Annals of Probability 15:837–870
Vapnik VN, Červonenkis AY (1981) Necessary and sufficient conditions for the uniform convergence of means to their expectations. Theory of Probability and Applications 26:532–553
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pflug, G.C., Ruszczyński, A. & Schultz, R. On the Glivenko-Cantelli problem in stochastic programming: Mixed-integer linear recourse. Mathematical Methods of Operations Research 47, 39–49 (1998). https://doi.org/10.1007/BF01193835
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01193835