Projects per year
Abstract
Typically, there are many alternative models of a given problem as a constraint satisfaction problem, and formulating an ef fective model requires a great deal of expertise. To reduce this bot tleneck, automated constraint modelling systems allow the abstract specification of a problem, which can then be refined automatically to a solverindependent modelling language. The final step is to tailor the model to a particular constraint solver. We show that we can eliminate common subexpressions in the tailoring step, as compilers do when compiling source code. We show that common subexpres sion elimination has two key benefits. First, it can lead to a dramatic reduction in the size of a constraint problem, to the extent that solving time is reduced by an order of magnitude when the number of nodes searched is the same. Second, it can lead to enhanced propagation and reduced search. The effect of this can be even more dramatic, leading to reductions in nodes searched and time taken by several or ders of magnitude. Where the technique does not lead to improved search, we have not seen it cause a significant overhead. Therefore, we propose that common subexpression elimination is an important technique for constraint programming.
Original language  English 

Type  Workshop paper 
Number of pages  6 
Publication status  Published  2008 
Publication series
Name  Proceedings of the International Workshop on Modeling and Solving Problems with Constraints 

Fingerprint
Dive into the research topics of 'Common Subexpression Elimination in Automated Constraint Modelling'. Together they form a unique fingerprint.Projects
 1 Finished

EPSRC Refinementdriven Transformation: Refinementdriven transformation for effective automatedconstraint modelling
27/09/06 → 26/09/09
Project: Standard