Constraint satisfaction and optimization problems are an important class of problems in artificial intelligence, where a set of decisions need to be made together, so that some requirements are satisfied and perhaps also some criteria optimised. There are many examples including vehicle routing, scheduling, and planning.
This PhD project would be to apply machine learning methods to help solve constraint problems, whether by predicting the answer (or part of it) or reducing the amount of work that a constraint solver needs to do.
One possibility is end-to-end learning, where a machine learning model is trained to predict the entire solution to a problem – for example, predicting the solution to a logic problem using a graph convolutional network [1], a type of deep learning network. Even answers that are not 100% correct can be useful, e.g. as a starting point for a systematic solver.
Another direction the project could take is learning-to-prune [2]. In this approach, a machine learning model is trained to reduce the size of the problem, making it easier to solve. For example, in a vehicle routing problem, a learning-to-prune model could delete parts of the road network that are very unlikely to be used in an optimal solution, thus speeding up the solver.
The initial focus of the project would be on demonstrating the chosen method on one problem class. Later, it may be possible to generalise to more than one class, working towards a general system for learning to solve constraint problems specified in a language (such as those written in the Essence Prime language for the tool Savile Row [3]).
Research supervision
If successful, you will conduct your research under the supervision of Dr Peter Nightingale. He is a lecturer, and member of the AI group in the Department of Computer Science.
Funding requirements
To be considered for this funding you must:
- meet the entrance requirements for a PhD in Computer Science
- qualify for UK home fees
- We will look favourably on applicants that can demonstrate knowledge in undergraduate-level machine learning, and have strong programming skills. Also, a broader background in undergraduate-level AI (particularly the areas of search and logic) would be an advantage.
Apply for this studentship
1. Apply to study
- You must apply online for a full-time PhD in Computer Science.
- You must quote the project title (Machine Learning for Solving Constrained Optimisation Problems) in your application.
- There is no need to write a full formal research proposal (2,000-3,000 words) in your application to study as this studentship is for a specific project.
2. Provide a personal statement. As part of your application please provide a personal statement of 500-1,000 words with your initial thoughts on the research topic.
Deadlines
The studentship will begin in October, 2023.
Informal enquiries
Project enquiries: Peter Nightingale [Email Address Removed]
Application enquiries: [Email Address Removed]
There are a limited number of fully funded international awards available each year, however at this particular time we can only accept applications from students who qualify for UK home fees.