Letter to the Editor—Note on Computing Optimum Discrete Allocations

The object of this Note is to extend the discussion of the recursive (dynamic programming) solution of discrete allocation problems found in the first two chapters of Bellman and Dreyfus, Applied Dynamic Programming, Princeton University Press, 1962. These problems frequently involve a continuous state space, characterizing a total amount of resource, and optimum return and policy functions that can change over small segments of this space. In order to compute these functions recursively, it is necessary to replace the continuous space by a discrete grid and compute values of the functions on this grid. The possibility of rapid changes in these functions makes impossible the accurate interpolation of values of an optimum partial return function from those of its predecessor if the grid is chosen arbitrarily. Instead, when problem constants are positive rational numbers, there is a unique grid size that essentially scales the problem to a minimum equivalent solvable all-integer problem.