|Lecturer:||Prof. Friedrich Eisenbrand|
- 29.06.2010: Due to an error in the lecture notes, the proof of Proposition 3.2 will not be required in the exam anymore.
- 10.06.2010: Exam announcement is online.
- 04.06.2010: Solutions for sheet 6 are online.
- 26.05.2010: Slides for tomorrows lecture are online.
- 20.05.2010: Solutions for exercise sheet 5 and the sample exam are online.
- 19.05.2010: Exercise sheet 6 is online.
- 05.05.2010: Slides for lecture 10 are online.
- 05.05.2010: Minor fix in sheet 5: In exercise 5, we require that the negative cycle is reachable from the source node s.
- 04.05.2010: Assignment sheet 5 online.
- 03.05.2010: A sample exam is now available.
- 28.04.2010: Chapter 06 of lecutre notes online.
- 24.04.2010: Deadline for exercise sheet 4 extended by one week. Statement (iii) in exercise 4 corrected (as announced in the last exercise session).
- 19.04.2010: Sample solutions for sheet 3 online.
Acquaint students with linear programming models and algorithms. To train them to design and analyze algorithms.
- Linear programming
- Simplex algorithm
- Perturbation and lexicographic rule
- Farkas lemma and duality
- Dual simplex method
- Integer programming
- Total unimodularity
- Ellipsoid method
Grading and Examination
There will be a written exam at the end of the semester.
Your final grade gets computed with the following formula:
where p is the percentage of points obtained in the exam, b is the percentage of bonus points obtained during the semester, and ceil is a function that rounds the argument up to the nearest integer.
The exam is scheduled for July 1th, 12:00 – 15:00 in room SG1. See the announcement
Time and Date
Lecture: Thursdays, 10:15 – 12:00, MA11
Exercise session: Thurdays, 12:15 – 13:00, MA11
- Lecture 1 – 25.02.2010
- Lecture 2 – 04.03.2010
- Lecture 3/4 – 11/18.03.2010
- Lecture 4 – 18.03.2010
- Lecture 5 – 25.03.2010
- Lecture 6 – 01.04.2010
- Lecture 7/8 – 15.04.2010/22.04.2010
- Lecture 9/10 – 29.04.2010/06.05.2010 (last update: 06.05.2010)
- Lecture 10/11 – 06.05.2010/20.05.2010
- Lecture 12 – 27.05.2010
- Simplex example (Maple worksheet)
- Chapter 1: Introduction – Lecture 1
- Chapter 2: Convex sets – Lecture 2
- Chapter 3: The simplex method – Lectures 3/4 (last update: 25.03.2010)
- Chapter 4: Duality – Lecture 5/6 (last update: 31.03.2010)
- Chapter 5: Integer programming – Lecture 7/8 (last update: 28.04.2010)
- Chapter 6: Paths, cycles and ﬂows in graphs – Lecture 9-12 (last update: 28.04.2010)
Assignment sheets and exercise sessions
- Assignment Sheet 1 – Submission: 11.03.2010 – Solution
- Assignment Sheet 2 – Submission: 25.03.2010 – Solution
- Assignment Sheet 3 – Submission: 15.04.2010 – Solution
- Assignment Sheet 4 – Submission: 06.05.2010 – Solution
- Assignment Sheet 5 – Submission: 20.05.2010 – Solution
- Assignment Sheet 6 – Submission: 03.06.2010 – Solution
There will be new exercise sheets every two weeks. You are highly encouraged to work on these exercises on your own or in small groups. A good opportunity to work on these exercises will be the exercise sessions in the two weeks after the exercise sheets have been released. There you can discuss the exercises and the contents of the lecture with the assistants.
You can hand in written solutions for marked exercises on the exercise sheets to obtain bonus points. We will correct them and give you feedback. You can hand in your solutions in groups of up to three persons.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN 0521833787 (available online)
Jean-François Hêche, Thomas M. Liebling, Dominique de Werra, Recherche opérationnelle pour ingénieurs I (library)
Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization. Athena Scientific, 1997. ISBN 1-886529-19-1
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network flows : theory, algorithms, and applications. Prentice Hall, 1993. ISBN 0-13-617549-X