By the same authors

From the same journal

From the same journal

Automatically improving constraint models in Savile Row

Research output: Contribution to journalArticle

Author(s)

  • Peter Nightingale
  • Özgür Akgün
  • Ian P. Gent
  • Christopher Jefferson
  • Ian James Miguel
  • Patrick Spracklen

Department/unit(s)

Publication details

JournalArtificial Intelligence
DateAccepted/In press - 5 Jul 2017
DateE-pub ahead of print - 13 Jul 2017
DatePublished (current) - Oct 2017
Volume251
Number of pages27
Pages (from-to)35-61
Early online date13/07/17
Original languageEnglish

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.

Bibliographical note

© 2017 Elsevier B.V. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.

Authors thank the EPSRC for funding this work through grants EP/H004092/1, EP/K015745/1, EP/M003728/1, and EP/P015638/1. In addition, Dr Jefferson is funded by a Royal Society University Research Fellowship.

    Research areas

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

Discover related content

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

View graph of relations