Exact quantization of multistage stochastic linear problems - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Exact quantization of multistage stochastic linear problems

(1) , (2) , (1)
1
2

Abstract

We show that the multistage linear problem (MSLP) with an arbitrary cost distribution is equivalent to a 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 is fixed-parameter tractable.

Dates and versions

hal-03504876 , version 1 (30-12-2021)

Identifiers

Cite

Maël Forcier, Stéphane Gaubert, Vincent Leclère. Exact quantization of multistage stochastic linear problems. 2021. ⟨hal-03504876⟩
32 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More