Extracting Constraint Satisfaction Subproblems
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 548-556.
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.
@inproceedings{ijcai1995p72,
title = {Extracting Constraint Satisfaction Subproblems},
author = {Freuder, Eugene C. and Hubbe, Paul D.},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {548--556},
year = {1995},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1995/72},
}
TY - CPAPER TI - Extracting Constraint Satisfaction Subproblems AU - Freuder, Eugene C. AU - Hubbe, Paul D. T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 548 EP - 556 UR - https://ijcai.org/proceedings/1995/72 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
