Automating branch-and-bound for dynamic programs

Jakob Puchinger; Peter J. Stuckey

doi:10.1145/1328408.1328421

Automating branch-and-bound for dynamic programs

Jakob Puchinger, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
Pages	81-89
Number of pages	9
DOIs	https://doi.org/10.1145/1328408.1328421
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08 - San Francisco, CA, United States of America Duration: 7 Jan 2008 → 8 Jan 2008

Publication series

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

Conference

Conference	ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08
Country/Territory	United States of America
City	San Francisco, CA
Period	7/01/08 → 8/01/08

Keywords

Automatic transformation
Branch and bound
Dynamic programming

Access to Document

10.1145/1328408.1328421

Cite this

Puchinger, J., & Stuckey, P. J. (2008). Automating branch-and-bound for dynamic programs. In PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (pp. 81-89). (Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation). https://doi.org/10.1145/1328408.1328421

@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",

}

Puchinger, J & Stuckey, PJ 2008, Automating branch-and-bound for dynamic programs. in PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pp. 81-89, ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08, San Francisco, CA, United States of America, 7/01/08. https://doi.org/10.1145/1328408.1328421

Automating branch-and-bound for dynamic programs. / Puchinger, Jakob; Stuckey, Peter J.
PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. 2008. p. 81-89 (Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Automating branch-and-bound for dynamic programs

AU - Puchinger, Jakob

AU - Stuckey, Peter J.

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

KW - Automatic transformation

KW - Branch and bound

KW - Dynamic programming

UR - http://www.scopus.com/inward/record.url?scp=77950905883&partnerID=8YFLogxK

U2 - 10.1145/1328408.1328421

DO - 10.1145/1328408.1328421

M3 - Conference Paper

AN - SCOPUS:77950905883

SN - 9781595939777

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

SP - 81

EP - 89

BT - PEPM'08 - Proceedings of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation

T2 - ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, PEPM'08

Y2 - 7 January 2008 through 8 January 2008

ER -

Automating branch-and-bound for dynamic programs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this