A Constraint Modelling and Solving Toolchain
Constraints are a natural, powerful means of representing and reasoning about complex problems that impact all of our lives. For example, in the production of a university timetable many constraints occur, such as: the maths lecture theatre has a capacity of 100 students; no student can attend two lectures at once. Constraint programming offers a means by which solutions to such problems can be found automatically, and proceeds in two phases. First, the problem is modelled as a set of decision variables, and a set of constraints on those variables that a solution must satisfy. A decision variable represents a choice that must be made in order to solve the problem. The domain of potential values associated with each decision variable corresponds to the options for that choice. In our timetabling example one might have two decision variables per lecture, one representing its time and the other its venue. The second phase consists of using a constraint solver to find solutions to the model: assignments of values to decision variables satisfying all constraints.
Constraint programming is a proven technology for solving complex combinatorial decision or optimisation problems of this kind in many disciplines, such as: scheduling; industrial design; aviation; banking; combinatorial mathematics; and the petrochemical and steel industries, to name but a few examples.
The St Andrews Constraints Group, with our colleagues at Cork, Dundee and York, offer a complete constraint modelling toolchain that, starting with an abstract specification of a constraint problem, performs the modelling and solving phases efficiently and automatically. The components of the toolchain are as follows:
- Conjure, which accepts a problem specified in the abstract constraint specification language Essence and automatically produces a model in the solver-independent constraint modelling language Essence’.
- Savile Row, which accepts a solver-independent constraint model in Essence’ and automatically tailors it to the input required for a particular constraint solver.
- Minion, a constraint solver, which automatically finds a solution or solutions to a given constraint model.
Recently we’ve also introduced Athanor, a local search solver that operates directly on the Essence language. The high-level nature of Essence allows for a well-performing and much more scalable local search compared to other constraint programming solvers that work on a low-level modelling language.
As a service to the constraint programming community, we also maintain CSPLib: A problem library for constraints. CSPLib is a collection of problem descriptions for constraint programming researchers and practitioners. We welcome contributions to CSPLib via the GitHub repository. Details of how to contribute can be found on the CSPLib website.