Correlation Heuristics for Constraint Programming

Backtracking search combined with constraint solving is the main approach to solve problems in Constraint Programming (CP). The key to effective search is having a good variable search heuristic to select a variable to branch as the size of the search tree is strongly dependent on the selected variables. In CP, many general purpose variable ordering search heuristics have been proposed and implemented in many CP solvers, such as the conflict-driven heuristic dom/wdeg [1], impactbased search (IBS) heuristic [2], and activity-based search (ABS) heuristic [3]. Search heuristics by their nature are not designed to be optimal search strategies but merely good ones. Thus, our goal in this paper is a new search heuristic which can outperform existing heuristics on some instances across a range of problems. We propose a new idea which is correlation-based search (CRBS), the search heuristic employs correlations between variables.