Skip to Main content Skip to Navigation
Conference papers

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 efficient versions 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01301580
Contributor : Jakob Puchinger <>
Submitted on : Thursday, April 21, 2016 - 9:28:02 AM
Last modification on : Thursday, December 20, 2018 - 1:36:01 PM

Identifiers

Citation

Jakob Puchinger, Peter Stuckey. Automating branch-and-bound for dynamic programs. PEPM '08- ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, Jan 2008, San Francisco, United States. pp.Pages 81-89 ⟨10.1145/1328408.1328421⟩. ⟨hal-01301580⟩

Share

Metrics

Record views

67