Course Details in 2025/26 Session

Module Title	LH Integer Programming and Combinatorial Optimisation
School	Mathematics
Department	Mathematics
Module Code	06 30558
Module Lead	Nick Webber
Level	Honours Level
Credits	20
Semester	Full Term
Pre-requisites
Co-requisites
Restrictions	Available only to students on the Jinan Dual Degree programmes
Contact Hours	Lecture-44 hours Seminar-24 hours Practical Classes and workshops-4 hours Guided independent study-128 hours Total: 200 hours
Exclusions
Description	Many practical problems such as train and airline scheduling, vehicle routing, production planning, resource management, telecommunications and network design can be modelled as integer or mixed-integer programs. This module presents a comprehensive theory and exact and approximate algorithms for integer programming problem and a wide variety of its applications. This module will start with formulations and illustrative examples of integer programs. Following that, the optimality, relaxation, bound and total unimodularity will be introduced. Based on these fundamental concepts, some computational methods of integer programing such as the dynamic programming, branch and bound, valid inequalities and cutting planes, and heuristic methods will be presented. Modern semi-definite programming (SDP) technique dealing with integer programming is optional and at the discretion of the lecturer in charge. 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.
Learning Outcomes	By the end of the module students should be able to: 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. 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. Solve an IP problem efficiently by taking into account the particular structure of the problem and interpret the results obtained. Explain the difference between discrete and continuous optimisation, and understand the uniqueness of the techniques for solving integer programs. Formulate practical problems as discrete optimisation and apply exact or approximate algorithms to problems such as shortest path, network flows, transportation, knapsack and travelling salesman; show an understanding of computational complexity and its reduction and of proofs that certain problems are NP hard; they will understand the role of matroids in optimisation.
Assessment	30558-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions	Assessment: 3 hour examination (80%), work done during semester (20%) Reassessment: best of 3 hour resit examination (100%) or 3 hour resit examination (80%) and work done during the semester (20%)
Other	Delivery Location: Jinan University, China via Flying Faculty
Reading List