Skip to content

Research at St Andrews

Automatically improving constraint models in Savile Row

Research output: Contribution to journalArticle

DOI

Abstract

When solving a combinatorial problem using Constraint Programming (CP) or Satisfiability (SAT), modelling and formulation are vital and difficult tasks. Even an expert human may explore many alternatives in modelling a single problem. We make a number of contributions in the automated modelling and reformulation of constraint models. We study a range of automated reformulation techniques, finding combinations of techniques which perform particularly well together. We introduce and describe in detail a new algorithm, X-CSE, to perform Associative-Commutative Common Subexpression Elimination (AC-CSE) in constraint problems, significantly improving existing CSE techniques for associative and commutative operators such as +. We demonstrate that these reformulation techniques can be integrated in a single automated constraint modelling tool, called Savile Row, whose architecture we describe. We use Savile Row as an experimental testbed to evaluate each reformulation on a set of 50 problem classes, with 596 instances in total. Our recommended reformulations are well worthwhile even including overheads, especially on harder instances where solver time dominates. With a SAT solver we observed a geometric mean of 2.15 times speedup compared to a straightforward tailored model without recommended reformulations. Using a CP solver, we obtained a geometric mean of 5.96 times speedup for instances taking over 10 seconds to solve.
Close

Details

Original languageEnglish
Pages (from-to)35-61
Number of pages27
JournalArtificial Intelligence
Volume251
Early online date13 Jul 2017
DOIs
StatePublished - Oct 2017

    Research areas

  • Common subexpression elimination, Constraint satisfaction, Modelling, Propositional satisfiability, Reformulation

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

View graph of relations

Related by author

  1. 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: Chapter in Book/Report/Conference proceedingConference contribution

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

    Nightingale, P., Akgun, O., Gent, I. P., Jefferson, C. & Miguel, I. Sep 2014 Principles and Practice of Constraint Programming. OSullivan, B. (ed.). Cham: Springer, p. 590-605 16 p. (Lecture Notes in Computer Science; vol. 8656)

    Research output: Chapter in Book/Report/Conference proceedingConference 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: Chapter in Book/Report/Conference proceedingChapter

  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: Chapter in Book/Report/Conference proceedingConference 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: Chapter in Book/Report/Conference proceedingConference contribution

Related by journal

  1. Generating custom propagators for arbitrary constraints

    Gent, I. P., Jefferson, C., Linton, S., Miguel, I. & Nightingale, P. 1 Jun 2014 In : Artificial Intelligence. 211, 1, p. 1-33 33 p.

    Research output: Contribution to journalArticle

  2. The Extended Global Cardinality Constraint: An Empirical Survey

    Nightingale, P. Feb 2011 In : Artificial Intelligence. 175, 2, p. 586-614 29 p.

    Research output: Contribution to journalArticle

  3. Implementing logical connectives in constraint programming

    Jefferson, C. A., Moore, N. C. A., Nightingale, P. & Petrie, K. E. Nov 2010 In : Artificial Intelligence. 174, 16-17, p. 1407-1429 23 p.

    Research output: Contribution to journalArticle

  4. Filtering Algorithms for the Multiset Ordering Constraint

    Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I. J. & Walsh, T. Feb 2009 In : Artificial Intelligence. 173, 2, p. 299-328 29 p.

    Research output: Contribution to journalArticle

ID: 250522992