Local Search with Constraint Propagation and Conflict-Based Heuristics

In this paper, we introduce a new solving algorithm for Constraint Satisfaction Problems (CSP). It performs an overall local search together with a domain filtering technique to prune the search space. Conflicts detected during filtering are used to guide the search. First experiments with a tabu version of the algorithm have shown good results on hard instances of open shop scheduling problems. It competes well with the best highly specialized algorithms.