Email RIS file
Bookmark
Report an Issue

Decomposition and (importance) sampling techniques for multi-stage stochastic linear programs [electronic resource].

Published
Arlington, Va. : National Science Foundation (U.S.), 1993.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description
42 pages : digital, PDF file
Additional Creators
National Science Foundation (U.S.) and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Free-to-read Unrestricted online access
Summary
The difficulty of solving large-scale multi-stage stochastic linear programs arises from the sheer number of scenarios associated with numerous stochastic parameters. The number of scenarios grows exponentially with the number of stages and problems get easily out of hand even for very moderate numbers of stochastic parameters per stage. Our method combines dual (Benders) decomposition with Monte Carlo sampling techniques. We employ importance sampling to efficiently obtain accurate estimates of both expected future costs and gradients and right-hand sides of cuts. The method enables us to solve practical large-scale problems with many stages and numerous stochastic parameters per stage. We discuss the theory of sharing and adjusting cuts between different scenarios in a stage. We derive probabilistic lower and upper bounds, where we use importance path sampling for the upper bound estimation. Initial numerical results turned out to be promising.
Report Numbers
E 1.99:sol--93-7
sol--93-7
Subject(s)
Other Subject(s)
Note
Published through SciTech Connect.
11/01/1993.
"sol--93-7"
"DE94007384"
"KC0701010"
": Contract N00014-89-J-1659 Grant ECS-8906260 Grant DMS-89130"
"89 Contract RP 8010-09 Grant CSA-4005335 Grant J0323-Phy"
Infanger, G.
Stanford Univ., CA (United States). Systems Optimization Lab.
Type of Report and Period Covered Note
Topical; 11/01/1993 - 11/01/1993
Funding Information
FG03-92ER25117
View MARC record | catkey: 14354844