Interchangeability Supports Abstraction and Reformulation for Multi-Dimensional Constraint Satisfaction
Abstract
Interchangeability provides a principled approach to abstraction and reformulation of constraint satisfaction problems. Values are interchangeable if exchanging one for the other in any solution produces another solution. Abstracting a problem by simplifying the constraints can increase interchangeability. Multi-dimensional constraint satisfaction problems can provide natural opportunities for this abstraction process. Multi-dimensional problems may involve vectors of values, or conjunctive constraints. Utilizing the interchangeability can permit more efficient solutions of the abstracted problem. These solutions can be expanded into smaller reformulations of the original problem. Solving abstracted and then reformulated problems can be considerably more efficient than solving the original problems. We provide data that demonstrates the potential of this abstraction/reformulation process for multi-dimensional problems, and illuminates how its utility can depend on natural problem parameters.
Cite
Text
Freuder and Sabin. "Interchangeability Supports Abstraction and Reformulation for Multi-Dimensional Constraint Satisfaction." AAAI Conference on Artificial Intelligence, 1997.Markdown
[Freuder and Sabin. "Interchangeability Supports Abstraction and Reformulation for Multi-Dimensional Constraint Satisfaction." AAAI Conference on Artificial Intelligence, 1997.](https://mlanthology.org/aaai/1997/freuder1997aaai-interchangeability/)BibTeX
@inproceedings{freuder1997aaai-interchangeability,
title = {{Interchangeability Supports Abstraction and Reformulation for Multi-Dimensional Constraint Satisfaction}},
author = {Freuder, Eugene C. and Sabin, Daniel},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1997},
pages = {191-196},
url = {https://mlanthology.org/aaai/1997/freuder1997aaai-interchangeability/}
}