Two simplex-based approximate stochastic dynamic programming schemes for a real hydropower management problem

We present an approximate stochastic dynamic programming methodology for a real-world hydropower management problem, in which water must be released from reservoirs to produce electricity to power aluminum smelters over a planning horizon of a year (three-day time step). In each period, decisions are constrained by limits on the releases and the level of the four reservoirs, among others. The approach is a revisit of our previous work on simplicial approximate stochastic dynamic programming, in which the so-called cost-to-go or value functions are approximated over grid points chosen as vertices of simplices. The latter are constructed by first partitioning the reservoir level space into simplices and then iteratively subdividing existing simplices until a desired approximation error or a fixed number of grid points is reached. For each simplex, the approximation error is given by the difference between an upper and a lower bound. This scheme requires storing the list of created simplices in memory. In each iteration, the list is searched to find the existing simplex with the highest approximation error. This may be time-consuming as the number of existing simplices may be very large. In the new proposal, we avoid creating a long list of simplices by combining the original simplicial scheme with Monte Carlo simulation, similar to an exploration strategy in reinforcement learning. We benchmark the new method against its ancestor and an internal software package developed and used by an industrial partner, based on operational metrics and the concept of super-efficiency in data envelopment analysis. The Monte Carlo simplex-based scheme (the new method) outperforms the former method on all metrics considered. In addition, we compare the computational efficiency of both methods for different grid sizes. The average CPU time (over 15 replications) of the Monte Carlo simplicial approach varies between 78% and 98% of that of the simplicial method. As the grid sizes increase above 3,000 points, the simplicial method becomes intractable, in contrast to the Monte Carlo version, which confirms the advantage of the latter. Lastly, to further justify the Monte Carlo simplicial method, we create an artificial system by duplicating each component of the original system. In contrast to the new proposal, under the simplicial approach, the problem is tractable only for relatively modest size grids (up to 1,500 points), for which the average CPU time under the Monte Carlo approach varies between 2% and 5% of that of its simplicial counterpart.