Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse
From MaRDI portal
Publication:2097658
DOI10.1007/S10107-020-01609-8zbMATH Open1506.90182arXiv2002.09743OpenAlexW3007251772MaRDI QIDQ2097658FDOQ2097658
Authors: Cristian Ramirez-Pico, Eduardo Moreno 
Publication date: 14 November 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We present a method to solve two-stage stochastic problems with fixed recourse when the uncertainty space can have either discrete or continuous distributions. Given a partition of the uncertainty space, the method is addressed to solve a discrete problem with one scenario for each element of the partition (sub-regions of the uncertainty space). Fixing first stage variables, we formulate a second stage subproblem for each element, and exploiting information from the dual of these problems, we provide conditions that the partition must satisfy to obtain the optimal solution. These conditions provide guidance on how to refine the partition, converging iteratively to the optimal solution. Results from computational experiments show how the method automatically refines the partition of the uncertainty space in the regions of interest for the problem. Our algorithm is a generalization of the adaptive partition-based method presented by Song & Luedtke (2015) for discrete distributions, extending its applicability to more general cases.
Full work available at URL: https://arxiv.org/abs/2002.09743
Recommendations
- An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse
- Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
- Partition-based decomposition algorithms for two-stage stochastic integer programs with continuous recourse
- Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse
- On a conservative partition refinement (CPR) method for a class of two-stage stochastic programming problems
two-stage stochastic programmingscenario aggregationcontinuous distributionadaptive partition-based approach
Numerical mathematical programming methods (65K05) Linear programming (90C05) Stochastic programming (90C15)
Cites Work
- Coherent measures of risk
- A regularized decomposition method for minimizing a sum of polyhedral functions
- Multi-stage stochastic optimization applied to energy planning
- New variants of bundle methods
- A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition
- The empirical behavior of sampling methods for stochastic programming
- The sample average approximation method for stochastic discrete optimization
- Inexact bundle methods for two-stage stochastic programming
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Solving LP relaxations of large-scale precedence constrained problems
- Lectures on stochastic programming. Modeling and theory.
- Bounds on the Expectation of a Convex Function of a Multivariate Random Variable
- Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- Applying oracles of on-demand accuracy in two-stage stochastic programming -- a computational study
- Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
- Tight Bounds for Stochastic Convex Programs
- A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs
- Restricted risk measures and robust optimization
- Title not available (Why is that?)
- Stochastic linear programming. Models, theory, and computation.
- Partition-based decomposition algorithms for two-stage stochastic integer programs with continuous recourse
- Improving the integer L-shaped method
- The normal law under linear restrictions: simulation and estimation via minimax tilting
- Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
- An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse
- A study of the Bienstock-Zuckerberg algorithm: applications in mining and resource constrained project scheduling
- Accelerating the Benders decomposition method: application to stochastic network design problems
Cited In (7)
- Special issue: Global solution of integer, stochastic and nonconvex optimization problems
- An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse
- Towards global solutions for nonconvex two-stage stochastic programs: a polynomial lower approximation approach
- Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse
- Title not available (Why is that?)
- Generalized adaptive partition-based method for two-stage stochastic linear programs: geometric oracle and analysis
- On a conservative partition refinement (CPR) method for a class of two-stage stochastic programming problems
Uses Software
This page was built for publication: Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097658)
