ABSTRACT
Having described the techniques used to solve the dynamic programming functional equation, I now take up a difficulty that often impedes a successful solution of this equation. This difficulty, which has proved to be the bane of many dynamic programming applications, was summed up by Bellman [1957a p. xii] in his now classic phrase: The Curse of Dimensionality . Very broadly, in the context of dynamic programming, this graphic phrase
indicates that the volume of computation required to solve the dynamic programming functional equation often increases very rapidly (exponentially?) with the size of a problem. Indeed, the amount of computation can assume such magnitude that solving the equation becomes a practical impossibility. Of course, the problem of dimensionality is not an ill that afflicts only
dynamic programming. Still, it is of particular significance for dynamic programming because it hits hardest at what one might well argue is dynamic programming’s forte, namely combinatorial optimization problems, or what I shall call here discrete optimization problems. I therefore devote this chapter to a brief analysis of the Curse of Dimen-
sionality and to an assessment of the prospects for its elimination.
