Optimization Online


A deterministic algorithm for solving multistage stochastic programming problems

Regan Baucke (r.baucke***at***auckland.ac.nz)
Anthony Downward (a.downward***at***auckland.ac.nz)
Golbon Zakeri (g.zakeri***at***auckland.ac.nz)

Abstract: Multistage stochastic programming problems are an important class of optimisation problems, especially in energy planning and scheduling. These problems and their solution methods have been of particular interest to researchers in stochastic programming recently. Because of the large scenario trees that these problems induce, current solution methods require random sampling of the tree in order to build a candidate policy. Candidate policies are then evaluated using Monte Carlo simulation. Under certain sampling assumptions, theoretical convergence is obtained almost surely. In practice, convergence of a given policy requires a statistical test and is only guaranteed at a given level of confidence. In this paper, we present a deterministic algorithm to solve these problems. The main feature of this algorithm is a deterministic path sampling scheme during the forward pass phase of the algorithm which is guaranteed to reduce the bound gap at all the nodes visited. Because policy simulation is no longer required, there is an improvement in performance over traditional methods for problems in which a high level of confidence is sought.

Keywords: stochastic, multistage, dynamic programming, decomposition, SDDP

Category 1: Stochastic Programming

Citation: The University of Auckland, 70 Symonds Street, Grafton, Auckland. July 2017.

Download: [PDF]

Entry Submitted: 07/23/2017
Entry Accepted: 07/23/2017
Entry Last Modified: 10/04/2017

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