Using conflict and support counts for variable and value ordering in CSPs

摘要

A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Solving a CSP often requires searching for a solution in a large search space. Very often, much of the search efforts are wasted on the part of the search space that does not lead to a solution. Therefore, many search algorithms and heuristic techniques have been proposed to solve CSPs efficiently by guiding the search and reducing its size. Variable and value ordering techniques are among the most efficient ones as past experiments have shown that these heuristics can significantly improve the search performance and lead to the solution sooner. One such heuristic works by gathering information during search to guide subsequent decisions when selecting variables. More precisely, this heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. In this paper, we propose a variant of this heuristic where the weight of a constraint is also based on the conflict and support counts, of each variable attached to this constraint, gathered during constraint propagation. We also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic performs well in the cases of hard random and quasi-random instances. The test results also show that combining the proposed variable and value ordering heuristics can improve the performance significantly for some difficult problems.