Dr K Papadaki, NAB 3.14.

MSc Applicable Mathematics, MSc Management Science (Operational Research) and as permitted by the regulations.

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.

• 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.

Students will be assessed by a three-hour formal examination in the ST.