Course Details in 2025/26 Session

Module Title	LM Integer Programming and Combinatorial Optimisation
School	Mathematics
Department	Mathematics
Module Code	06 33233
Module Lead	Dr Yunbin Zhao
Level	Masters Level
Credits	20
Semester	Semester 1
Pre-requisites	LI Linear Algebra & Linear Programming - (06 25765)
Co-requisites
Restrictions	None
Contact Hours	Lecture-46 hours Tutorial-10 hours Guided independent study-144 hours Total: 200 hours
Exclusions
Description	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. This module develops some of the ideas introduced in Management Mathematics and will continue to encourage interest in practical problems. The 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.
Learning Outcomes	By the end of the module, students should be able to: Students will understand that integer programming problems arise in many fields such as engineering, economics, and management. They will understand basic theory and algorithms for integer programs and understand why integer programs are hard to handle in general. They will know how to use the basic techniques of integer programming (branch-bound, relaxation, cutting-plane, heuristics, etc.) to solve integer programming models for a variety of managerial and other practical problems. They will be able to solve an IP problem efficiently by taking into account the particular structure of the problem and interpret the results obtained. They will be able to explain the difference between discrete and continuous optimisation, and understand the uniqueness of the techniques for solving integer programs. Formulate practical problems as discrete optimisations and apply exact or approximate algorithms to problems like shortest path, network flows, transportation, knapsack and travelling salesman problems Demonstrate an understanding of computational complexity and its reduction and of proofs that certain problems are NP hard Explore this topic beyond the taught syllabus
Assessment	33233-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions	3 hour Written Unseen Examination (80%); In-course Assessment (20%)
Other
Reading List