Research On Techniques Of Solving Constraint Satisfaction Problems

Constraint Programming is a powerful paradigm for solving combinational search problems.It has been successfully applied to many domains, such as scheduling, planning, configuration,network and bioinformatics. The basic idea in Constraint Programming is that we first stateall the constraints and then use some solving algorithms to solve them. Constraints areessentially relations, a constraint satisfaction problem (CSP) states which relations areallowed by the constraints among the given variables. To solve CSPs, techniques of inferenceand search should be used. Inference aims at making the problem being considered simpler tosolve by eliminating some variables or some local consistencies. Search techniques are usedto transverse all the domains to find the solutions. During the search process, heuristics areusually used to boost the efficiency. Since search algorithms are similar, local consistenciesand heuristics are the most important factors of solving CSPs.Local consistencies are vital important to solving CSPs. They can be used in apre-processing process to delete those values which must not belong to any solutions, andused during search to verify whether the node exploited is correct. Different localconsistencies and relative algorithms have been researched long. The most popular localconsistencies are AC (Arc Consistency), SAC (Singleton Arc Consistency), PC (PathConsistency), PIC (Path Inverse Consistency) and maxRPC (max-Restricted PathConsistency). Among all the local consistencies, AC is outstanding and the search algorithmMAC using AC as inference technique has been the most efficient algorithm for solvingCSPs.Heuristics have been used in search algorithms to make decisions, such as variableselection and value selection. A lot of experimental results have shown the power ofheuristics in terms of boosting the efficiency of solving CSPs. With the development ofrelative research, dynamic variable heuristics have been most studied. Among popularheuristics such as dom, dom+deg, dom/deg and dom/wdeg, dom/wdeg is the most efficientone and is still the-state-of-the-art, for it can perform well on a variety of problems.The main contributions of this paper are on the topic of improving the efficiency of solving CSPs by innovations on local consistencies and heuristics, which are as follows.（1） A new local consistency called singleton strong bound consistency (SSBC) and itslight version, light SSBC, are proposed. SSBC has a pruning power between SACand AC. The search algorithm maintaining light SSBC can outperform MAC on aconsiderable number of problems.（2） Research has been done on boosting the efficiency of maxRPC which is a quiteimportant local consistency. Two new coarse-grained algorithms maxRPCbitandmaxRPCbit+rmare proposed. The experimental results show that our algorithmsoutperform all the other existing algorithms.（3） A reasonable scheme for combining different local consistencies (we take AC andmaxRPC as example) have been proposed, which is called PmaxRPC. PmaxRPCensures that those variables with higher possibilities of fail have higherpossibilities of being checked by stronger local consistencies. The searchalgorithm using PmaxRPC outperform both of MAC and MlmaxRPC.（4） The state-of-the-art heuristic dom/wdeg is analyzed in terms of its drawback. Anda new heuristic called dom/(wdeg/exist_ratio) is proposed. It is much moreefficient than dom/wdeg.