Royal Holloway logo and departmental theme Royal Holloway, University of London

MSc by Research in Computer Science

Back to MSc by Research in Computer Science Home Page

Discrete Optimisation Strand


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.


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


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


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.
Back to MSc by Research in Computer Science Home Page

Last updated Fri, 23-Jan-2009 15:12 GMT / PS
Department of Computer Science, University of London, Egham, Surrey TW20 0EX
Tel/Fax : +44 (0)1784 443421 /439786
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@
@@('' )@@