A separable piecewise linear upper bound for stochastic linear programs
Loading...
Authors
Birge, John R.
Wallace, Stein W.
Subjects
stochastic programming, upper bounds, convex functions, integration
Advisors
Date of Issue
1987-02
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
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
Type
Technical Report
Description
Series/Report No
Department
Organization
University of Michigan
Chr. Michelsen Institute
Identifiers
NPS Report Number
NPS-55-87-001
Sponsors
Ofiice of Naval Reasearch
Funding
N00014-86-K-0628
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.