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 :
Rapport
[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

https://hal.inria.fr/hal-00663267
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

Fichier

RR-7868.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00663267, version 1

Citation

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

Partager

Métriques

Consultations de la notice

411

Téléchargements de fichiers

169