Extracting Constraint Satisfaction Subproblems
Abstract
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.
Cite
Text
Freuder and Hubbe. "Extracting Constraint Satisfaction Subproblems." International Joint Conference on Artificial Intelligence, 1995.Markdown
[Freuder and Hubbe. "Extracting Constraint Satisfaction Subproblems." International Joint Conference on Artificial Intelligence, 1995.](https://mlanthology.org/ijcai/1995/freuder1995ijcai-extracting/)BibTeX
@inproceedings{freuder1995ijcai-extracting,
title = {{Extracting Constraint Satisfaction Subproblems}},
author = {Freuder, Eugene C. and Hubbe, Paul D.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1995},
pages = {548-557},
url = {https://mlanthology.org/ijcai/1995/freuder1995ijcai-extracting/}
}