Branch-and-Bound Strategies for Dynamic Programming
Branch-and-Bound Strategies for Dynamic Programming
复制标题
动态规划的分支定界策略
作者：
T. Morin;R. E. Marsten
本文展示了如何分支定界方法可以用来减少存储，并可能，在离散动态程序的计算要求。松弛和探测标准被用来识别和消除状态，其相应的子政策不能导致最优的政策。将一般动态规划/分枝定界方法应用于旅行商问题和非线性背包问题。我们的计算经验表明，混合的方法产生显着节省计算机存储和计算的要求。
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.