Constraint Programming (CP) is a flexible approach to combinatorial
optimization that has been applied to a wide range of important problems.
In recent CP conferences (2010 and 2011) we have seen many diverse
applications: design problems (design of cryptographic S-boxes, carpet
cutting to minimize waste), scheduling (nurse rostering with real-world
complications, resource allocation for datacentres), planning (contingency
planning for air traffic control, route finding for international container
shipping, assigning service professionals to tasks).
Savile Row is a modelling assistant for CP. It provides a high-level
language for the user to specify their constraint problem, and automatically
translates that language to the input language of a constraint solver. It is a
research tool, so it is designed to be flexible. It is very
easy to add new rules and program new translation pipelines.
During the translation process, Savile Row applies some reformulations to
improve the model. One interesting class of reformulations is common subexpression elimination
(CSE). If the same (or equivalent)
expression appears in different parts of a model, CSE replaces the expression
with a single variable everywhere it appears. In this way it connects together
different expressions in the model. This often improves constraint propagation, and
even when it does not do that it can improve the efficiency of a solver by
reducing the number of constraints to propagate.
Savile Row is the successor to Tailor, developed
by Andrea Rendl as part of
her PhD. Some of the techniques used by Savile Row were
pioneered by Andrea.
The main author of Savile Row is Peter Nightingale.
Ian Miguel wrote some parts of the
Essence' parser. Patrick Spracklen wrote the first version of the SAT backend.
To report bugs, ask questions, or ask for features, contact Peter:
Savile Row takes in the Essence' modelling language. Essence' is intended to be
solver-independent and high-level. More information about Essence' is available
in the tutorial that is included with the releases of Savile Row.
There is a Savile Row mailing list, details of which can be found at:
Savile Row Users Group.
Questions can be sent to the mailing list and new releases will be announced there.
At the moment Minion is fully
supported, and Gecode is almost completely
supported. Savile Row has a SAT backend and can run MiniSat and Lingeling solvers and
parse the solution.
Savile Row can produce Minizinc
output to access a number of solvers. Also, work is in progress on supporting the
Dominion constraint solver
Why is it called Savile Row?
Savile Row is a street in London with many tailors. The name comes
from the idea of "tailoring" a constraint model in various