Towards a Closer Integration of Dynamic Programmingand Constraint Programming
Publication Type:
Refereed Conference Meeting Proceeding
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.
Conference Name:
General Conference Artificial Intelligence (GCAI) 2018
Digital Object Identifer (DOI):
....
Publication Date:
20/09/2018
Conference Location:
Luxembourg
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
No