logo IMB
Retour

Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

DADP : a spatial decomposition algorithm for multistage stochastic optimization problem

Vincent Leclère

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.