A new approach to partial constraint satisfaction problems

Abstract

A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems.

In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n² d²) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ⌊n(n − 2)(d − 2)/(d − 1)⌋.

E-mail: [email protected]

Keywords:

• Branch and bound
• Consistency checks
• Independent sets
• Value constraint graph
• Scheduling
• Constraint relaxation
• CSPs
• PCSPs

Notes

E-mail: [email protected]