Restricted-Recourse Bounds for Stochastic Linear Programming
Morton, David P.
Wood, R. Kevin
MetadataShow full item record
We consider the problem of bounding the expected value of a linear program (LP) containing random coeffecients, with applications to solving two-stage stochastic programs. An upper bound for minimizations is derived from a restriction of an equivalent, penalty-based formulation of the primal stochastic LP, and a lower bound is obtained from a restriction of a reformulation of the dual. Our "restricted recourse bounds" are more general and more easily computed than most other bounds because random coefficients may appear anywhere in the LP, neither independence nor boundedness of the coefficients is needed, and the bound is computed by solving a single LP or nonlinear program. Analytical examples demonstrate that the new bounds can be stronger than complementary Jensen bounds. (An upper bound is "complementary" to a lower bound, and vice versa). In computational work, we apply the bounds to a two-stage stochastic program for semiconductor manufacturing with uncertain demand and production rates.
Operations Research, 47, pp. 943-956.
Showing items related by title, author, creator and subject.
Royset, Johannes O.; Wets, Roger J.-B. (2017-06-09);We propose a framework for nonparametric maximum likelihood estimation of densities in situations where the sample is supplemented by information and assumptions about shape, support, continuity, slope, location of modes, ...
Rahim, Noor Hishmuddian (Monterey, California. Naval Postgraduate School, 2006-03);Since 1957, Malaysia has faced external and internal security threats. Over time, Malaysia has succeeded in solving the external threats but internal threats remained. The internal threats have come in many forms, including ...
Cavanaugh, Kevin J. (Monterey, California. Naval Postgraduate School, 1992-09);This thesis presents an exploration of the application of multigrid/multilevel techniques to a non-geometric long transportation problem. An introduction to multigrid is given, and specifics of how it is applied to this ...