Two-stage linear decision rules for multi-stage stochastic programming
From MaRDI portal
(Redirected from Publication:2118081)
Abstract: Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the optimal value of the MSLP, and, under certain assumptions, can be formulated as an explicit linear program. Similarly, as proposed by Kuhn, Wiesemann, and Georghiou (Math. Program., 130, 177-209, 2011) a lower bound for an MSLP can be obtained by restricting decisions in the dual of the MSLP to follow an LDR. We propose a new approximation approach for MSLPs, two-stage LDRs. The idea is to require only the state variables in an MSLP to follow an LDR, which is sufficient to obtain an approximation of an MSLP that is a two-stage stochastic linear program (2SLP). We similarly propose to apply LDR only to a subset of the variables in the dual of the MSLP, which yields a 2SLP approximation of the dual that provides a lower bound on the optimal value of the MSLP. Although solving the corresponding 2SLP approximations exactly is intractable in general, we investigate how approximate solution approaches that have been developed for solving 2SLP can be applied to solve these approximation problems, and derive statistical upper and lower bounds on the optimal value of the MSLP. In addition to potentially yielding better policies and bounds, this approach requires many fewer assumptions than are required to obtain an explicit reformulation when using the standard static LDR approach. A computational study on two example problems demonstrates that using a two-stage LDR can yield significantly better primal policies and modestly better dual policies than using policies based on a static LDR.
Recommendations
- Primal and dual linear decision rules in stochastic and robust optimization
- A Linear Decision-Based Approximation Approach to Stochastic Programming
- Bound-based decision rules in multistage stochastic programming
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
Cites work
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming
- A Linear Decision-Based Approximation Approach to Stochastic Programming
- A Stochastic Approximation Method
- A comment on ``Computational complexity of stochastic programming problems
- A constraint sampling approach for multi-stage robust optimization
- A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs
- A regularized decomposition method for minimizing a sum of polyhedral functions
- Acceleration of Stochastic Approximation by Averaging
- Adjustable robust solutions of uncertain linear programs
- Aggregation bounds in stochastic linear programming
- Analysis of stochastic dual dynamic programming method
- Applications of Stochastic Programming
- Approximate Dynamic Programming
- Computational complexity of stochastic programming problems
- Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
- Cut sharing for multistage stochastic linear programs with interstage dependency
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- Design of near optimal decision rules in multistage adaptive mixed-integer optimization
- Duality for Stochastic Programming Interpreted as L. P. in $L_p $-Space
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Epi-convergent discretizations of multistage stochastic programs via integration quadratures
- Generalized decision rule approximations for stochastic programming via liftings
- Generating scenario trees for multistage decision problems
- Lectures on stochastic programming. Modeling and theory.
- MSLiP: A computer code for the multistage stochastic linear programming problem
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- Multi-stage stochastic optimization applied to energy planning
- Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
- Multistage stochastic convex programs: duality and its implications
- New variants of bundle methods
- On Rates of Convergence for Stochastic Optimization Problems Under Non–Independent and Identically Distributed Sampling
- On complexity of stochastic programming problems
- On decision rules in stochastic programming
- On the convergence of decomposition methods for multistage stochastic convex programs
- On the convergence of stochastic dual dynamic programming and related methods
- On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs
- Optimization for simulation: theory vs. practice
- Primal and dual linear decision rules in stochastic and robust optimization
- Risk exposure and Lagrange multipliers of nonanticipativity constraints in multistage stochastic problems
- Risk neutral and risk averse stochastic dual dynamic programming method
- Robust Stochastic Approximation Approach to Stochastic Programming
- Robust optimization-methodology and applications
- SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
- Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs
- Scenario tree modeling for multistage stochastic programs
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Solving two-stage stochastic programming problems with level decomposition
- Stochastic programming approach to optimization under uncertainty
- The Scenario Approach to Robust Control Design
- The Scenario Generation Algorithm for Multistage Stochastic Linear Programming
- The empirical behavior of sampling methods for stochastic programming
- Variance reduction in sample approximations of stochastic programs
Cited in
(16)- ROC++: Robust Optimization in C++
- On the impact of deep learning-based time-series forecasts on multistage stochastic programming policies
- Robust two-stage stochastic linear programs with moment constraints
- The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
- Lagrangian dual decision rules for multistage stochastic mixed-integer programming
- Deviation measures in linear two-stage stochastic programming
- Step decision rules for multistage stochastic programming: a heuristic approach
- Hybrid strategies using linear and piecewise-linear decision rules for multistage adaptive linear optimization
- Two-Stage Stochastic Programming with Linearly Bi-parameterized Quadratic Recourse
- scientific article; zbMATH DE number 1389742 (Why is no real title available?)
- Joint dynamic probabilistic constraints with projected linear decision rules
- Constant depth decision rules for multistage optimization under uncertainty
- Stochastic two-stage programming
- Bound-based decision rules in multistage stochastic programming
- Solving multistage stochastic linear programming via regularized linear decision rules: an application to hydrothermal dispatch planning
- Binary decision rules for multistage adaptive mixed-integer optimization
This page was built for publication: Two-stage linear decision rules for multi-stage stochastic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118081)
