Note—An Improved Discrete Dynamic Programming Algorithm for Allocating Resources Among Interdependent Projects
在Nemhauser和Ullmann的离散动态规划方法基础上，加入分支定界策略，显著减少计算时间，并消除对非零交互项数量的限制，适用于相互依赖项目的资源分配问题。
Nemhauser and Ullmann (1969) 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, we augment their DP approach with a branch-and-bound strategy as suggested in Morin and Marsten (1976). Computational results demonstrate that this enhancement significantly reduces required computation time and effectively removes any limit on the number of nonzero interaction terms allowed. We also demonstrate that our approach compares favorably to an alternative implicit enumeration approach proposed by Hansen (1972).