Integer Programming

The course consists of two elements. Element 1 (6.0 credits): *Mathematical theory for integer optimisation.* This element provides specialised knowledge of optimisation. Particular focus is placed on the properties of integer programmes and techniques used to solve these. Methods include dynamic programming, branch-and-bound and cutting planes. Different families of cutting planes are studied and utilised to solve and provide stronger formulations of integer problems. Heuristics for finding good upper and lower bounds of the objective function are discussed, including greedy techniques and linear program or Lagrangian relaxation. The concepts of convex hull and total unimodularity are discussed. An introduction is given to complexity theory, with examples of problems of different complexity classes.   Element 2 (1.5 credits): *Computer lab work.* In this element, computers are used to implement and apply some technique for integer optimisation.