A Recursive Split, Solve, and Join Strategy for Solving Constraint Satisfaction Problems

摘要

Constraint satisfaction is a recurrent problem found in both industrial and academic environments. The importance of this particular problem relies on the fact that many other problem domains can be represented as constraint satisfaction problems. The instances of this problem are usually difficult to solve due to their combinatorial nature, as they often require an exponential time in the number of variables. Various solving strategies have been proposed to tackle this problem in the past, being the two most important trends local search and backtracking-based methods. In this paper we propose a novel solving strategy that partitions constraint satisfaction instances into smaller ones that can be independently solved and later, uses their solutions to solve the original instance. This process is performed in a recursive fashion, including both a local search-based and a backtracking-based solver. Tests of the proposed approach on a set of benchmark instances taken from public repositories obtained encouraging results with respect to both local search and backtracking-based solvers applied in isolation.