SPECIFIC CONSTRAINT HANDLING IN CONSTRAINT SATISFACTION PROBLEMS

Abundant literatures exist on consistency techniques for solving Constraint Satisfaction Problems (CSPs). These literatures, however, focused mainly on finding efficient general techniques to achieve network consistency and to solve CSPs. So far, many techniques have been reported, e.g., node consistency, arc consistency, path consistency, k-consistency, forward checking, lookahead, partial lookahead, etc. Not enough attention has been given to individual constraints, and how constraint specific features may be exploited for more efficient consistency check. Many types of constraints exist in real problems, and each has its own features. These features may allow specific consistency techniques to be designed such that they are more efficient than the general algorithms. To analyze this issue, we divide a consistency algorithm into three parts: (1) activating constraints for check; (2) selecting the next constraint to be checked; and (3) checking the selected constraint. We will discuss how constraint specific features may influence each of these aspects and how special handling techniques may be designed to improve the efficiency. In order to allow these individual constraint handling techniques to be used, a new consistency algorithm is also proposed.