16th AIAI 2020, 5 -7 June 2020, Greece

An Introduction of FD-Complete Constraints

Sven Löffler, Petra Hofstedt, Ke Liu


  The performance of solving a constraint problem can often be improved by converting a subproblem into a single constraint (for example into a regular membership constraint or a table constraint). In the past, it stood out, that specialist constraint solvers (like simplex solver or SAT solver) outperform general constraint solvers, for the problems they can handle. The disadvantage of such specialist constraint solvers is that they can handle only a small subset of problems with special limitations to the domains of the variables and/or to the allowed constraints. In this paper we introduce the concept of fd-complete constraints and fd-complete constraint satisfaction problems, which allow combining both previous approaches. More accurately, we convert general constraint problems into problems which use only one, respectively one kind of constraint. The goal is it to interpret and solve the converted constraint problems with specialist solvers, which can solve the transformed constraint problems faster than the original solver the original constraint problems.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.