Using Conflict and Support Counts for Variable and Value Ordering in CSPs

Abstract

A Constraint Satisfaction Problem (CSP) is a very powerful framework for representing and solving constraint problems. Many real world computational problems in Artificial Intelligence and other areas of computer science can be formulated as CSPs. Problems such as scheduling and timetabling in operations research, map-coloring problem and Boolean satisfiability are some of the examples that can be represented and solved with a CSP framework. Solving a CSP is about searching for a solution in a huge search space. Very often, much 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 reducing the search space. Variable and Value Ordering is one of them. Many experiments and analyses have been conducted to show that good ordering of variables and values can significantly reduce the size of the search space and thus make the search more efficient. Many heuristics have been proposed for ordering variables or values. One such heuristics works by gathering information during search to guide subsequent decision in selecting variables. The heuristic gathers and records information about failures in the form of constraint weight during constraint propagation. Constraints will be assigned weights based on the information gathered. Each variable in the constraint graph will have a weighted degree which is the sum of the weights of the constraints the variable is involved in. In this thesis I will 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. The conflict and support counts information is gathered during constraint propagation. The weight of the constraint is the ratio of conflict to support counts. I will also propose a dynamic value ordering heuristic based on the support and conflict count information. Experiments have been conducted on the proposed heuristics using the renowned benchmarks which include random, quasi-random, pattern and real world instances. The test results show that the proposed variable ordering heuristic perform 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 in some difficult problems.