Automatically improving constraint models in Savile Row

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

Research output: Contribution to journalArticlepeer-review

40 Citations (Scopus)
5 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)35-61
Number of pages27
JournalArtificial Intelligence
Volume251
Early online date13 Jul 2017
DOIs
Publication statusPublished - Oct 2017

Keywords

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

Fingerprint

Dive into the research topics of 'Automatically improving constraint models in Savile Row'. Together they form a unique fingerprint.

Cite this