A heuristic based on domain-splitting nogoods from restarts

Inspired by Boolean Satisfiability Problems (SAT), Constraint Satisfaction Problems (CSP) are starting to use restart techniques associated with learning nogoods widely. Recent developments show how to learn nogoods from restarts and that these nogoods are of major importance when solving a CSP. Using a backtracking search algorithm, with domain-splitting branching, nogoods are learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named ds-nogoods, is still not proven to be effective in solving CSP. Nevertheless, information retained within dsnogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose and evaluate a variable selection heuristic based on ds-nogoods. Experimental results show that this allows some problems to be solved more efficiently.