Advertisement
Published in:
2005 | OriginalPaper | Chapter
Solution Equivalent Subquadrangle Reformulations of Constraint Satisfaction Problems
Authors : Chris Houghton, David Cohen
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Constraint Satisfaction Problem instances (CSPs) are a natural way to model real life problems such as image processing, scheduling and natural language understanding. In this paper we are concerned with the modeling of problems as CSPs and how this can affect the performance of different solution algorithms. In particular we are interested in modeling in the language of subquadrangles.
A Quadrangle is essentially an ‘anything-goes’ constraint for some Cartesian product of domains. A Subquadrangle [1] is a constraint all of whose projections to proper subsets of the scope are quadrangles.
Subquadrangles are a very ‘natural’ way in which to represent constraints. This is because they do not place any restrictions on proper subsets of their scope, thus reducing the number of required constraint checks. This leads us to believe that a subquadrangle aware solver could be particularly efficient.