Optimization Online


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

zhihao cen(zhihao.cen***at***polytechnique.edu)

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.

Keywords: integer programming stochastic programming dual dynamic programming cutting plane method

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 01/26/2012
Entry Accepted: 01/26/2012
Entry Last Modified: 01/26/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society