Heuristics for Combinatorial Optimisation

点击翻译按钮获取中文摘要

This research project will be based in the area of combinatorial optimisation, with a particular focus on algorithmic graph theory and heuristics. Problems within this field are known to have many real-world applications in areas such as transportation, logistics, timetabling, and manufacturing. Many of these problems are also known to be NP-hard, and therefore require the use of heuristic and approximate methods. This PhD project will focus on designing, implementing, and testing a range of algorithms in this problem area, focusing on specific problems that will be decided upon in the early stages of the studentship. In doing this, we will seek to deepen our understanding of the problem area and, where appropriate, make connections to other graph-theoretical problems and results. During this PhD, the student will research several methods for tackling combinatorial optimisation problems, including integer programming, heuristics, and metaheuristics. Such techniques will then be implemented for this problem. There will also be opportunities to learn how to interrogate online mapping and graphing APIs to collect and exploit real-world data. There will be a significant element of coding in these projects (most likely C++ and Python) and the student will become experienced in running large scale experiments and statistically analysing results. More generally, the student will become experienced in critical thinking, complex problem solving, and correct decision-making. They will develop the research skills needed to dig deeply into the literature in order to find credible and relevant information. All of these skills are highly transferrable inside and outside of academia, particularly in areas of analytics and data science. The proposed studentship involves a combination of both theoretical and experimental work. Theoretical results will be derived via a thorough review of the literature, mathematical thought, and supervisory discussions. Significant results will be documented through publication with the student named as first author, helping to develop their research portfolio. Upon completion, the desired aim is for the student to have achieved at least one journal publication in addition to their thesis. Opportunities to teach in tutorial sessions will also be provided. A compulsory taught element of the programme will also be provided by NATCOR, a series of week-long residential courses taught at different UK universities. These will be used to introduce the student to important research skills and methods and will help to advance and broaden their knowledge in the field. The student will also attend international conferences, where they will present their work to their peers. The student will also be encouraged to seek publications during their PhD. This will aid the improvement of their writing skills and allow them to gain experience in revising and defending work. From a mathematical and data science perspective, the ubiquitous nature of graphs and networks in the modern world, together with our desire to understand and learn from them, makes this a very important area of study. We expect this studentship to result in at least one paper to be published in a 4-star journal, plus additional output in conference proceedings. Seminars and conference presentations will also be given by the student as the research progresses