Using Inferred Disjunctive Constraints To Decompose Constraint Satisfaction Problems
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 254-260.
Abstract
Constraint satisfaction problems involve finding values for problem variables that satisfy constraints on what combinations of values are permitted. They have applications in many areas of artificial intelligence, from planning to natural language understanding. A new method is proposed for decomposing constraint satisfaction problems using inferred disjunctive constraints. The decomposition reduces the size of the problem. Some solutions may be lost in the process, but not all. The decomposition supports an algorithm that exhibits superior performance. Analytical and experimental evidence suggests that the algorithm can take advantage of local weak spots in globally hard problems.
@inproceedings{ijcai1993p36,
title = {Using Inferred Disjunctive Constraints To Decompose Constraint Satisfaction Problems},
author = {Freuder, Eugene C. and Hubbe, Paul D.},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {254--260},
year = {1993},
note = {Constraint Satisfaction Problems},
url = {https://ijcai.org/proceedings/1993/36},
}
TY - CPAPER TI - Using Inferred Disjunctive Constraints To Decompose Constraint Satisfaction Problems AU - Freuder, Eugene C. AU - Hubbe, Paul D. T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 254 EP - 260 UR - https://ijcai.org/proceedings/1993/36 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
