Level of study Third/Final year
Credit value 20
Semester Students may study 1, 2 or both.
Pre-requisite modules 22503
Semester 1: Many practical problems such as train and airline scheduling, vehicle routing, production planning, resource management and telecommunications network design can be modelled as integer (or mixed-integer) programs. This module presents a comprehensive theory of and exact and approximate algorithms for integer programming and a wide variety of its applications. Starting from formulations and illustrative examples of integer programs to optimality, relaxation to methods such as branch and bound, cutting planes and valid inequalities, Lagrangean relaxation and heuristic methods. Basic computational complexity theory will be also introduced. Modern semi-definite programming (SDP) technique dealing with integer programming is optional and at the discretion of the lecturer in charge.
Semester 2: The second part of this module presents a systematic survey of methods of optimisation for problems with discrete features, and relates them to practical problems such as finding the cheapest route through a transportation network or efficiently assigning resources to objectives. The concept of computational complexity leads to a classification of problems into grades of hardness and to the concept of the efficiency of an algorithm.