Constant depth decision rules for multistage optimization under uncertainty

DOI10.1016/J.EJOR.2021.02.042zbMATH Open1487.90496arXiv2005.13387OpenAlexW3132770526MaRDI QIDQ2239862FDOQ2239862

Authors: Vincent Guigues, Anatoli Juditsky, Arkadi Nemirovski 

Publication date: 5 November 2021

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: In this paper, we introduce a new class of decision rules, referred to as Constant Depth Decision Rules (CDDRs), for multistage optimization under linear constraints with uncertainty-affected right-hand sides. We consider two uncertainty classes: discrete uncertainties which can take at each stage at most a fixed number d of different values, and polytopic uncertainties which, at each stage, are elements of a convex hull of at most d points. Given the depth mu of the decision rule, the decision at stage t is expressed as the sum of t functions of mu consecutive values of the underlying uncertain parameters. These functions are arbitrary in the case of discrete uncertainties and are poly-affine in the case of polytopic uncertainties. For these uncertainty classes, we show that when the uncertain right-hand sides of the constraints of the multistage problem are of the same additive structure as the decision rules, these constraints can be reformulated as a system of linear inequality constraints where the numbers of variables and constraints is O(1)(n+m)d^mu N^2 with n the maximal dimension of control variables, m the maximal number of inequality constraints at each stage, and N the number of stages. As an illustration, we discuss an application of the proposed approach to a Multistage Stochastic Program arising in the problem of hydro-thermal production planning with interstage dependent inflows. For problems with a small number of stages, we present the results of a numerical study in which optimal CDDRs show similar performance, in terms of optimization objective, to that of Stochastic Dual Dynamic Programming (SDDP) policies, often at much smaller computational cost.

Full work available at URL: https://arxiv.org/abs/2005.13387

Recommendations

• Two-stage linear decision rules for multi-stage stochastic programming
• Robust Dual Dynamic Programming
• Design of near optimal decision rules in multistage adaptive mixed-integer optimization
• Joint dynamic probabilistic constraints with projected linear decision rules
• Bound-based decision rules in multistage stochastic programming

zbMATH Keywords

decision rulesstochastic dual dynamic programmingstochastic programming, robust optimization

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Stochastic programming (90C15)

Cites Work

• Robust optimization
• On the convergence of stochastic dual dynamic programming and related methods
• Multi-stage stochastic optimization applied to energy planning
• Approximate dynamic programming. Solving the curses of dimensionality
• Lectures on Stochastic Programming
• Introduction to Stochastic Programming
• Analysis of stochastic dual dynamic programming method
• Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints
• Adjustable robust solutions of uncertain linear programs
• Generalized decision rule approximations for stochastic programming via liftings
• SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
• Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs
• Multistage stochastic portfolio optimisation in deregulated electricity markets using linear decision rules
• On complexity of stochastic programming problems
• Robust production management
• Joint dynamic probabilistic constraints with projected linear decision rules
• On decision rules in stochastic programming
• Multistage adaptive robust optimization for the unit commitment problem
• Inexact Cuts in Stochastic Dual Dynamic Programming

Cited In (1)

• Evaluation and ranking of battery electric vehicles by Shannon's entropy and TOPSIS methods

Uses Software

• Mosek
• MSPPy

This page was built for publication: Constant depth decision rules for multistage optimization under uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2239862)