You are here

Towards a Closer Integration of Dynamic Programmingand Constraint Programming


Steven Prestwich, Roberto Rossi, Armagan Tarim, Andrea Visentin

Publication Type: 
Refereed Conference Meeting Proceeding
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.
Conference Name: 
General Conference Artificial Intelligence (GCAI) 2018
Digital Object Identifer (DOI): 
Publication Date: 
Conference Location: 
National University of Ireland, Cork (UCC)
Open access repository: