Using nogoods information from restarts in domain-splitting search

The use of restart techniques associated with learning nogoods in solving Constraint Satisfaction Problems (CSPs) is starting to be considered of major importance for backtrack search algorithms. In a backtracking search algorithm, with domain-splitting branching, nogoods can be learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named domain-splitting (ds) nogoods, is still not proven to be effective in solving CSP. However, information retained within ds-nogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose to include ds-nogood information in the heuristic decision. Experimental results show that this allows some problems to be solved more efficiently.