Automating branch-and-bound for dynamic programs

Jakob Puchinger, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationPEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
Pages81-89
Number of pages9
DOIs
Publication statusPublished - 1 Dec 2008
Externally publishedYes
EventACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08 - San Francisco, CA, United States of America
Duration: 7 Jan 20088 Jan 2008

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation

Conference

ConferenceACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08
Country/TerritoryUnited States of America
CitySan Francisco, CA
Period7/01/088/01/08

Keywords

  • Automatic transformation
  • Branch and bound
  • Dynamic programming

Cite this