A Context for Constraint Satisfaction Problem Formulation Selection

Much research effort has been applied to finding effective ways for solving constraint satisfaction problems. However, the most fundamental aspect of constraint satisfaction problem solving, problem formulation, has received much less attention. This is important because the selection of an appropriate formulation can have dramatic effects on the efficiency of any constraint satisfaction problem solving algorithm.In this paper, we address the issue of problem formulation. We identify the heuristic nature of generating a good formulation and we propose a context for this process. Our work presents the research community with a focus for the many elements which affect problem formulation and this is illustrated with the example adding redundant constraints. It also provides a significant step towards the goal of automatic selection of problem formulations.