Constant Depth Decision Rules for multistage optimization under uncertainty
| Autor: | Arkadi Nemirovski, Anatoli Juditsky, Vincent Guigues |
|---|---|
| Přispěvatelé: | Fundação Getulio Vargas - Escola de Matemática Aplicada [Rio de Janeiro] (FGV/EMAp), Données, Apprentissage et Optimisation (DAO), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), School of Industrial and Systems Engineering [Georgia Tech] (ISyE), Georgia Institute of Technology [Atlanta], ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019), Juditsky, Anatoli, MIAI @ Grenoble Alpes - - MIAI2019 - ANR-19-P3IA-0003 - P3IA - VALID |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Convex hull
Mathematical optimization Information Systems and Management General Computer Science 0211 other engineering and technologies Control variable 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST] 0502 economics and business FOS: Mathematics Mathematics - Optimization and Control [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST] Mathematics 050210 logistics & transportation 021103 operations research 05 social sciences Robust optimization Decision rule Stochastic programming Dynamic programming Linear inequality Optimization and Control (math.OC) Modeling and Simulation Constant (mathematics) |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, 2021, 295 (1), pp.223-232. ⟨10.1016/j.ejor.2021.02.042⟩ |
| ISSN: | 0377-2217 1872-6860 |
| DOI: | 10.1016/j.ejor.2021.02.042⟩ |
| Popis: | 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 μ of the decision rule, the decision at stage t is expressed as the sum of t functions of μ 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 μ 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect