Integer Optimisation ‒ Disopt ‐ EPFL

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

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

Linear Algebra, Discrete Optimisation (or Introduction to Algorithms)

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