A Constraint Modelling Pipeline
Lead Research Organisation:
University of St Andrews
Department Name: Computer Science
Abstract
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.
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.
Planned Impact
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.
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.
Publications
![publication icon](/resources/img/placeholder-60x60.png)
![publication icon](/resources/img/placeholder-60x60.png)
![publication icon](/resources/img/placeholder-60x60.png)
Chang M
(2020)
Disjoint direct product decomposition of permutation groups
![publication icon](/resources/img/placeholder-60x60.png)
Salamon A
(2020)
Superlinear Lower Bounds Based on ETH
![publication icon](/resources/img/placeholder-60x60.png)
Zhu X
(2020)
How People Visually Represent Discrete Constraint Problems.
in IEEE transactions on visualization and computer graphics
![publication icon](/resources/img/placeholder-60x60.png)
Abbara A
(2020)
Endocrine Requirements for Oocyte Maturation Following hCG, GnRH Agonist, and Kisspeptin During IVF Treatment.
in Frontiers in endocrinology
![publication icon](/resources/img/placeholder-60x60.png)
Bofill M
(2021)
Relaxing non-interference requirements in parallel plans
in Logic Journal of the IGPL
Description | Making, and optimising, decisions effectively is fundamentally important across industry, academia, and the third sector. Consider, for example, planning an evacuation in a disaster scenario. Evacuees must be assigned to vehicles and evacuation routes planned while respecting vehicle capacities and constraints on route safety, resource consumption and time constraints. The importance and difficulty of problems of this type means that automated solution techniques are very valuable. A key problem in this regard is describing, or modelling, a problem of interest in a form suitable for input to an automated solver that searches for a solution. The model chosen to describe the problem has a substantial effect on the efficiency of this search: while a good model will aid the solver in finding a solution quickly, a poor one can lead to the solver being unable to deliver a solution in a practical amount of time. In this work, we have developed a pipeline of tools that automates this modelling process. Our constraint modelling pipeline accepts a high level specification of a problem and produces a high quality model for a variety of solver types automatically, leading to consistently high performance versus naive models. |
Exploitation Route | Our constraint modelling pipeline is a very general decision-making and optimisation platform. Therefore it can used by practitioners to solve problems in a wide variety of settings, such as planning, design, logistics, or manufacturing, across industry, academia and the third sector. Our work has also advanced the state of the art in how we can automatically model these problems effectively for input for a range of different solvers. These insights can be used by the research community to make further advances. |
Sectors | Aerospace, Defence and Marine,Agriculture, Food and Drink,Creative Economy,Digital/Communication/Information Technologies (including Software),Financial Services, and Management Consultancy,Manufacturing, including Industrial Biotechology,Retail,Transport |
URL | https://constraintmodelling.org |
Description | Our constraint modelling pipeline is disseminated and supported via the website at constraintmodelling.org. We are collaborating with a number of SMEs nationally and multinational companies to transfer our work into their business. Sectors include the video games industry, manufacturing, and a vendor of Enterprise AI solutions. Our advances in understanding patience games were featured by Major Nelson, the most popular Xbox gaming podcast, in their 700th episode. |
First Year Of Impact | 2018 |
Sector | Creative Economy,Digital/Communication/Information Technologies (including Software),Manufacturing, including Industrial Biotechology |
Impact Types | Cultural,Economic |
Title | How people visually represent discrete constraint problems (dataset) |
Description | |
Type Of Material | Database/Collection of data |
Year Produced | 2019 |
Provided To Others? | Yes |
Title | Conjure |
Description | An automated constraint modelling tool |
Type Of Technology | Software |
Year Produced | 2014 |
Open Source License? | Yes |
Impact | This tool, still under active development, makes it possible to generate constraint models automatically from their specifications, rather than relying on human experts. |
URL | http://constraintmodelling.org/conjure/ |
Title | Minion |
Description | A constraint solver |
Type Of Technology | Software |
Year Produced | 2006 |
Open Source License? | Yes |
Impact | This software is in used by researchers worldwide to solve combinatorial search problems. |
URL | http://constraintmodelling.org/minion/ |
Title | Savile Row |
Description | An automated constraint modelling tool |
Type Of Technology | Software |
Year Produced | 2014 |
Open Source License? | Yes |
Impact | This tool is used for teaching and for research in various institutions worldwide |
URL | http://savilerow.cs.st-andrews.ac.uk |
Title | stacs-cp/CP2020-SR-SMT: July 2020 |
Description | This is to go with the final version of the paper. We will probably tidy the repository a little bit and make another release soon. |
Type Of Technology | Software |
Year Produced | 2020 |
URL | https://zenodo.org/record/3953083 |
Title | stacs-cp/CP2020-SRSMT: July 2020 |
Description | Supplemental repository for "Effective Encodings of Constraint Programming Models to SMT" published in CP2020. |
Type Of Technology | Software |
Year Produced | 2020 |
URL | https://zenodo.org/record/3953600 |
Description | DemoFest 2018 |
Form Of Engagement Activity | Participation in an activity, workshop or similar |
Part Of Official Scheme? | No |
Geographic Reach | National |
Primary Audience | Industry/Business |
Results and Impact | Presentation led to several discussions with potential industrial collaborators. |
Year(s) Of Engagement Activity | 2018 |
URL | https://www.sicsa.ac.uk/knowledge-exchange/industry-collaboration/demofest/ |