Branch-and-Bound Strategies for Dynamic Programming

Thomas L. Morin and Roy E. Marsten
Additional contact information
Thomas L. Morin: Purdue University, West Lafayette, Indiana
Roy E. Marsten: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1976, vol. 24, issue 4, 611-627

Abstract: 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.

Date: 1976
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.24.4.611 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:24:y:1976:i:4:p:611-627

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().