Extracting Constraint Satisfaction Subproblems

Given a subproblem, S, of a constraint satisfaction problem, we can decompose the problem into a set of disjoint subproblems one of which will be S. This decomposition permits exploitation of problem-specific metaknowledge, a priori or acquired knowledge, about S. If we know that S is unsolvable, for example, the decomposition permits us to extract and then discard S, restricting the search for a solution to the remaining subproblems. A variety of potential uses for the decomposition method are discussed. A specific method that dynamically discards failed subproblems during forward checking search is described, and its utility demonstrated experimentally.

Authors

• Eugene C. Freuder Insight Centre for Data Analytics, University College Cork, Cork, Ireland
• Paul D. Hubbe Eugene C. Freuder

Keywords

No keywords are indexed for this paper.