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 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 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 Refinement-driven Transformation: Refinement-driven transformation for effective automatedconstraint modelling
Miguel, I. J. (PI) & Gent, I. P. (CoI)
27/09/06 → 26/09/09
Project: Standard