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 |
The lecture gives an introduction to integer optimization. We discuss basic structures like lattices, main theorems, and algorithmic methods to solve integer linear programs.
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.
Introduction to Algorithms, Mathematics A and B, or equivalent courses.
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:
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.
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)