Constraint modelling pipeline
Dr Özgür Akgün, Prof. Ian Gent & Prof. Ian Miguel
School of Computer Science
Combinatorial search problems are ubiquitous across the public and private sectors, and academia. Consider a staff rostering problem to assign staff to shifts while respecting required shift patterns and staffing levels, physical and staff resources, and staff working preferences. The decision-making process is often further complicated by the need also to optimise an objective, such as to maximise profit or to minimise waste. We will deliver better solutions to these problems more rapidly, increasing efficiency and reducing cost.
It is natural to characterise such problems as a set of decision variables, each representing a choice that must be made in order to solve the problem at hand (e.g. which staff member is on duty for the Friday night shift), and a set of constraints describing allowed combinations of variable assignments (e.g. a staff member cannot be assigned to a day shift immediately following a night shift). A solution is an assignment of a value to each variable satisfying all constraints.
Many decision-making and optimisation formalisms take this general form. In all of these formalisms the model of the problem is crucial to the efficiency with which it can be solved. A model in this sense is the set of decision variables and constraints chosen to represent a given problem. There are typically many possible models and formulating an effective model is notoriously difficult. Therefore, automating modelling is a key challenge.
Over the last decade, in the context of Constraint Programming, we have taken a novel approach to addressing this challenge. The user writes a problem specification in the abstract constraint specification language ‘Essence’, capturing the structure of the problem above the level of abstraction at which modelling decisions are made. Our modelling pipeline, on which our proposed research is based, automatically generates a model from this specification. This removes the need for user constraint modelling expertise, and also preserves the structure of the specified problem, allowing the system easily to explore alternative models and to exploit properties such as symmetry.
Our pipeline generates constraint models equivalent in quality to those of a competent human constraint programmer, and so represents a significant milestone towards fully automated modelling.
Centre for Interdisciplinary Research in Computational Algebra (CIRCA)