Towards a closer integration of dynamic programming and constraint programming

S Prestwich, Armagan Tarim, Andrea Visentin, Roberto Rossi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Three connections between Dynamic Programming (DP) and Constraint Programming (CP) have previously been explored in the literature: DP-based global constraints, DP like memoisation during tree search to avoid recomputing results, and subsumption of both by bucket elimination. In this paper we propose a new connection: many discrete DP algorithms can be directly modelled and solved as a constraint satisfaction problem (CSP) without backtracking. This has applications including the design of monolithic CP models for bilevel optimisation. We show that constraint filtering can occur between leader and follower variables in such models, and demonstrate the method on network interdiction.
Original languageEnglish
Title of host publicationGCAI-2018
Subtitle of host publication4th Global Conference on Artificial Intelligence
EditorsDaniel Lee, Alexander Steen, Toby Walsh
PublisherEasyChair
Pages202-214
Volume55
DOIs
Publication statusPublished - 17 Sep 2018
Event 4th Global Conference on Artificial Intelligence (GCAI 2018) - Luxembourg, Luxembourg
Duration: 17 Sep 201819 Sep 2018
https://luxlogai.uni.lu/

Publication series

NameEPiC Series in Computing
ISSN (Print)2398-7340

Conference

Conference 4th Global Conference on Artificial Intelligence (GCAI 2018)
CountryLuxembourg
CityLuxembourg
Period17/09/1819/09/18
Internet address

Fingerprint Dive into the research topics of 'Towards a closer integration of dynamic programming and constraint programming'. Together they form a unique fingerprint.

Cite this