Approximate Dynamic Programming for Large-Scale Resource Allocation Problems. Powell, W. B. & Topaloglu, H. In Johnson, M. P., Norman, B., Secomandi, N., Gray, P., & Greenberg, H. J., editors, TutORials in Operations Research: Models, Methods, and Applications for Innovative Decision Making, pages 123–147.
Approximate Dynamic Programming for Large-Scale Resource Allocation Problems [link]Paper  abstract   bibtex   
We present modeling and solution strategies for large-scale resource allocation problems 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 functions 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. Computational experiments indicate that the strategies we present yield high-quality solutions. We also present comparisons with conventional stochastic programming methods.
@incollection{powellApproximateDynamicProgramming2006,
  title = {Approximate {{Dynamic Programming}} for {{Large}}-{{Scale Resource Allocation Problems}}},
  booktitle = {{{TutORials}} in {{Operations Research}}: {{Models}}, {{Methods}}, and {{Applications}} for {{Innovative Decision Making}}},
  author = {Powell, Warren B. and Topaloglu, Huseyin},
  editor = {Johnson, Michael P. and Norman, Bryan and Secomandi, Nicola and Gray, Paul and Greenberg, Harvey J.},
  date = {2006},
  pages = {123--147},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.1922},
  abstract = {We present modeling and solution strategies for large-scale resource allocation problems 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 functions 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. Computational experiments indicate that the strategies we present yield high-quality solutions. We also present comparisons with conventional stochastic programming methods.},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-13389751,approximate-dynamic-programming,curse-of-dimensionality,mitigation,monte-carlo,monte-carlo-trajectory,scenario-analysis,statistics}
}

Downloads: 0