@inproceedings{792ac16ec8b8402e86c2d034d20b94ba,
title = "Automating branch-and-bound for dynamic programs",
abstract = "Dynamic programming is a powerful technique for solving optimization problems efficiently. We consider a dynamic program as simply a recursive program that is evaluated with memoization and lookup of answers. In this paper we examine how, given a function calculating a bound on the value of the dynamic program, we can optimize the compilation of the dynamic program function. We show how to automatically transform a dynamic program to a number of more efficientversions making use of the bounds function. We compare the different transformed versions on a number of example dynamic programs, and show the benefits in search space and time that can result.",
keywords = "Automatic transformation, Branch and bound, Dynamic programming",
author = "Jakob Puchinger and Stuckey, {Peter J.}",
year = "2008",
month = dec,
day = "1",
doi = "10.1145/1328408.1328421",
language = "English",
isbn = "9781595939777",
series = "Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation",
pages = "81--89",
booktitle = "PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation",
note = "ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08 ; Conference date: 07-01-2008 Through 08-01-2008",
}