Core06: Optimisation - Archived material for the year 2019-2020

2019-2020
Lecturer(s): 
Prof. Raphael Hauser
Course Term: 
Michaelmas
Course Overview: 

In many practical problems that can be approached via linear optimisation problems, some or all of the variables are constrained to take binary or integer values. For example, in optimal crew scheduling a pilot cannot be fractionally assigned to two different flights at the same time. Likewise, in combinatorial optimisation an element of a given set either belongs to a chosen subset or it does not. Integer programming is the mathematical theory of such problems and of algorithms for their solution. The aim of this course is to provide an introduction to some of the general ideas on which attacks to integer programming problems are based: generating bounds through relaxations by problems that are easier to solve, and branch-and-bound.
Students will understand some of the theoretical underpinnings that render certain classes of integer programming problems tractable ("easy'' to solve), and they will learn how to solve them algorithmically. Furthermore, they will understand some general mechanisms by which intractable problems can be broken down into tractable subproblems, and how these mechanisms are used to design good heuristics for solving the intractable problems. Understanding these general principles will enable the students to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.
This course is primarily structured as a reading course with students watching online lectures and attending regular sessions to discuss particular issues.

Course Synopsis: 

Linear programming, Total Unimodularity, Branch-and-Bound, Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm, Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm, the Generalised Assignment Problem.

Reading List: 

Course lecture notes (Oxford B6.3 Integer Programming).
M. Conforti, G. Cornuejols, G. Zambelli, Integer Programming (Springer 2014), ISBN 978-3-319-11007-3.
L. A. Wolsey, Integer Programming (John Wiley & Sons, 1998), parts of chapters 1-5 and 7.

Please note that e-book versions of many books in the reading lists can be found on SOLO and ORLO.