Machine Learning for Understanding and Predicting Stochastic Algorithm Performance in Combinatorial Optimisation

Instance space analysis (ISA) seeks to understand the relationship between problem-instance characteristics and algorithm performance. It addresses questions including: how accurately algorithm performance can be predicted for a new instance and which algorithm should be selected; which instance characteristics determine performance; and whether informative lower-dimensional representations of instance space can reveal the factors governing algorithm behaviour.

Despite increasing interest in ISA, important methodological challenges remain. In particular, existing studies predominantly model average or median algorithm performance. This overlooks the stochastic nature of many heuristics: repeated executions of the same algorithm on the same problem instance can produce different outcomes. For practical algorithm selection, understanding this variability is important, particularly when poor outcomes are costly. This project will therefore investigate methods for modelling the distribution of algorithm performance, including conditional quantiles and measures of variability, enabling algorithm-selection decisions to account explicitly for uncertainty rather than relying only on expected performance. Quantile regression, which to the best of our knowledge has not been explored within ISA, provides one promising direction.

A second challenge concerns representation learning. Dimension reduction and algorithm-performance prediction are generally treated separately within ISA. Supervised dimension reduction (SDR) instead seeks low-dimensional representations that retain information relevant to predicting algorithm performance. Existing SDR approaches typically assume a single response for each feature vector, whereas stochastic algorithms generate repeated performance observations for the same problem instance. The project will investigate SDR methodology that explicitly exploits this repeated-measures structure, with the aim of producing informative and interpretable representations of instance space.

Finally, existing ISA generally treats the available experimental data as fixed. In practice, algorithm evaluations are computationally expensive and unevenly distributed: some algorithms may have been evaluated many times on particular instances, while others have been evaluated only a few times or not at all. The project will investigate active-learning strategies for deciding which algorithm-instance combinations should be evaluated next. By directing computational effort towards evaluations expected to provide the greatest information gain, these methods will seek to reduce uncertainty and improve subsequent algorithm-performance predictions and selection decisions.

The methodology will be evaluated across optimisation problems, with transport planning and pick-and-pack optimisation providing motivating real-world application settings. Transport planning involves routing and scheduling deliveries subject to constraints such as time windows and loading facilities, while pick-and-pack optimisation involves determining efficient picking and packing strategies subject to product locations, categories and packing constraints. These applications provide complex testbeds for evaluating the generalisability, robustness and practical value of the proposed methods.

Desirable Student Background

A successful student would ideally have a strong quantitative background, with knowledge of machine learning, statistics or probabilistic modelling, and good programming skills, particularly in Python or a similar scientific computing language. Experience with data analysis, predictive modelling or experimental design would be beneficial. Familiarity with combinatorial optimisation and heuristics would be advantageous but is not essential, provided the student has a strong interest in developing expertise in these areas.

How to apply

Please apply under the University of Manchester application portal and select 'PhD in Artificial Intelligence' (OAA Application portal).

When applying, you’ll need to specify the full name of this project, the name of your supervisor, if you already having funding or if you wish to be considered for available funding through the university, details of your previous study, and names and contact details of two referees.

Your application will not be processed without all of the required documents submitted at the time of application, and we cannot accept responsibility for late or missed deadlines. Incomplete applications will not be considered.

You will be asked to upload the following supporting documents:

• Final Transcript and certificates of all awarded university level qualifications
• Interim Transcript of any university level qualifications in progress
• CV
• Supporting statement: A one or two page statement outlining your motivation to pursue postgraduate research and why you want to undertake postgraduate research at Manchester, any relevant research or work experience, the key findings of your previous research experience, and techniques and skills you’ve developed. (This is mandatory for all applicants and the application will be put on hold without it).
• Contact details for two referees (Please ensure referee email addresses are official university or workplace accounts, as we may need to verify the references.)
• English Language Certificate (if applicable)

We actively encourage applicants from diverse career paths and backgrounds and from all sections of the community, regardless of age, disability, ethnicity, gender, gender expression, sexual orientation and transgender status.

We also support applications from those returning from a career break or other roles. We are dedicated to supporting work-life balance and offer flexible working arrangements to accommodate individual needs. Our selection process is free from bias, and we are committed to ensuring fair and equal opportunities for all applicants.

We are dedicated to supporting work-life balance and offer flexible working arrangements to accommodate individual needs, including a part-time study option.

Join us and help grow the UK’s national capability in artificial intelligence, part of the UK’s modern industrial strategy. Everyone is welcome if you are passionate about uncertainty quantification, decision making with humans in the loop and decision making for machine learning systems and their applications in Science and Engineering, and looking to develop your research and innovation skills at the doctoral level to further your career in the AI sector.

Equality, diversity and inclusion is fundamental to the success of The University of Manchester, and is at the heart of all of our activities. We know that diversity strengthens our research community, leading to enhanced research creativity, productivity and quality, and societal and economic impact. (Equality, diversity and inclusion | The University of Manchester)

Funding Notes

Fully funded AI UKRI CDT 4 year program; The Project will be based in University of Manchester.

The UKRI AI CDT in Decision Making for Complex Systems is part of the TechFirst offering stipends of £30,000 for students eligible for home fee status. The start date is September 2027.

References

1. D. J. Hand. Classifier Technology and the Illusion of Progress. Statistical Science, 21(1):1-14, 2006.
2. J. P. A. Ioannidis. Why most published research findings are false. PLOS Medicine, 2(8), 08 2005.
3. K. Smith-Miles and M. A. Munoz. Instance space analysis for algorithm testing: Methodology and software tools. ACM Computing Surveys, 55(12):1-31, 2022