Course Details in 2027/28 Session


If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title LH Integer Programming and Combinatorial Optimisation
SchoolMathematics
Department Mathematics
Module Code 06 21624
Module Lead Dr John Leach, Director of Year 3
Level Honours Level
Credits 20
Semester Full Term
Pre-requisites LI Linear Algebra & Linear Programming - (06 25765)
Co-requisites
Restrictions Optional for G100, G103, G1N2 in Year 3
Contact Hours Lecture-46 hours
Tutorial-10 hours
Total: 56 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
  • 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.
  • Students will be able to 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 21624-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions 3 hour Written Unseen Examination (80%); In-course Assessment (20%).
Other
Reading List