Exploiting domain structures in heuristic algorithms for the set covering problem

Exploiting domain structures in heuristic algorithms for the set covering problem

Eligibility: UK/EU/International graduates with the required entry requirements

Reason for eligibility restriction: Funder requirement and timescale

Duration: Full-Time – between three and three and a half years fixed term

Application deadline: 30 June 2020

Interview date: Will be confirmed to shortlisted candidates

Start date:  September 2020

For further details contact: Seyed Mousavi

About the project

Many real-world optimization problems in various domains including computational biology and wireless sensor networks are formulated as the set covering problem, for which no fast optimum algorithm is known to date. In practice, at least for large problem instances, inexact algorithms are used that (are hoped to) provide near-optimum solutions in affordable time. Such algorithms are often based on (meta) heuristics that are general and do not exploit domain-specific structures of given instances, which is exactly the gap considered in this research.

To address this gap, this research develops a novel general data science framework to identify domain-specific heuristics. We will devise several probabilistic heuristics and record extensive data on their performance at run-time, on datasets from at least three domains.

The generated datasets are then analysed using statistical and machine learning data analytics, based on which further modifications are made and improved heuristics are obtained and further analysed. Eventually, selected heuristics for each domain are identified. The resulting algorithms for each domain are expected to outperform existing state-of-the-art.

Finally, the obtained heuristics are integrated under a unique hyper-heuristic algorithm, which determines at run-time which ones to use for a given problem instance.

Funding details

Full studentship which includes tuition fees and living expenses for a doctoral candidate over 3.5 years.

Stipend rates set by UKRI with an annual projected average increase of 1.25% per year.


The successful candidate will receive comprehensive research training including technical, personal and professional skills. All researchers at Coventry University (from PhD to Professor) are part of the Doctoral College and Centre for Research Capability and Development, which provides support with high-quality training and career development activities.

Entry requirements

  • A minimum of a 2:1 first degree in a relevant discipline/subject area with a minimum 60% mark in the project element or equivalent with a minimum 60% overall module average.
  • A Masters’ degree in a relevant subject, or equivalent professional experience would be desirable.
  • The potential to engage in innovative research and to complete the PhD within a 3.5 years.
  • A minimum of English language proficiency (IELTS overall minimum score of 7.0 with a minimum of 6.5 in each component).
  • Highly skilled in algorithm design and computer programming.
  • Deep understanding of computer science theory.

How to apply

All applications require full supporting documentation, a covering letter, plus a 2000-word supporting statement showing how the applicant’s expertise and interests are relevant to the project.

Apply to Coventry University