Solver Feedback Loops for Automated Constraint Modelling at University of York on FindAPhD.com

This project is no longer listed on FindAPhD.com and may not be available.

Click here to search FindAPhD.com for PhD studentship opportunities

Dr P Nightingale No more applications being accepted Competition Funded PhD Project (UK Students Only)

York United Kingdom Artificial Intelligence

About the Project

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 optimizing some criteria. There are many examples in industry such as vehicle routing, scheduling, and planning. The PhD would be in automated modelling and solving of combinatorial optimization and constraint satisfaction problems. The ultimate goal is for the user to be able to state the problem without considering how it will be solved, and for the modelling and solving tools to produce a solution efficiently. To do this, the tools must make choices of formulation and solving strategy automatically, and this is itself an artificial intelligence problem.

At York we have a strong track record in automated modelling, especially in reformulating an existing model to improve its efficiency. Most of our work in this area is implemented in the open-source tool Savile Row [1], which has various reformulation options and produces output for a wide range of solvers, including SAT, SMT, constraint programming (CP), and mixed-integer programming. By reformulating a model, Savile Row can in some cases improve the performance of a solver by hundreds or even thousands of times [1,2,3].

This project is to investigate the promising technique of solver feedback loops, where a solver is used in model reformulation (e.g. to pre-solve part of a problem [3] or derive implied constraints [2]). We already have some very promising results to build on, from basic kinds of solver feedback loop. The PhD will be concurrent with a research grant on a closely related topic. The grant will provide funding to employ a research associate (RA) to join the research group, and I would fully expect the RA to work with you on some aspects of your research.

Competent programming skills will be needed for this project, and undergraduate-level AI would be an advantage (particularly in the areas of search and logic).

Please send informal enquiries to Peter Nightingale, [Email Address Removed]

Funding Notes

This studentship is fully funded for 3.5 years by an Engineering and Physical Sciences Research Council (EPSRC) Doctoral Training Partnership studentship and covers: (i) a tax-free annual stipend at the standard Research Council rate (£15,609 pa for 2021 entry), (ii) tuition fees at the home rate, (iii) research training and consumables
Studentships are available to any student who is eligible to pay tuition fees at the home rate: https://www.york.ac.uk/study/postgraduate-research/fees/status/
Not all projects will be funded; candidates will be appointed via a competitive process.

References

[1] P. Nightingale, Ö. Akgün, I. P. Gent, C. Jefferson, I. Miguel, P. Spracklen, Automatically Improving Constraint Models in Savile Row, Artificial Intelligence, Volume 251, Pages 35-61, 2017.
[2] C. Ansótegui, M. Bofill, J. Coll, N. Dang, J. L. Esteban, I. Miguel, P. Nightingale, A. Z. Salamon, J. Suy, M. Villaret, Automatic Detection of At-Most-One and Exactly-One Relations for Improved SAT Encodings of Pseudo-Boolean Constraints, in Proceedings of the 25th International Conference on Principles and Practice of Constraint Programming, pages 20-36, 2019.
[3] Ö. Akgün, I. P. Gent, C. Jefferson, I. Miguel, P. Nightingale, and A. Z. Salamon, Automatic Discovery and Exploitation of Promising Subproblems for Tabulation, in Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP), pages 3-12, 2018.

How good is research at University of York in Computer Science and Informatics?

Research output data provided by the Research Excellence Framework (REF)

Click here to see the results for all UK universities

Where will I study?

University of York

A prestigious Russell Group university with a global reputation for inspirational and life-changing research

We’ve won a FindAMasters and FindAPhD Postgrad Award!

As a previous winner of a Postgrad Award, our university community has been recognised for their excellence in, and dedication to, postgraduate education. Studying with us means you’ll be part of a supportive environment that has been celebrated for its achievements and positive impact on our postgraduate students.

Find out more