Integer Programming

Module Title - Integer Programming
Number of credits - 10

Module 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.

By the end of the module you will 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.
  • By the end of the module students should be able to explore these topics beyond the taught syllabus.

Teaching and assessment:

  • Assessment: Exam  (90%), Coursework (10%).
  • Semester 1.
  • 22 hours of lectures, 5 hours example classes.