Lecturer	Raphael Hauser
Degrees	Schedule B2 — Computer Science Schedule B2 — Mathematics and Computer Science
Term	Hilary Term 2009  (16 lectures)

Overview

In many areas of practical importance linear optimisation problems occur with integrality constraints imposed on some of the variables. In optimal crew scheduling for example, 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.

Learning outcomes

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 render the students able to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.

Synopsis

1. Course outline. What is integer programming (IP)? Some classical examples.
2. Further examples, hard and easy problems.
3. Alternative formulations of IPs, linear programming (LP) and the simplex method.
4. LP duality, sensitivity analysis.
5. Optimality conditions for IP, relaxation and duality.
6. Total unimodularity, network flow problems.
7. Optimal trees, submodularity, matroids and the greedy algorithm.
8. Augmenting paths and bipartite matching.
9. The assignment problem.
10. Dynamic programming.
11. Integer knapsack problems.
12. Branch-and-bound.
13. More on branch-and-bound.
14. Lagrangian relaxation and the symmetric travelling salesman problem.
15. Solving the Lagrangian dual.
16. Branch-and-cut.

Syllabus

Simplex algorithm for linear programming in dictionary form, linear programming duality and sensitivity analysis, alternative formulations of integer programmes, ideal formulations of integer programmes, optimality conditions for integer programming, integer programming duality, linear programming relaxation, combinatorial relaxation and Lagrangian relaxation of integer programming problems, total unimodularity, network flow models, submodularity, matroids and the greedy algorithm, maximum weight subtree problems, augmenting paths, bipartite matching, the assignment problem, integer knapsack problems, dynamic programming, branch-and-bound, the symmetric travelling salesman problem, the subgradient algorithm, elementary branch-and-cut approaches.

Reading list

• L.A. Wolsey, Integer Programming, John Wiley & Sons, 1998, parts of chapters 1-5 and 7.
• Lecture notes and problem sheets posted on the course web page.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.