MSc by Research in Computer Science

Discrete Optimisation Strand

Overview

This course will cover classical and modern methods of discrete optimisation (DO). To grasp the course content the students will need to study theoretical basis of various DO algorithms and heuristics and to code some of them in order to carry out certain computational experiments. The students will also learn about various applications of discrete optimisation.

Aims

This course's aim is to provide the student with sufficient understanding of theoretical basis, design, implementation and analysis of DO algorithms and heuristics.

Objectives

At the end of the course the student should have a general understanding of basic areas of discrete optimisation and detailed understanding of specific areas where coursework will be carried out. The student should have a good working knowledge mathematical basics, algorithmic approaches and applications of discrete optimisation.

Sessions of Provisional Syllabus

The course will consist of three parts.

1. Exact Algorithms:
   Complexity of DO problems; Polynomial Solvable Problems; Branch-and-Bound and Branch-and-Cut Algorithms
2. DO Heuristics:
   Construction Heuristics; Local Search; Meta-Heuristics
3. Analysis of DO Heuristics:
   Computational Analysis of Heuristics; Approximation Analysis of Heuristics; Domination Analysis of Heuristics

Supervisors

Gregory Gutin, Anders Yeo

Main References

1. G. Ausiello et al. Complexity and Approximation, Wiley, 2000.
2. F. Glover and M. Laguna, Tabu Search, Kluwer, 1997.
3. Traveling Salesman Problem and Its Variations. G. Gutin and A.P. Punnen (eds.), Kluwer, 2002.
4. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Dover, 1998.
5. L.A. Wolsey, Integer Programming, Wiley, 1998.