A Constraint Modelling Pipeline

In numerous contexts today we are faced with making decisions of increasing size and complexity, where many different considerations interlock in complex ways. 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.

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. Important challenges do, however, remain. The first is to generate models of the quality that human experts are capable. Given the inherent difficulty of these problems, and the importance of the model in mitigating that difficulty, raising the quality of the generated models is crucial. The second is to expand the range of output models beyond the constraint programming formalism.

The substantial challenge we address in this proposal is to overcome these two limitations to produce a powerful, general automated modelling and solving system unique in targeting a range of solving formalisms from a single abstract constraint specification. Our existing pipeline is ideal for extension to other formalisms.

The impact of this change will be substantial: combinatorial search problems are ubiquitous across the public and private sectors, and academia. We will deliver better solutions to these problems more rapidly, increasing efficiency and reducing cost.

Our proposed research is in the field of decision making and optimisation. This is an enabling technology allowing the solution of complex combinatorial problems, such as in planning, scheduling and design, found across the whole of our economy and society, impacting all of our lives. Therefore, the set of potential beneficiaries is both large and diverse, as outlined below.

Impact to Society

Efficient decision-making is of central importance to a modern society. Consider, for example, healthcare. By making effective resourcing decisions incorporating shift requirements, staff and patient preferences, and physical hospital resources, staff morale and patient satisfaction is increased (improving quality of life for both) while the public purse is saved millions of pounds. More generally, the complex combinatorial problems that our research can help to solve lie at the heart of many important questions of public policy, including: energy supply, road and rail network design and usage prediction, and housing provision.

Impact to the Economy

Decision support tools are vital to business. Complex combinatorial problems amenable to solution using our proposed research abound in industry, including: supply chain scheduling, inventory management, vehicle routing, warehouse and factory location, and pricing. Although a number of existing companies offer combinatorial optimisation technology, none offers the ease of use married with the scalability and robustness we envisage. Hence, our technology has the potential to be spun out into a startup company contributing directly to the UK economy.

Impact to People

Currently, solving a complex problem efficiently with decision making and optimisation software requires substantial expertise. Although our proposed research will reduce the level of expertise considerably, potential beneficiaries of our technology will need to acquire a core set of skills in order to harness our technology most effectively. As described in detail in our Pathways to Impact document, we will educate a wide demographic of potential users through two principal mechanisms: a suite of online demonstrator applications and two physical workshops, both of which will illustrate the use and benefits of our work.

This project will employ a Researcher Co-Investigator, Peter Nightingale. Peter is already one of the world's leading experts on automated modelling, the subject central to our proposal, and this project will allow him to develop still further, as a researcher through continued close interaction with the PI and Co-Is, and as a manager through interaction with our Scientific Officer in order to deliver our programme of impact activities. In due course, Peter will supervise and train his own students and post-docs, continuing the pipeline of skilled researchers in our field in the UK.

Impact to Knowledge

The Academic Impact section of this form describes in detail the impact that our work will make to the academic community (both in Constraints and beyond) and how it will increase our body of knowledge. Our main contribution will be to introduce techniques which can take a single abstract specification we can refine effective models, then reformulate and encode them into a wide range of powerful solving formalisms, resulting in state-of-the-art performance in solving complex combinatorial problems.