Approximate Dynamic Programming for High-Dimensional Resource Allocation Problems

Primary tabs

Dynamic programming has long been relegated to small problems due to the well-known "curse of dimensionality." We show that there are actually three curses of dimensionality, but that these can be overcome by using a different form of the optimality equations along with carefully chosen functional approximations. In particular, the use of separable, piecewise linear approximations of the value function is particularly well suited for discrete resource allocation problems, allowing us to solve dynamic programs where the dimensionality of the state variable is in the tens of thousands. We illustrate these methods in the context of several large-scale freight transportation applications, and discuss research issues that have arisen in these applications. One challenge has been the management of resources with complex attributes, which produces dynamic programs where the dimensionality of the state vector can measure in the millions. We show how hierarchical learning strategies can be used to produce effective approximations, helping to solve the "explore vs. exploit" dilemma that is well-known in approximate dynamic programming. As a byproduct, the value functions provide accurate gradient information, avoiding the need to perform statistically unreliable "what if" simulations to determine the effect of changes in fleet size and mix.


  • Workflow Status:
  • Created By:
    Barbara Christopher
  • Created:
  • Modified By:
    Fletcher Moore
  • Modified:


    No keywords were submitted.

Target Audience

    No target audience selected.