An improved discrete dynamic programming algorithm for allocating resources among interdependent projects

Nemhauser and Ullmann proposed a discrete dynamic programming (DP) approach for several variations of the basic capital allocation model, including one in which the returns and resource consumption of projects are interdependent. For this case, the authors augment their DP approach with a branch-and-bound strategy. Computational results demonstrate that this enhancement significantly reduces required computation time and effectively removes any limit on the number of nonzero interaction terms allowed. The authors also demonstrate that the present approach compares favorably to an alternative implicit enumeration approach proposed by Hansen.