Modulcode:	infIO-01a
Englische Bezeichnung:	Integer Optimization
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS19/20 WS20/21 SS22 WS24/25)
Präsenzzeiten:	2V 2Ü 1PÜ
ECTS:	8
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 15 Std. praktische Übungen, 165 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-WInf (MSc WInf (21)) TI (MSc Inf (15)) WI (MSc Inf (15)) WWi (MSc WInf (15))
Lehrsprache:	Englisch
Voraussetzungen:	Inf-ADS Inf-Math-A Inf-Math-B

Kurzfassung:

The lecture gives an introduction to integer optimization. We discuss basic structures like lattices, main theorems, and algorithmic methods to solve integer linear programs.

Lernziele:

Participants of this course will learn algorithmic techniques to solve integer linear programs (IPLs), to model general optimization problems as ILPs and to develop new algorithmic ideas for knapsack, scheduling and packing problems.

Lehrinhalte:

1. Introduction to Lattices (Minkowski's Theorem, Hermite Normal Form, Linear Diophantine Equations, LLL Algorithm)
2. Modelling of Optimzation Problems as Integer Linear Programms
3. Integer Programming in Fixed Dimension (Lenstra's Algorithm)
4. Algorithms for Shortest and Closest Vector Problem
5. Integer Conic Combinations and Applications in Bin Packing (Algorithm by Goemans and Rothvoss)
6. Fourier Transformation and Convolution
7. Integer Programming with few Constraints (Steinitz Lemma, Algorithm by Eisenbrand and Weismantel, Knapsack Problems)
8. Integer Programming with N-Folds (Graver Bases, Augmenting Algorithms)

Weitere Voraussetzungen:

Introduction to Algorithms, Mathematics A and B, or equivalent courses.

Prüfungsleistung:

The prerequisite for the examination is the successful completion of homework (Exercises).

For the exam students are set individual research tasks that they have to work on. The research task consists of 2 parts, which are weighted in a ratio of 2: 1:

1. written elaboration (approx. 8-15 pages) of a research result, e.g. improvement of an algorithm with regard to running time or approximation quality. Instead of a research result, it is also possible to implement a new algorithmic idea and an elaborate it.
2. A presentation of the result.

Lehr- und Lernmethoden:

Lecture on theoretical foundaton of integer linear programming with theoretical exercises to understand the algorithms and the underlying theory. Implemention of algorithms for integer programming (e.g. knapsack, bin packing and scheduling problems) and experimentations.

Verwendbarkeit:

Literatur:

D. Bertsimas and R. Weismantel: Optimization over Integers

T. Rothvoss: Integer Optimization and Lattices

A. Schrijver: Theory of Linear and Integer Programming

T.H. Corman, C.E. Leiserson, R.L. Rivest, and C. Stein: Introductions to Algorithms

C.P. Schnorr: Gitter und Kryptographie (Skript)

Verweise:

Kommentar: