Branch-and-Bound Strategies for Dynamic Programming

This paper shows how branch-and-bound methods can be used to reduce storage and, possibly, computational requirements in discrete dynamic programs. Relaxations and fathoming criteria are used to identify and to eliminate states whose corresponding subpolicies could not lead to optimal policies. The general dynamic programming/branch-and-bound approach is applied to the traveling-salesman problem and the nonlinear knapsack problem. Our computational experience demonstrates that the hybrid approach yields dramatic savings in both computer storage and computational requirements.