Retour Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique
DADP : a spatial decomposition algorithm for multistage stochastic optimization problem
Salle 385
le 17 juin 2016 à 11:00
Multistage stochastic optimization problem are hard to solve. Indeed, the extensive formulation has a huge size. We claim that decomposition methods which allow to see this huge problem as a collection of coordinated smaller problems are an efficient way to address multistage stochastic optimization. Decomposition methods can be done in at least three ways : by scenarios (e.g. Progressive Hedging approaches), by time (e.g. dynamic programming or SDDP approaches) or spatially by disconnecting subpart of the system. The Dual Approximate Dynamic Programming (DADP) algorithm we present fall in the last category and is motivated by the study of the optimal management of an hydroelectric valley composed of N linked dams. Dualizing the couling constraint, and fixing a multiplier allow to solve the problem as N independant dams. Unfortunately in a stochastic setting this approach fails. The DADP algorithm rely on an approximation of the multiplier allowing to efficiently solve the subproblems by dynamic programming. We present theoretical results and interpretation of the DADP algorithm as well as numerical results.