A separable piecewise linear upper bound for stochastic linear programs
By: John R. Birge, Stein W. Wallace
Contributors: Wallace, Stein W.; Naval Postgraduate School (U.S.). Dept. of Operations Research
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1987
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Subjects: LINEAR PROGRAMMING
Other titles: NPS-55-87-001.
Description: Stochastic linear programs require the evaluation of an integral in which the integrand is itself      the value of a linear program. This integration is often approximated by discrete distributions      that bound the integral from above or below. A difficulty with previous upper bounds is that      they generally require a number of function evaluations that grows exponentially in the      number of variables. We give a new upper bound that requires operations that only grow      polynomially in the number of random variables. We show that this bound is sharp if the      function is linear and give computational results to illustrate its performance. Keywords:      Stochastic programming, Upper bounds, Convex functions, Integration.
Notes: Cover title.

"NPS-55-87-001."

"February 1987."

AD A178 694.

Includes bibliographical references (p. 20-22).

aq/aq cc:9116 07/18/97