A Constraint Solver based on Abstract Domains

Abstract. In this article, we apply techniques from Abstract Interpreta-tion (a general theory of semantic abstractions) to Constraint Program-ming (which aims at solving hard combinatorial problems with a generic framework based on first-order logics). We highlight some links and dif-ferences between these fields: both compute fixpoints by iteration but employ different extrapolation and refinement strategies; moreover, con-sistencies in Constraint Programming can be mapped to non-relational abstract domains. We then use these correspondences to build an ab-stract constraint solver that leverages abstract interpretation techniques (such as relational domains) to go beyond classic solvers. We present en-couraging experimental results obtained with our prototype implemen-tation.