Restricted-recourse bounds for stochastic linear programming
成果类型：
Article
署名作者：
Morton, DP; Wood, RK
署名单位：
University of Texas System; University of Texas Austin; United States Department of Defense; United States Navy; Naval Postgraduate School
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.6.943
发表日期：
1999
页码：
943-956
关键词：
摘要：
We consider the problem of bounding the expected value of a linear program (LP) containing random coefficients, 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.