Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

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

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.
Fichier principal
Vignette du fichier
RR-7868.pdf (879.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00663267 , version 1 (26-01-2012)

Identifiers

  • HAL Id : hal-00663267 , version 1

Cite

Zhihao Cen. Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach. [Research Report] RR-7868, INRIA. 2012. ⟨hal-00663267⟩
270 View
135 Download

Share

Gmail Facebook Twitter LinkedIn More