Exact Quantization of Multistage Stochastic Linear Problems
From MaRDI portal
(Redirected from Publication:6188513)
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.
Recommendations
- Stability of Multistage Stochastic Programs
- On reduction of the multistage problem of stochastic programming with quantile criterion to the problem of mixed integer linear programming
- On Stability of Multistage Stochastic Programs
- scientific article; zbMATH DE number 1187213
- Stability of multistage stochastic programming
Cites work
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A comment on ``Computational complexity of stochastic programming problems
- A distance for multistage stochastic optimization models
- An approximation scheme for stochastic linear programming and its application to stochastic integer programs
- Analysis of stochastic dual dynamic programming method
- Bounds for Two-Stage Stochastic Programs with Fixed Recourse
- Bounds in multistage linear stochastic programming
- Complexity of stochastic dual dynamic programming
- Computational complexity of stochastic programming problems
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- Duality and minors of secondary polyhedra
- Evaluation of scenario generation methods for stochastic programming
- Fiber polytopes
- Generalized adaptive partition-based method for two-stage stochastic linear programs: geometric oracle and analysis
- Generalized bounds for convex multistage stochastic programs.
- scientific article; zbMATH DE number 3854294 (Why is no real title available?)
- scientific article; zbMATH DE number 575960 (Why is no real title available?)
- scientific article; zbMATH DE number 665697 (Why is no real title available?)
- scientific article; zbMATH DE number 7733446 (Why is no real title available?)
- Integer points in polyhedra
- Integer Programming with a Fixed Number of Variables
- Introduction to stochastic programming.
- Lectures on stochastic programming. Modeling and theory.
- Lifting projections of convex polyhedra
- Measuring solid angles beyond dimension three
- Multi-stage stochastic optimization applied to energy planning
- Normal fans of polyhedral convex sets
- On complexity of stochastic programming problems
- On the Complexity of Familiar Functions and Numbers
- Points entiers dans les polyèdres convexes
- Polytope Volume Computation
- Projections of polytopes and the generalized Baues conjecture
- Scenario reduction algorithms in stochastic programming
- Scenario reduction in stochastic programming
- Simple formula for integration of polynomials on a simplex
- Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
- The maximum numbers of faces of a convex polytope
- The Polyhedral Geometry of Pivot Rules and Monotone Paths
- The Upper Bound Conjecture and Cohen-Macaulay Rings
- The upper bound theorem for polytopes: An easy proof of its asymptotic version
- Triangulations. Structures for algorithms and applications
- Variation of cost functions in integer programming
This page was built for publication: Exact Quantization of Multistage Stochastic Linear Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188513)
