Skip to content

Research at St Andrews

Automatically Improving Constraint Models in Savile Row through Associative-Commutative Common Subexpression Elimination

Research output: ResearchConference contribution



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 sub-expression 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 Associative-Commutative CSE (AC-CSE). This technique exploits the properties of associativity and commutativity of binary operators, for example in sum constraints. We present a new algorithm, X-CSE, that is able to choose from a larger palette of common subexpressions than previous approaches. We demonstrate substantial gains in performance using X-CSE. For example on BIBD we observed speed increases of more than 20 times compared to a standard model and that using X-CSE outperforms a sophisticated model from the literature. For Killer Sudoku we found that X-CSE 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 X-CSE to exploit. In summary we show that X-CSE, combined with preprocessing and other reformulations, is a powerful technique for automated modelling of problems containing associative and commutative constraints.



Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
EditorsB OSullivan
Place of PublicationCham
Number of pages16
ISBN (Electronic)978-3-319-10428-7
ISBN (Print)978-3-319-10427-0
StatePublished - Sep 2014
Event20th International Conference on the Principles and Practice of Constraint Programming (CP 2014) - Lyon, France
Duration: 8 Sep 201412 Sep 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing AG
ISSN (Print)0302-9743


Conference20th International Conference on the Principles and Practice of Constraint Programming (CP 2014)

    Research areas

  • Symmetry, Breaking, System

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P. Oct 2017 In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Research - peer-reviewArticle

  2. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W. 2016 Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892)

    Research output: ResearchConference contribution

  3. Breaking conditional symmetry in automated constraint modelling with CONJURE

    Akgün, Ö., Gent, I., Jefferson, C., Miguel, I. & Nightingale, P. 2014 ECAI 2014. Schaub, T., Friedrich, G. & O'Sullivan, B. (eds.). IOS Press, Vol. 263, p. 3-8 6 p. (Frontiers in Artificial Intelligence and Applications; vol. 263)

    Research output: ResearchChapter

  4. An Automated Constraint Modelling and Solving Toolchain

    Akgun, O., Frisch, A. M., Gent, I. P., Hussain, B. S., Jefferson, C. A., Kotthoff, L., Miguel, I. J. & Nightingale, P. W. 2013 ARW 2013 - 20th Automated Reasoning Workshop.

    Research output: ResearchConference contribution

  5. Automated Symmetry Breaking and Model Selection in Conjure

    Akgun, O., Frisch, A. M., Gent, I. P., Hussain, B. S., Jefferson, C. A., Kotthoff, L., Miguel, I. J. & Nightingale, P. W. 2013 CP 2013 - Principles and Practice of Constraint Programming, 19th International Conference.

    Research output: ResearchConference contribution

ID: 160060146