Common Subexpression Elimination in Automated Constraint Modelling

Research output: Other contribution

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 solver-independent 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 languageEnglish
TypeWorkshop paper
Number of pages6
Publication statusPublished - 2008

Publication series

NameProceedings 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.

Cite this