Abstract
We show that the multistage stochastic linear problem (MSLP) with an arbitrary cost distribution is equivalent to an MSLP on a finite scenario tree. We establish this exact quantization result by analyzing the polyhedral structure of MSLPs. In particular, we show that the expected cost-to-go functions are polyhedral and affine on the cells of a chamber complex, which is independent of the cost distribution. This leads to new complexity results, showing that MSLP becomes polynomial when certain parameters are fixed.
| Original language | English |
|---|---|
| Pages (from-to) | 533-562 |
| Number of pages | 30 |
| Journal | SIAM Journal on Optimization |
| Volume | 34 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Jan 2024 |
Keywords
- complexity
- multistage stochastic programming
- polyhedron
- stochastic optimization
Fingerprint
Dive into the research topics of 'EXACT QUANTIZATION OF MULTISTAGE STOCHASTIC LINEAR PROBLEMS'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver