MIDAS: a mixed integer dynamic approximation scheme (Q2188240)

A number of authors in the literature have looked to extend stochastic dual dynamic programming (SDDP) methods to deal with non-convex stage problems. In this paper, the authors propose a new extension of SDDP called mixed integer dynamic approximation scheme (MIDAS) for solving multistage stochastic dynamic programming problems with nondecreasing Bellman functions. MIDAS uses the same algorithmic framework as SDDP but instead of using cutting planes, MIDAS uses step functions to approximate the value function. The authors describe the MIDAS algorithm for a deterministic multistage optimization problem (MP), and prove its almost-sure convergence. They extend the model MP to include random noise on the state transition function. Also, the authors give two different extensions of the MIDAS of the deterministic setting: Full-tree MIDAS goes over every node at each iteration and sampled MIDAS computes only one pseudo trajectory at each iteration. They analyze the convergence of the two algorithms. Finaly, a simple hydro-electric scheduling example illustrating the algorithm is presented.