PhD Project – A Prediction Model for Algorithm Selection in Solving Combinatorial Optimisation Problems
Supervisors: Ahmed Kheiri, Nicos Pavlidid
Industry Partner: Tesco
A large number of Tesco operations, such as delivery planning, vehicle routing problems and distribution systems, involve combinatorial optimisation. While these problems have been widely studied, the decision about which algorithm performs best on a particular instance, or class of instances is still unresolved.
The main objective of this project is to develop a model to predict which from a set of algorithms is most suitable for solving different instances of combinatorial optimisation problems. Problems can be characterised using different features, and we will model the relationship between such features and the performance of different heuristic algorithms. We will also explore these models for problems with dynamic features that change with time.
The project will develop new analysis methods to help explain the performance of the algorithms for different problem instances. The techniques developed will be able to explain to decision-makers under which conditions we can expect those algorithms to provide trustworthy solutions and when we may expect that the solutions provided to be infeasible or of low quality.