Optimization Spring 2005


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


Monday, 9:30-11:00
building 45,  lecture theatre 002
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. 


 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 online

Sample 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:

04-15Introduction[Lee04] Chapter 3
04-18Theorems of Alternatives (part 1)[Lee04] Chapter 5
04-22Theorems of Alternatives (part 2)[Lee04] Chapter 5
04-25Duality (part 1)[Lee04] Chapter 7
04-29Duality (part 2)[Lee04] Chapter 7
05-02Geometry of Linear Programming (part 1)[BerTsi97] Chapter 2
05-06Geometry of Linear Programming (part 2)[BerTsi97] Chapter 2
05-09Summary and look ahead
05-13The Simplex Method[BerTsi97] Chapter 3
05-20Bland's Rule
Finding an initial basic feasible solution

[BerTsi 97] Chapter 3.5
05-23Implementation of the Simplex Method
Dual Simplex Method
[BerTsi97] Chapter 3.3
[BerTsi97] Chapter 4.5
05-27Sensitivity Analysis[BerTsi97] Chapter 5
05-30Midterm Exam
06-03Ellipsoid Method (part 1)[BerTsi97] Chapter 8
06-06Lecture canceled
06-10Integer linear programming: Introduction
Modelling combinatorial problems as ILPs
06-13Modelling combinatorial problems as ((M)I)LPs: MinMax problems,
Boolean expressions, piece-wise linear objective functions.
06-17Unimodularity and Integrality: Main Theorems, 3 examples.
06-20Unimodularity and Integrality: Applications.
06-27Ellipsoid Method (part 2)
07-01Ellipsoid Method (part 2)
07-04Theorem of Beck and Fiala
07-08Randomized Rounding
07-11Hint for the final exam
Approximation algorithms
07-15Approximation 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:

  • 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.