Download PDFOpen PDF in browser

The Polyhedral Structure and Complexity of Multistage Stochastic Linear Problem with General Cost Distribution

EasyChair Preprint 4113

31 pagesDate: August 30, 2020

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 chambercomplex 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.

Keyphrases: Chamber Complex, Normal fan, complexity, dynamic programming, multistage stochastic programming, polyhedra, polyhedron, stochastic programming

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:4113,
  author    = {Maël Forcier and Stéphane Gaubert and Vincent Leclère},
  title     = {The Polyhedral Structure and Complexity of Multistage Stochastic Linear Problem with General Cost Distribution},
  howpublished = {EasyChair Preprint 4113},
  year      = {EasyChair, 2020}}
Download PDFOpen PDF in browser