Dr Katerina Papadaki NAB 3.14

This course is available on the MSc in Applicable Mathematics and MSc in Management Science (Operational Research). This course is available as an outside option to students on other programmes where regulations permit.

Some familiarity with graph theory and some knowledge of programming could be desirable.

The course is intended as an introduction to discrete and combinatorial techniques for solving optimisation problems, mainly involving graphs and networks, as described under the headings of the lecture course below. OR406.1 Foundations of Mathematical Programming. An introduction to the mathematical foundations of mathematical programming. OR408 Combinatorial Optimisation. Shortest path algorithms in networks, various matching algorithms, the Chinese postman problem, solution techniques for Travelling Salesman and other Combinatorial Optimisation problems. Also polyhedral combinatorics, heuristic approaches and a brief introduction to complex theory.

20 hours of lectures and 15 hours of seminars in the LT. 3 hours of lectures in the ST.

OR406.1 -  four LT; OR406.1A two x 1.5 LT.

OR408 - sixteen LT; OR408A eight x 1.5 LT and one revision session.

Lecture notes containing problems are supplied. Written answers will be expected by the lecturer on a regular basis, and the problems will be discussed in the problem class.

Relevant sections from the following texts will provide useful supplementary reading - N Christofidis, Graph Theory: An Algorithmic Approach; Nemhauser, Rinnooy Kan & Todd, Optimization; Nemhauser & Wolsey, Integer and Combinatorial Optimization; C F Laywine & G L Mullen, Discrete Mathematics using Latin Squares, Wiley & Sons 1998. Alexander Schrijver, Combinatorial Optimization, Ahuja, Magnanti and Orlin, Network Flows, Jon Lee, A First Course in Combinatorial Optimization, Cambridge University Press 2004. As concise reference material for the graph theoretic part of the course R Wilson's book Introduction to Graph Theory should prove useful.

Exam (100%, duration: 3 hours) in the main exam period.