Preprint
Adaptive Two-stage Stochastic Programming with an Application to Capacity Expansion Planning
ArXiv.org
06/08/2019
DOI: 10.48550/arxiv.1906.03513
Abstract
Multi-stage stochastic programming is a well-established framework for
sequential decision making under uncertainty by seeking policies that are fully
adapted to the uncertainty. Often such flexible policies are not desirable, and
the decision maker may need to commit to a set of actions for a number of
planning periods. Two-stage stochastic programming might be better suited to
such settings, where the decisions for all periods are made here-and-now and do
not adapt to the uncertainty realized. In this paper, we propose a novel
alternative approach, where the stages are not predetermined but part of the
optimization problem. Each component of the decision policy has an associated
revision point, a period prior to which the decision is predetermined and after
which it is revised to adjust to the uncertainty realized thus far. We motivate
this setting using the multi-period newsvendor problem by deriving an optimal
adaptive policy. We label the proposed approach as adaptive two-stage
stochastic programming and provide a generic mixed-integer programming
formulation for finite stochastic processes. We show that adaptive two-stage
stochastic programming is NP-hard in general. Next, we derive bounds on the
value of adaptive two-stage programming in comparison to the two-stage and
multi-stage approaches for a specific problem structure inspired by the
capacity expansion planning problem. Since directly solving the mixed-integer
linear program associated with the adaptive two-stage approach might be very
costly for large instances, we propose several heuristic solution algorithms
based on the bound analysis. We provide approximation guarantees for these
heuristics. Finally, we present an extensive computational study on an
electricity generation capacity expansion planning problem and demonstrate the
computational and practical impacts of the proposed approach from various
perspectives.
Details
- Title: Subtitle
- Adaptive Two-stage Stochastic Programming with an Application to Capacity Expansion Planning
- Creators
- Beste BasciftciShabbir AhmedNagi Gebraeel
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.1906.03513
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 06/08/2019
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380588202771
Metrics
3 Record Views