Premium
The policy graph decomposition of multistage stochastic programming problems
Author(s) -
Dowson Oscar
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21932
Subject(s) - stochastic programming , mathematical optimization , dynamic programming , computer science , dual (grammatical number) , time horizon , extension (predicate logic) , graph , decomposition , class (philosophy) , mathematics , theoretical computer science , artificial intelligence , art , ecology , literature , biology , programming language
We propose the policy graph as a structured way of formulating a general class of multistage stochastic programming problems in a way that leads to a natural decomposition. We also propose an extension to the stochastic dual dynamic programming algorithm to solve a subset of problems formulated as a policy graph. This subset includes discrete‐time, convex, infinite‐horizon, multistage stochastic programming problems with continuous state and control variables. To demonstrate the utility of our algorithm, we solve an existing multistage stochastic programming problem from the literature based on pastoral dairy farming. We show that the finite‐horizon model in the literature suffers from end‐of‐horizon effects, which we are able to overcome with an infinite‐horizon model.