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 re
striction of an equivalent, penalty-based formulation of the primal stochas
tic 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 ea
sily computed than most other bounds because random coefficients may appear
anywhere in the LP, neither independence nor boundedness of the coefficien
ts is needed, and the bound is computed by solving a single LP or nonlinear
program. Analytical examples demonstrate that the new bounds can be strong
er 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 unce
rtain demand and production rates.