The polyhedral structure and complexity of multistage stochastic linear problem with general cost distribution - École des Ponts ParisTech Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

The polyhedral structure and complexity of multistage stochastic linear problem with general cost distribution

Résumé

By studying the intrinsic polyhedral structure of multistage stochastic linear problems (MSLP), we show that a MSLP with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree. More precisely, we show that the expected cost-to-go function, at a given stage, is affine on each cell of a chamber complex i.e., on the common refinement of the complexes obtained by projecting the faces of a polyhedron. This chamber complex is independent of the cost distribution. Furthermore, we examine several important special cases of random cost distributions, exponential on a polyhedral cone, or uniform on a polytope, and obtain an explicit description of the supporting hyperplanes of the cost-to-go function, in terms of certain valuations attached to the cones of a normal fan. This leads to fixed-parameter tractability results, showing that MSLP can be solved in polynomial time when the number of stages together with certain characteristic dimensions are fixed.
Fichier principal
Vignette du fichier
main.pdf (583.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02929361 , version 1 (15-09-2020)

Identifiants

  • HAL Id : hal-02929361 , version 1

Citer

Maël Forcier, Stephane Gaubert, Vincent Leclère. The polyhedral structure and complexity of multistage stochastic linear problem with general cost distribution. 2020. ⟨hal-02929361⟩
198 Consultations
410 Téléchargements

Partager

Gmail Facebook X LinkedIn More