OR408 Half Unit
Combinatorial Optimisation
This information is for the 2013/14 session.
Teacher responsible
Dr Katerina Papadaki NAB 3.14
Availability
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.
Pre-requisites
Some familiarity with graph theory and some knowledge of programming could be desirable.
Course content
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.
Teaching
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.
Formative coursework
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.
Indicative reading
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.
Assessment
Exam (100%, duration: 3 hours) in the main exam period.
Key facts
Department: Management Science Group
Total students 2012/13: 36
Average class size 2012/13: 14
Value: Half Unit
Personal development skills
- Problem solving
- Application of numeracy skills
- Specialist skills