Integer Optimisation

Instructor: Prof. Friedrich Eisenbrand

Assistant: Martina Gallato 

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 

 

Content of lectures:

  • 21.02. – Minkowski Weyl Theorem for Cones, separation Theorem (see video),  Integer hull is a polyhedron [1, p. 230-231]
  • 28.02. – Integral polyhedra [1, p. 231-232], Totally unimodular matrices [1, p. 266-269]
  • 07.03. – Branch and Bound [1, p. 360-361]
  • 14.03. – Dynamic Programming, Knapsack FPTAS [3, p. 68 – 70]
  • 21.03. – Steinitz Theorem and Dynamic Programming for integer programming (E. Weismantel 2020)
  • 28.03. – Lattice and Mikowski’s Theorem [2. p. 5-10]
  • 04.04. – The LLL Algorithm [2. p. 12-18]
  • 11.04. – Solving random subset sum instances [2. p. 21-22]
  • 25.04. – The Hermite Normal Form [this paper p. 5-10]
  • 02.05. – Dual lattices and approximating shortest vector via Minkowski’s Theorem [2. p. 22-24]
  • 09.05. Excursion to randomized algorithms. Miller-Rabin test. [blackboard]
  • 16.05. Transference bounds [5. p. 311-314]
  • 25.05. The Voronoi Cell of a lattice and closest vector [2. p. 55-58]
  • 01.06. A singly exponential algorithm for CVP [2. p. 59-60]

 

Prerequisites:

Linear Algebra, Discrete Optimisation (or Introduction to Algorithms)

Organisation:

Lectures and Videos: 
  • Weekly videos of 35-45 minutes to watch before the course, published here
  • On-site lecture on Monday 14h00-15h00 MAA331
  • Exercise session on Monday 15h00-17h00 MAA331. The exercise sessions start on Monday 28th February
  • The exercise sets and all relevant material are published here
Grading, Exam and Exercises: 
  • There will be a final oral exam
  • 20% of final grade is determined by exercise presentations during exercise session 

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