|
Lecturers:
| Dr. Ernst Althaus |
building 46 (MPI), room 308 |
| Dr. Benjamin Doerr |
building 46 (MPI), room 304 |
- Linear optimization is a key subject in theoretical computer
science.
Many 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
Contents:
Dates:
| Lecture | Monday, 9:30-11:00 |
building 45,
lecture theatre 002 |
| Lecture | Friday, 13:30-15:00 |
building 45, lecture theatre 002 |
| Midterm Exam |
May 30th, 9:15-12:15 | bulding 45, lectrue theatre 002 |
| Final Exam |
July 25th, 9:15-12:15 | bulding 45, lecture theatre 002 |
| Repeating Exam |
tba | tba |
| First lecture |
Friday April 15 |
- The lecture will be held in english. There will be exercise groups held in german and english.
- J. Beck and V. T. Sos, Discrepancy Theory. In: R. Graham, M. Grötschel and L. Lovasz, Handbook of Combinatorics, 1405-1446, Elsevier, 1995.
- J. Spencer, Ten lectures on the probabilistic method, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
Language:
Grading:
The credit for this course is 9 graded Leistungspunkte. The credit is awarded upon successful participation at the midterm and final exam. The course grade is determined by the grade of the midterm exam (50%), and the grade of the final exam (50%). At least 50% of the credits in the exercises number 1 to 4 are necessary to be admitted to the midterm exam; at least 50% of the credits in the exercises number 5 to 10 are necessary to be admitted to the final exam. If you fail exactly one of the two exams (but were admitted to both), you will be admitted to the repeating exam. If you pass the repeating exam, your grade will be the average of the two exams you passed.Midterm Exam
Results are now onlineSample solutions: ps or pdf.
Final Exam
Results are now online .Sample solutions (sorry for the bad style): ps or pdf.
Further notices: Many of you did a really good job! Also, almost all of you did not lose points for bad writing or other forbidden stuff. Congratulations! Students with immatriculation numbers 2030251, 2507218, 2507783, 2501804 and 2501070 (in random order) showed some particular skills which might be highly useful for a masters/diploma/PhD project in one of my [Benjamin's] research areas (e.g. discrete maths, randomized algorithms, combinatorial problems in computer science). So if you're at least vaguely interested, please contact me [note that I'm travelling for four weeks, so be patient or rather send me an email].
For those who were less lucky in one of the two exams, there will be a second chance ("Nachschreibklausur"). This will take place in the first week of the semester. You have to register for this by sending an email to Ernst Althaus before September 1st.
You can have a look at your exam on Thursday, August 4th, at 2pm-3pm in Room 024.
Thanks for attending the lecture. Have a nice summer break!
Repeating Exam
You should have received an eMail with the date, if you have to take the repeating exam.Lecture details:
| Date | Topic | Reference |
| 04-15 | Introduction | [Lee04] Chapter 3 |
| 04-18 | Theorems of Alternatives (part 1) | [Lee04] Chapter 5 |
| 04-22 | Theorems of Alternatives (part 2) | [Lee04] Chapter 5 |
| 04-25 | Duality (part 1) | [Lee04] Chapter 7 |
| 04-29 | Duality (part 2) | [Lee04] Chapter 7 |
| 05-02 | Geometry of Linear Programming (part 1) | [BerTsi97] Chapter 2 |
| 05-06 | Geometry of Linear Programming (part 2) | [BerTsi97] Chapter 2 |
| 05-09 | Summary and look ahead | |
| 05-13 | The Simplex Method | [BerTsi97] Chapter 3 |
| 05-20 | Bland's Rule Finding an initial basic feasible solution | [BerTsi 97] Chapter 3.5 |
| 05-23 | Implementation of the Simplex Method Dual Simplex Method | [BerTsi97] Chapter 3.3 [BerTsi97] Chapter 4.5 |
| 05-27 | Sensitivity Analysis | [BerTsi97] Chapter 5 |
| 05-30 | Midterm Exam | |
| 06-03 | Ellipsoid Method (part 1) | [BerTsi97] Chapter 8 |
| 06-06 | Lecture canceled | |
| 06-10 | Integer linear programming: Introduction Modelling combinatorial problems as ILPs | |
| 06-13 | Modelling combinatorial problems as ((M)I)LPs: MinMax problems, Boolean expressions, piece-wise linear objective functions. | |
| 06-17 | Unimodularity and Integrality: Main Theorems, 3 examples. | |
| 06-20 | Unimodularity and Integrality: Applications. | |
| 06-27 | Ellipsoid Method (part 2) | |
| 07-01 | Ellipsoid Method (part 2) | |
| 07-04 | Theorem of Beck and Fiala | |
| 07-08 | Randomized Rounding | |
| 07-11 | Hint for the final exam Approximation algorithms | |
| 07-15 | Approximation algorithms (2) |
Literature for the second half of the lecture: I collected the stuff from different sources, so it is hard to really recommend a reference that helps in preparing for the exam. If you know what I did in the lecture, you are well prepared. For further reading on discrepancy theory, here are some references: