Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach

Zhihao Cen 1
1 Commands - Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, UMA - Unité de Mathématiques Appliquées, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7641
Abstract : We consider a model of medium-term commodity contracts management. Randomness takes place only in the prices on which the commodities are exchanged, whilst state variable is multi-dimensional, and decision variable is integer. In our previous article, we proposed an algorithm based on the quantization of random process and a dual dynamic programming type approach to solve the continuous relaxation problem. In this paper, we study the multi-stage stochastic mixed integer linear program (SMILP) and show the difficulty when using dual programming type algorithm. We propose an approach based on the cutting plane method combined with the algorithm in our previous article, which gives an upper and a lower bound of the optimal value and a sub-optimal integer solution. Finally, a numerical test on a real problem in energy market is provided.
Type de document :
[Research Report] RR-7868, INRIA. 2012
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger
Contributeur : Zhihao Cen <>
Soumis le : jeudi 26 janvier 2012 - 16:54:10
Dernière modification le : jeudi 10 mai 2018 - 02:05:50
Document(s) archivé(s) le : lundi 19 novembre 2012 - 14:50:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00663267, version 1


Zhihao Cen. Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach. [Research Report] RR-7868, INRIA. 2012. 〈hal-00663267〉



Consultations de la notice


Téléchargements de fichiers