Effectiveness of the Maximum Satisfiability formulation of the set covering problem and its variants

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

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

Application deadline: This opportunity will only remain open until a suitable candidate is identified and appointed- early application is therefore highly recommended

Interview date: Will be confirmed to shortlisted candidates

Start date: Entry points are September, January and May.

Please apply at the earliest opportunity as this project will be recruited to as soon as a suitable candidate is identified.

For further details contact: Dr Seyed Mousavi

Introduction

Coventry University (CU) and the Research Centre for Data Science (CDS) is inviting applications from suitably-qualified graduates for a self-funded PhD position.

The Research Centre for Data Science (CDS) is based in the Faculty of Engineering, Environment and Computing (EEC) of Coventry University.  It provides a hub to develop cutting edge research in the areas of Artificial Intelligence, Data Science and Future Computing Technologies. The centre has a vocation to push the boundaries of both fundamental science and practical applications. 

About the project

The Maximum Satisfiability (MaxSAT) problem is to determine the maximum number of clauses from a given Boolean formula in conjunctive normal form that can be made true by an assignment to the variables.  Many exact and inexact solvers are proposed for MaxSAT every year at the satellite events of the annual SAT conference. The formulation of other problems as Max-SAT has been beneficial in several cases. Therefore, a natural question is whether other NP-hard optimisation problems could be solved more effectively via MaxSAT formulation.

Among important NP-hard optimisation problems are the set covering problem and its variants. This project will identify those variants for which a MaxSAT formulation leads to improved exact and/or inexact solvers.

To that end, we will first identify recognised variants of the set covering problem. Then, we will see if the MaxSAT formulation of such a variant is affordable, i.e. is performed in O(n²) time. For those with such a formulation, we integrate the implemented formulation with existing MaxSAT solvers to obtain new solvers that potentially outperform the existing solvers. The results will be presented in journal papers and the source code for the resulting solvers will become available to accelerate their usage and further research.

Funding 

This project is offered on a self-funded or externally funded basis. We particular welcome applications from candidates with funding from their home governments or sponsorship from companies.

For the academic year 2020/21:  English, Welsh and EU students can apply to borrow up to £26,445 to help cover the cost of their PhD.  Find out more about PHD Loans.

Benefits

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. 
  PLUS 
  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)

Additionally

The candidate should be comfortable with programming and algorithm design.

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.