📣 Help Shape the Future of UKRI's Gateway to Research (GtR)

We're improving UKRI's Gateway to Research and are seeking your input! If you would be interested in being interviewed about the improvements we're making and to have your say about how we can make GtR more user-friendly, impactful, and effective for the Research and Innovation community, please email gateway@ukri.org.

Keep Learning

Lead Research Organisation: University of St Andrews
Department Name: Computer Science

Abstract

Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
 
Description On automated reformulation:
A fundamental aspect of solving optimisation problems is the effective formulation of a constraint model for a family of parameterised problems. Different modelling choices can dramatically impact solver efficiency, yet it is often difficult to know which model will work best. As part of our research we developed a system that addresses this challenge by automatically reformulating an input model using graph rewriting techniques. It leverages a high-level abstract modelling language to identify and rework the structure of the model, then translates the solution of the improved formulation back into the original model's terms for verification and presentation. This approach minimises guesswork in model selection and has been shown, through a detailed case study, to boost performance significantly.

On algorithm selection:
Another fundamental challenge in combinatorial optimisation is selecting the most effective algorithm for each problem instance. Our work addressed this by exploring multi-task algorithm selection, where the goal is producing unified classifiers that work across multiple domains without needing specialised, domain-specific features. Our findings revealed that general representations can perform on par with traditional, feature-based approaches, while offering the benefit of simplicity and easy extension to additional domains. This approach simplifies the algorithm selection pipeline and opens the door to transfer learning across diverse combinatorial optimisation domains.

On knowledge graphs:
We developed a knowledge graph to systematically capture and quantify the interplay between constraint optimisation problem formulations, their representations, reformulation strategies, and solvers' performance. In our design, each node represents a distinct problem instance characterised by its domain-specific attributes, modelling parameters, and representation details, while directed edges denote the explicit reformulation operations or transitions between these representations. Edge weights encode quantitative performance metrics. This system provides a rigorous framework for evaluating reformulations and algorithm selection strategies across diverse problem domains. It aims to guide the proactive design of adaptive optimisation systems, linking theoretical insights with practical solver implementations, promoting data-driven decision-making in constraint optimisation and satisfaction. The knowledge graph can be visualised and explored via a graphic interface, providing further insights that are hard to capture numerically.
Exploitation Route Combinatorial optimisation problems are ubiquitous across industry, academia and the third sector. Our work can be integrated into optimisation frameworks to solve these problems more effectively and efficiently.
Sectors Digital/Communication/Information Technologies (including Software)

Healthcare

Transport