Example PhD

Parallel branch and bound algorithms for graph problems

Supervisor: Dr C.L. Mumford

Keywords: High performance computing, combinatorial optimization, graph algorithms.

In operational research branch and bound methods are popular exact techniques for solving integer programming problems. However, for NP hard problems, such as the travelling salesman problem, and numerous others, exact methods such as branch and bound, are only practicable for relatively small instances. In recent years however, improvements in computer technology has made it possible to solve larger instances of hard combinatorial problems than ever before. This project will use the high performance computing resources available in Cardiff to explore a range of models of parallel branch and bound algorithms, and explore the most efficient ways to distribute the processing.

Key Skills/Background: Open to computing or mathematics graduates and postgraduates

Contact: Dr C.L. Mumford to discuss this research topic.