Dual dynamic programming for stochastic programs over an infinite horizon

Abstract

We consider solving stochastic programs over an infinite horizon. By leveraging the stationarity of the problem, we develop a novel continually-exploring infinite-horizon explorative dual dynamic programming (CE-Inf-EDDP) algorithm. CE-Inf-EDDP builds upon the existing explorative dual dynamic programming, designed for the finite-horizon problem, by specializing it for the infinite-horizon, stationary case. By incorporating cut sharing, frequent cutting-plane model updates, and a new adaptive search point selection strategy, CE-Inf-EDDP provides state-of-the-art iteration complexity while offering encouraging numerical performance. In the newsvendor and hydrothermal planning problem, CE-Inf-EDDP can reduce the runtime of each iteration by up to one to two orders of magnitude compared to prior methods while maintaining similar solution quality. As a result, the final solution quality and its guarantees can be much improved over the same runtime. For example, in the hydrothermal planning problem, CE-Inf-EDDP attains about an order of magnitude improvement in the relative optimality gap compared to existing methods.

Major revision updates