Accessibility statement

Automatically improving constraint models with Savile Row

A collaboration with the University of St Andrews and the Universitat de Girona.

Challenging decision-making and optimisation problems are pervasive across the public and private sectors and academia. Powerful solvers exist for these problems, however the way in which a constraint problem is modelled (presented to the solver) makes a huge difference to the performance of the solver, and modelling requires extensive human expertise. The project has two main aspects: to generalise and automate modelling techniques used by expert modellers, and to automatically select and sequence these techniques to create high-performance models, starting with a naïve model or an abstract specification. The ultimate goal is to exceed the performance of models written by experts.

Part of our answer to this challenge is a tool named Savile Row that implements a reformulation approach – given a straightforward or naïve model, Savile Row can apply various reformulations to introduce or remove decision variables and rewrite the constraints, sometimes leading to orders-of-magnitude improvements in solving time. At a lower level, Savile Row implements multiple encodings of constraints for some solver types and these can be automatically selected for performance. Savile Row is part of a toolchain with Conjure (which can produce multiple diverse models from a single specification) and Minion (a constraint solver and presolver), and can produce output for several classes of solvers.

Staff