Interchangeability supports abstraction and reformulation for multi-dimensional constraint satisfaction
Eugene C. Freuder, Daniel D. Sabin · 1997
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.