Discrete Optimization
Core Course, 4+2
Basic Information
| Lecturer: | Andreas Karrenbauer |
|---|---|
| Lectures: | Wednesday + Thursday, 14:00 - 16:00 (room 024 in E1 4 and online) |
| Teaching Assistant: | Paolo Luigi Rinaldi |
| Tutorials: | Monday 10:00 - 12:00 (room 023 in E1 4) Friday, 14:00 - 16:00 (room 024 in E1 4, on 03.05 room 023 in E1 4, on 07.06 room ??? in E? ?) |
| Credits: | 9 |
| Prerequisites: | Basics in linear algebra, discrete mathematics, calculus, algorithms, and complexity. At Saarland University these topics are covered in the bachelor courses Mathematik für Informatiker 1 & 2, Grundzüge der Theoretischen Informatik, and Grundzüge von Algorithmen und Datenstrukturen. |
| Exam: | Your final grade will be the best of the final exam and the re-exam. You may bring one A4 cheat sheet (double-sided, in your own handwriting) to the exams. Exams might be oral if there is only a small number of registered participants. Final Exam: 07.08.2024 Re-Exam: TBA
|
If you would like to participate in this course, please register to this Moodle.
Description
This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs.
Linear optimization is a key subject in theoretical computer science. Moreover, it has many applications in practice. A lot of problems can be formulated as (integer) linear optimization problem. For example, combinatorial problems, such as shortest paths, maximum flows, maximum matchings in graphs, among others have a natural formulation as a linear (integer) optimization problem. In this course you will learn:
- how to optimize a linear function subject to linear constraints
- how to formulate combinatorial problems as (integer) linear optimization problems
- how to solve them
To this end, basic concepts from polyhedral theory will be introduced. The simplex algorithm and the ellipsoid method will be presented. The lecture concludes with exact and approximation algorithms for NP-hard optimization problems. There will be theoretical and practical exercises.
Policies
This is a 9-credit-point core lecture ("Stammvorlesung"). There will be two lectures and one exercise session per week. We will hand out exercises every week. Teams of three are allowed provided that everyone understands all solutions. Admission to the exam is secured with 50% of the points. There will be optional practical exercises with bonus points to make up for missed points.
Lectures
The first lecture will be on Wednesday, 17 April 2024.
Access to the virtual classrum, all further related information, and the course material (slides, handout, supplement) will be accessible in our Moodle.
Literature
- Integer Programming by Laurence A. Wolsey.
- Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.