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.

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.

Publications

10 25 50
 
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 GitHub at https://github.com/conjure-cp. 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 Conjure: The Automated Constraint Modelling Tool 
Description It has been a while since we made a release. There was a pandemic since the last one, that might have something to do with it. We do not support Windows natively. Please us WSL and download the linux binaries. There are two sets of binaries for every operating system. Most users will need the *-with-solvers.zip file, which contains Savile Row and a bunch of supported solver backends in addition to Conjure. Just unzip and place all the files in a directory that's in your $PATH. Files that doesn't have with-solvers in their name only include the Conjure binary. All the commits between the two releases can be see here, not sure how useful it will be since the diff is huge. Here are the release notes auto-generated by GitHub. It mainly includes the PRs. What's Changed Adding code coverage to Azure by @ozgurakgun in https://github.com/conjure-cp/conjure/pull/468 Adding coin-or and CPLEX by @ozgurakgun in https://github.com/conjure-cp/conjure/pull/472 change expected output of test by @fraser-dunlop in https://github.com/conjure-cp/conjure/pull/476 Fix lex issue in #456 by @fraser-dunlop in https://github.com/conjure-cp/conjure/pull/477 paramgen: change middle/delta to min/max by @ndangtt in https://github.com/conjure-cp/conjure/pull/483 Remove comment files from JSON output, so the file is a valid stream of JSON objects by @ChrisJefferson in https://github.com/conjure-cp/conjure/pull/492 Print message to stderr, to make it easier to skip by @ChrisJefferson in https://github.com/conjure-cp/conjure/pull/493 Proofreading, minor changes by @felixvuo in https://github.com/conjure-cp/conjure/pull/497 Proofreading, minor tweaks by @felixvuo in https://github.com/conjure-cp/conjure/pull/498 Docsday by @ozgurakgun in https://github.com/conjure-cp/conjure/pull/496 New solver build method by @ChrisJefferson in https://github.com/conjure-cp/conjure/pull/499 Automatically Publish Docker Image to GHCR.io by @ZachNewbery in https://github.com/conjure-cp/conjure/pull/508 Update docker-publish.yml to include some basic caching by @ZachNewbery in https://github.com/conjure-cp/conjure/pull/518 correct underlines for stricter RST syntax checking in recent sphinx-doc by @ott2 in https://github.com/conjure-cp/conjure/pull/524 mention indexing syntax for sequences and tuples by @ott2 in https://github.com/conjure-cp/conjure/pull/525 update Z3 version, remove implicit dependency on Python 2 for build by @ott2 in https://github.com/conjure-cp/conjure/pull/526 replace which by command as per POSIX by @ott2 in https://github.com/conjure-cp/conjure/pull/531 tidy up docs build: reduce warnings by @ott2 in https://github.com/conjure-cp/conjure/pull/527 upgrade to Sphinx-5.x and document requirements by @ott2 in https://github.com/conjure-cp/conjure/pull/530 add simple permutations tutorial, lightly edited by @ott2 in https://github.com/conjure-cp/conjure/pull/529 Escape more characters in JSON output. Fixes #517 by @stylpe in https://github.com/conjure-cp/conjure/pull/519 Staris test files by @fionakillalea in https://github.com/conjure-cp/conjure/pull/520 New Contributors @ndangtt made their first contribution in https://github.com/conjure-cp/conjure/pull/483 @ChrisJefferson made their first contribution in https://github.com/conjure-cp/conjure/pull/492 @felixvuo made their first contribution in https://github.com/conjure-cp/conjure/pull/497 @ZachNewbery made their first contribution in https://github.com/conjure-cp/conjure/pull/508 @stylpe made their first contribution in https://github.com/conjure-cp/conjure/pull/519 @fionakillalea made their first contribution in https://github.com/conjure-cp/conjure/pull/520 Full Changelog: https://github.com/conjure-cp/conjure/compare/v2.3.0...v2.4.0 
Type Of Technology Software 
Year Produced 2022 
URL https://zenodo.org/record/7742611
 
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/