Reformulation of Models of Constraint Satisfaction Problems

Effective constraint programming (or: modelling) is very difficult, even
for application domain experts, and hence time-consuming. Moreover, most
of these problems are NP-hard in general, and hence require an exponential
amount of solving-time in the worst case. Furthermore, for a given solver
and a given instance of a problem, it is very hard to figure out which
model is the best.  To tackle the programming-time problem, ever more
expressive and declarative constraint programming languages are being
designed such as our modelling language ESRA. To tackle the solving-time
problem, the default behavior of the solver can be modified and the models
of the constraint satisfaction problem can be reformulated.  
Reformulation can be achieved by adding implied constraints, or switching
from a pure constraint program to an integer linear program, or from a
node-based model to an edge-based model, etc.  Three different approaches
to reformulation will be introduced, as well as our initial insights on
two of these approaches.