# Integer Optimisation

### Summary:

The course aims to introduce the basic concepts and results of integer optimisation.

### Content:

1. Integer Programming: definition, examples and complexity
2. The linear programming relaxation, Branch & Bound, the integer hull
3. Approximation algorithms via LP-rounding: Set Cover
4. Dynamic Programming: the Knapsack problem, PTAS, Steinitz Lemma and related open problems
5. The Greatest Common Divisor, Branch&Bound and Euclidean Algorithm
6. Lattices, Hermite Normal Form, Shortest and Closest Vector problems
7. Minkowski’s Theorem
8. Transference Bounds: Ellipsoids & general convex bodies, HKZ-reduced bases
9. Integer Programming in Fixed Dimension
10. 2^O(n) algorithm for Shortest Vector Problem

### Prerequisites:

Linear Algebra, Discrete Optimisation (or Introduction to Algorithms)

### Log:

20.02: Basic concepts, examples, integer hull
27.02: Integer hull, Minkowski-Weyl
06.03: Knapsack
13.03: FPTAS for Knapsack, sizes of solutions (notes courtesy of Edmund Hofflin)
20.03: Dynamic Programming for IP (Papadimitriou 1981)
27.03: Steinitz Theorem and speedup for integer programming
03.04: Lattices [5. Chapter 7.1]
17.03:  Minkowski’s Theorem [5. Chapter 7.2]
24.03: Transference Bound in 2D [5. Chapter 7.8]
01.05: Transference Theorem [5. Theorem 7.4] Closest vector in 2^O(n^2)
08.05: The LLL-algorithm [2. Chapter 1.4]
15.05: Approximating shortest vector via Minkowski [2. Chapter 1.6.2]
22.05: CVP in time 2^O(n^2) and Babai’s nearest plane algorithm

### Homework:

Question forum for exercises: https://moodle.epfl.ch/course/view.php?id=16458

1. Homework 1 presentation on Mon. Feb 27.
2. Homework 2 presentation on Mon. Mar 6.
3. Homework 3 presentation on Mon. Mar 13.
4. Homework 4 presentation on Mon. Mar 20.
5. Homework 5 presentation on Mon. Apr 3.
6. Homework 6 presentation on Mon. Apr 24.
7. Homework 7 presentation on Mon. May 1.
8. Homework 8 presentation on Mon. May 8.
9. Homework 9 presentation on Mon. May 15.
10. Homework 10 presentation on Mon. May 22.

### Resources:

1. Alexander Schrijver, Theory of linear and integer programming
2. Thomas Rothvoß, Integer Optimisation and Lattices
3. Oded Regev, Lattices in Computer Science
4. Vijay Vazirani, Approximation Algorithms
5. Alexander Barvinok, A course in Convexity,  AMS