Modelling Dynamic Programming-Based Global Constraints in Constraint Programming
Publication Type:
Refereed Conference Meeting Proceeding
Abstract:
Dynamic Programming (DP) can solve many complex problems in polynomial
or pseudo-polynomial time, and it is widely used in Constraint
Programming (CP) to implement powerful global constraints.
Implementing such constraints is a nontrivial task beyond the
capability of most CP users, who must rely on their CP solver to
provide an appropriate global constraint library. This also limits
the usefulness of generic CP languages, some or all
of whose solvers might not provide the required constraints. A
technique was recently introduced for directly modelling DP in CP,
which provides a way around this problem. However, no comparison of
the technique with other approaches was made, and it was missing a
clear formalisation. In this paper we formalise the approach and
compare it with existing techniques on MiniZinc benchmark problems,
including the flow formulation of DP in Integer Programming. We
further show how it can be improved by state reduction methods.
Conference Name:
6th World Congress on Global Optimization
Proceedings:
Optimization of Complex Systems: Theory, Models, Algorithms and Applications
Digital Object Identifer (DOI):
10.1007/978-3-030-21803-4
Publication Date:
05/07/2019
Conference Location:
France
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
No