Tutorial - CP 2014

At CP 2014 in Lyon I gave a tutorial about automated reformulation, with this title and abstract:

Automated Reformulation of Constraint Models in Savile Row

Abstract. Modelling languages such as OPL, MiniZinc and Essence’ have been and continue to be the focus of considerable research effort. These languages have several advantages compared to using a constraint solver directly: they abstract away from solver-dependent details of modelling to provide the user with a consistent language for multiple constraint solvers; they typically allow arbitrary nesting of expressions when constraint solvers do not; and they provide an opportunity for automated optimisation and reformulation of the model, before it is flattened and specialised for a particular solver. This tutorial focuses on automated optimisation and reformulation at the instance level, i.e. after problem class parameters have been substituted into the model. I also focus on finite-domain integer constraint problems, although many of the techniques can also be applied to continuous variables and set variables. I will use Essence’ and Savile Row as an example language and system.

The first part of this tutorial will be an overview of published reformulations of constraint models, such as active CSE and constraint aggregation. The second part will be a description of the internals of Savile Row, with example problems demonstrating various useful reformulations that it can perform.

Finally, the third part of the tutorial will focus on examples where a sequence of reformulations leads to a surprising result. One example of this is BIBDs, where a sequence of three reformulations lead to a model that improves on the sophisticated model published by Frisch et al (which itself is far better than the model commonly used in the constraints literature).

Peter Nightingale