Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

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

Abstract : 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.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal-enpc.archives-ouvertes.fr/hal-02929361
Contributeur : Maël Forcier <>
Soumis le : mardi 15 septembre 2020 - 14:09:34
Dernière modification le : mercredi 14 octobre 2020 - 04:07:36

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02929361, version 1

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

65

Téléchargements de fichiers

53