| Author(s) | I. Shah |
| Affiliation | Department of Computer Science, College of Computer & Information Sciences King Saud University, P.O.Box 51178, Riyadh 11543, Saudi Arabia |
| Title | Preprocessing Overconstrained CSPs to Locate and Resolve Conflicts |
| Source | Journal of King Saud University. Computer & Information Sciences. Volume 16, No 1. (2004/1424) |
| Abstract | A constraint satisfaction problem (CSP) is said to be overconstrained if it does not have a solution, and its constraints are said to be conflicting. Subsets of constraints conflicting with each other are defined here as conflict sets. The process of locating conflict sets is termed conflict location. Algorithms to locate conflict sets in an overconstrained CSP are proposed. It is shown that conflict sets make explicit all the alternative ways of resolving conflict and thus define a relaxation space. An algorithm to find an optimum relaxation, one that relaxes the minimum number of constraints to resolve the conflict, is also proposed. A pre-processing technique is proposed for overconstrained CSP, whereby, relaxation obtained from the conflict sets is used to resolve conflicts in the CSP. This is shown to improve the performance of branch and bound algorithms. Keywords: constraint satisfaction; overconstrained CSPs; partial constraint satisfaction. |
