AAAI Publications, Eighth Symposium on Abstraction, Reformulation, and Approximation

Font Size: 
Cluster Graphs as Abstractions for Constraint Satisfaction Problems
Susan L. Epstein, Xingjian Li

Last modified: 2009-10-22


In a constraint satisfaction problem, the tightness of an individual constraint only describes the influence that the variables within its scope have on one another. Clusters provide a broader view; they are dense, tight subproblems within a problem. A set of clusters for a problem and the links between them provide an abstraction of it. That abstraction can be used to guide search, to curtail inference, and to provide explanations to the user. This work is a hybrid of global and local search, where local search creates an abstraction and then global search exploits it. Heuristics reference clusters to order variables and to propagate more thoughtfully with respect to them. Results are provided on a variety of challenging benchmark problems.


constraint satisfaction; graphical representation; hybrid search; visualization

Full Text: PDF