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.
Type de document :
Communication dans un congrès
PEPM '08- ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, Jan 2008, San Francisco, United States. pp.Pages 81-89 2008, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. 〈10.1145/1328408.1328421〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01301580
Contributeur : Jakob Puchinger <>
Soumis le : jeudi 21 avril 2016 - 09:28:02
Dernière modification le : lundi 25 avril 2016 - 14:19:27

Identifiants

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 2008, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. 〈10.1145/1328408.1328421〉. 〈hal-01301580〉

Partager

Métriques

Consultations de la notice

13