Open AccessNote—An Improved Discrete Dynamic Programming Algorithm for Allocating Resources Among Interdependent Projects
Author(s) -
Robert L. Carraway,
Robert L. Schmidt
Publication year - 1991
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.37.9.1195
Subject(s) - interdependence , computer science , computation , limit (mathematics) , mathematical optimization , dynamic programming , algorithm , mathematics , mathematical analysis , political science , law
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).capital budgeting, project selection, dynamic programming, branch and bound