Projects per year
Abstract
When solving a problem using constraint programming, constraint modelling is widely acknowledged as an important and difficult task. Even a constraint modelling expert may explore many models and spend considerable time modelling a single problem. Therefore any automated assistance in the area of constraint modelling is valuable. Common subexpression elimination (CSE) is a type of constraint reformulation that has proved to be useful on a range of problems. In this paper we demonstrate the value of an extension of CSE called AssociativeCommutative CSE (ACCSE). This technique exploits the properties of associativity and commutativity of binary operators, for example in sum constraints. We present a new algorithm, XCSE, that is able to choose from a larger palette of common subexpressions than previous approaches. We demonstrate substantial gains in performance using XCSE. For example on BIBD we observed speed increases of more than 20 times compared to a standard model and that using XCSE outperforms a sophisticated model from the literature. For Killer Sudoku we found that XCSE can render some apparently difficult instances almost trivial to solve, and we observe speed increases up to 350 times. For BIBD and Killer Sudoku the common subexpressions are not present in the initial model: an important part of our methodology is reformulations at the preprocessing stage, to create the common subexpressions for XCSE to exploit. In summary we show that XCSE, combined with preprocessing and other reformulations, is a powerful technique for automated modelling of problems containing associative and commutative constraints.
Original language  English 

Title of host publication  Principles and Practice of Constraint Programming 
Subtitle of host publication  20th International Conference, CP 2014, Lyon, France, September 812, 2014. Proceedings 
Editors  Barry O'Sullivan 
Place of Publication  Cham 
Publisher  Springer 
Pages  590605 
Number of pages  16 
ISBN (Electronic)  9783319104287 
ISBN (Print)  9783319104270 
DOIs  
Publication status  Published  8 Sept 2014 
Event  20th International Conference on the Principles and Practice of Constraint Programming (CP 2014)  Lyon, France Duration: 8 Sept 2014 → 12 Sept 2014 Conference number: 20 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer International Publishing AG 
Volume  8656 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  20th International Conference on the Principles and Practice of Constraint Programming (CP 2014) 

Abbreviated title  CP 2014 
Country/Territory  France 
City  Lyon 
Period  8/09/14 → 12/09/14 
Keywords
 Symmetry
 Breaking
 System
Fingerprint
Dive into the research topics of 'Automatically improving constraint models in Savile Row through associativecommutative common subexpression elimination'. Together they form a unique fingerprint.Projects
 2 Finished

Working Together in ICT: Working Together: Constraint Programming and Cloud Computing
1/01/13 → 30/09/16
Project: Standard

A Constraint Solver Synthesiser: A Constraint Solver Synthesiser
Miguel, I. J., Balasubramaniam, D., Gent, I. P., Kelsey, T. & Linton, S. A.
1/10/09 → 30/09/14
Project: Standard