Savile Row




Tutorial at CP'14



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:

Modelling Language

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.

Mailing List

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.

Constraint Solvers

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 synthesizer.

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 different ways.