Approximate Dynamic Programming for Large-Scale Resource Allocation Problems

We present modeling and solution strategies for large-scale resource allocation prob- lems that take place over multiple time periods under uncertainty. In general, the strategies we present formulate the problem as a dynamic program and replace the value functions with tractable approximations. The approximations of the value func- tions are obtained by using simulated trajectories of the system and iteratively improving on (possibly naive) initial approximations; we propose several improvement algorithms for this purpose. As a result, the resource allocation problem decomposes into time-staged subproblems, where the impact of the current decisions on the future evolution of the system is assessed through value function approximations. Computa- tional experiments indicate that the strategies we present yield high-quality solutions. We also present comparisons with conventional stochastic programming methods.