This is a year three module. It is taught intensively by Birmingham academics over eight weeks. There is continuous assessment and a final examination.
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 programming 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.
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.
- 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.