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
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.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-00663267
Contributor : Zhihao Cen <>
Submitted on : Thursday, January 26, 2012 - 4:54:10 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:29 PM
Long-term archiving on : Monday, November 19, 2012 - 2:50:29 PM

File

RR-7868.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

454

Files downloads

188