Integer Programming Methods, LNMB 2017–2018

Course description

The vast majority of problems in combinatorial optimization can be formulated as an integer linear program (ILP): Maximize or minimize a linear objective function subject to linear constraints and the additional restriction that the decision variables can take only integer values (typically only 0/1). This makes ILPs a perfect tool for formulating problems in combinatorial optimization; many software packages are available for this. The drawback is that solving ILPs is generally a computationally demanding task; it is NP-hard. Nevertheless, in practice, also these problems have to be solved. In this part of the course we focus on techniques for solving ILPs. The following topics will be treated:

• the expressive power of ILPs in combinatorial optimization
• geometry of integer linear programs: the interplay of polyhedra and lattices
• easy and difficult ILPs
• geometric techniques based on cutting planes
• algebraic techniques based on lattice basis reduction

Literature

• Conforti, Cornuéjols, and Zambelli, Integer programming, Springer 2014 (available online via springerlink)

Prerequisites

• Knowledge of linear algebra and linear programming.

Examination

Take home problems. The problems and deadlines will be posted on this site.
Solutions to homework can be handed in by e-mail dion[dot]gijswijt[at]gmail[dot]com. Only .pdf documents will be accepted.

Lectures

• 20 Nov: Introduction
  • Slides: (PDF)
  • Book: Chapter 1 and part of Chapter 2 (examples of problems that can be modelled as ILP).
• 27 Nov: Linear Inequalities and Polyhedra
  • Summary: (PDF)
  • Book: Chapter 3.1 to 3.12
• 4 Dec: Integral Polyhedra and TU matrices
  • Summary: (PDF)
  • Book: Chapter 4.1, 4.2, 4.8, part of 4.3, 4.4
• 11 Dec: CANCELLED
• 18 Dec: Total dual integral systems
  • Summary: (PDF)
  • Book: Chapter 4.6, 4.7, part of 4.5
• 22 Jan: Extended formulations
  • Summary: (PDF)
  • Book: Chapter 4.10
• 29 Jan: Cutting planes
  • Summary: (PDF)
  • Book: Chapter 5.2.1, 5.2.2
• 5 Feb: Traveling Salesman Problem
  • Summary: (PDF)
  • Book: Chapter 2.7, 4.3.1, 4.3.3, 7.4.1, 7.4.2
• 12 Feb: LLL-algorithm
  • Summary: (PDF)
  • Book: Chapter 9.1.1
• 19 Feb: Integer programming in fixed dimension
  • Summary: (PDF)
  • Book: Chapter 9.1
• 5 March: Deadline homework sets.

Homework sets

Solutions to homework can be handed in by e-mail: dion[dot]gijswijt[at]gmail[dot]com.
Only .pdf documents will be accepted. Although use of LaTeX is highly recommended, scans of handwritten solutions are allowed (as long as they are in pdf and are not too large).

De deadline for all four homework sets is 5 March 2018 (two weeks after the last planned lecture).

• Set 1
  • Material: Lectures week 1-3
  • Deadline: 5 March 2018
  • Problems: (PDF)
• Set 2
  • Material: Lectures week 4-5
  • Deadline: 5 March 2018
  • Problems: (PDF)
• Set 3
  • Material: Lectures week 6-7
  • Deadline: 5 March 2018
  • Problems: (PDF)
• Set 4
  • Material: Lectures week 8-9
  • Deadline: 5 March 2018
  • Problems: (PDF)