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

EasyChair Preprint 4113

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

@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}}