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 Prime 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 Prime modelling language. Essence Prime is intended to be solver-independent and high-level. More information about Essence Prime is available in the tutorial that is included with the releases of Savile Row.

Constraint Solvers

At the moment Minion is fully supported and is also used for reformulations such as domain filtering and mutex detection. Gecode and Chuffed are also fully supported. Savile Row has SAT and MaxSAT backends and can run MiniSat, Lingeling, Glucose, and Open-WBO solvers and parse the solution. Savile Row can produce MiniZinc output to access a number of other solvers via the MiniZinc toolchain.

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.