Two-stage linear decision rules for multi-stage stochastic programming
From MaRDI portal
Publication:2118081
DOI10.1007/S10107-018-1339-4zbMATH Open1489.90074arXiv1701.04102OpenAlexW2578607773WikidataQ129089829 ScholiaQ129089829MaRDI QIDQ2118081FDOQ2118081
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.04102
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
- MSLiP: A computer code for the multistage stochastic linear programming problem
- SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming
- Acceleration of Stochastic Approximation by Averaging
- A Stochastic Approximation Method
- Robust Stochastic Approximation Approach to Stochastic Programming
- Generating Scenario Trees for Multistage Decision Problems
- Scenario tree modeling for multistage stochastic programs
- A regularized decomposition method for minimizing a sum of polyhedral functions
- Applications of Stochastic Programming
- On the convergence of stochastic dual dynamic programming and related methods
- Multi-stage stochastic optimization applied to energy planning
- Cut sharing for multistage stochastic linear programs with interstage dependency
- Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
- New variants of bundle methods
- Risk neutral and risk averse stochastic dual dynamic programming method
- The empirical behavior of sampling methods for stochastic programming
- Optimization for simulation: theory vs. practice
- Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
- Multistage Stochastic Decomposition: A Bridge between Stochastic Programming and Approximate Dynamic Programming
- Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs
- The Scenario Approach to Robust Control Design
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- The Scenario Generation Algorithm for Multistage Stochastic Linear Programming
- Analysis of stochastic dual dynamic programming method
- Epi-convergent discretizations of multistage stochastic programs via integration quadratures
- Robust optimization-methodology and applications
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Approximate Dynamic Programming
- Stochastic programming approach to optimization under uncertainty
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- Variance reduction in sample approximations of stochastic programs
- On Rates of Convergence for Stochastic Optimization Problems Under Non–Independent and Identically Distributed Sampling
- Aggregation bounds in stochastic linear programming
- Lectures on stochastic programming. Modeling and theory.
- Adjustable robust solutions of uncertain linear programs
- Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization
- Generalized decision rule approximations for stochastic programming via liftings
- Solving two-stage stochastic programming problems with level decomposition
- A Linear Decision-Based Approximation Approach to Stochastic Programming
- On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs
- SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
- Computational complexity of stochastic programming problems
- Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
- A comment on ``Computational complexity of stochastic programming problems
- Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
- On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs
- Title not available (Why is that?)
- Primal and dual linear decision rules in stochastic and robust optimization
- A constraint sampling approach for multi-stage robust optimization
- A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs
- On decision rules in stochastic programming
- Multistage stochastic convex programs: duality and its implications
- Duality for Stochastic Programming Interpreted as L. P. in $L_p $-Space
- Risk exposure and Lagrange multipliers of nonanticipativity constraints in multistage stochastic problems
Cited In (10)
- Stochastic two-stage programming
- Title not available (Why is that?)
- On the impact of deep learning-based time-series forecasts on multistage stochastic programming policies
- Robust two-stage stochastic linear programs with moment constraints
- Two-Stage Stochastic Programming with Linearly Bi-parameterized Quadratic Recourse
- ROC++: Robust Optimization in C++
- Solving multistage stochastic linear programming via regularized linear decision rules: an application to hydrothermal dispatch planning
- The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
- Deviation measures in linear two-stage stochastic programming
- Bound-based decision rules in multistage stochastic programming
Uses Software
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)
