max planck institut
informatik
informatik
| Lecture time: | Tuesday 14:00-16:00 / Thursday 14:00-16:00 |
|---|---|
| Lecture room: | HS 001, Campus E 13 |
| Lecturers: | Khaled Elbassioni and Anke van Zuylen |
| Textbook: | "Introduction to Linear Optimization" by Bertsimas and Tsitsiklis |
| Tutorial time & place: | Monday 16:00-18:00, room 024 E 14. (Exception: the tutorial on Monday May 23 will be held in Room 323 of Building E 1 7) Thursday 9:00-10:00, room 024 E 14. |
| Tutors: | Fahimeh Ramezani, Philipp Klodt |
This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs.
The Makeup exam will be on September 28, from 14-16. Location: Campus E1 4, Room 022. It is a comprehensive written exam. You are allowed to bring a small cheat sheet. The cheat sheet must be no larger than half of an A4 (one sided) and must be hand written (and it has to be written by you, not by a friend with tiny handwriting).
The final exam on Thursday July 21 will be held in our regular lecture room HS 001, E 13.
The exam will start at 14:00.
You are allowed to bring a small cheat sheet. The cheat sheet must be no larger than half of an A4 (one sided) and must be hand written (and it has to be written by you, not by a friend with tiny handwriting).
| Date | Topic | Reference | Homework | Lecturer |
|---|---|---|---|---|
| Apr 14 | Introduction to linear optimization | Ch. 1 | Anke | |
| Apr 19 | What does the feasible region of an LP look like? Polyhedra and convex sets. Vertices, extreme points and basic feasible solutions. |
Sec. 2.1, 2.2 | HW 1 | Anke |
| Apr 21 | Representation of bounded polyhedra, polyhedra in standard form. | Sec. 2.7, 2.3 | Anke | |
| Apr 26 | Polyhedra in standard form, developing the simplex method. | Sec. 2.3, example 3.1,LN 4 | Anke | |
| Apr 28 | An iteration of the simplex method. | Sec. 3.1-3.2,LN 5 | HW 2 | Anke |
| May 3 | Implementation of the Simplex Method - Revised Simplex and Tableaus. | Sec. 3.3,LN 6 | Anke | |
| May 5 | Initialization, Anti-Cycling and Number of Iterations. | Sec. 3.4, 3.5, 3.7,LN 7 | Anke | |
| May 10 | Linear Programming Duality. | Sec. 4.1-4.3,LN 8 | HW 3 | Anke |
| May 12 | Duality, Shortest Path, Complementary Slackness. | Sec. 4.1-4.3,LN 9 | Anke | |
| May 17 | Dual Simplex Method and Sensitivity Analysis. | Sec. 4.4-4.5, 5.1,LN 10 | HW 4 | Anke |
| May 19 | The Assignment Problem and Primal-Dual Algorithms. | LN 11 | Anke | |
| May 24 | The network flow problem and the network simplex algorithm | Sec. 7.1-7.3 | Khaled | |
| May 26 | The network simplex algorithm and the negative cost cycle algorithm | Sec. 7.3,7.4 | HW 5 | Khaled |
| June 7 | The negative cost cycle algorithm and the max flow problem | Sec. 7.4,7.5 | Khaled | |
| June 9 | The max flow min cut theorem | Sec. 7.5 | HW 5: new version | Khaled |
| June 14 | The Ellipsoid method | Ch. 8 | Khaled | |
| June 16 | The Ellipsoid method | Ch. 8 | HW 6 | Khaled |
| June 21 | The Ellipsoid method, Introducion to Interior point methods | Sec. 8.5, 9.1 | Khaled | |
| June 28 | Affine scaling algorithm, potential reduction algorithm | Sec. 9.1, 9.3 | Khaled | |
| June 30 | The potential reduction algorithm | Sec. 9.3 | HW 7 | Khaled |
| July 5 | Integer programming formulations | Ch. 10 | Khaled | |
| July 7 | Integer prorgamming methods | Sec. 11.1, 11.2, 11.4 | HW 8 | Khaled |
| July 12,14 | Dealing with NP-hardness | LN23 | Anke | |
| July 14 | Approximation Algorithms for metric TSP | Mömke-Svensson paper | Anke | |
| July 7 | Single machine scheduling | Sec. 12.5 | Khaled |
| 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, Grundzüge von Algorithmen und Datenstrukturen. |
|---|---|
| Policies: | This is a 9-credit-point class. There will be two lectures and one exercise session per week. Your final grade will be based on your performance in the midterm and final exams---each is worth half of the final grade. You need to get at least 50% of the exercise credit to be able to take the final exam. We will have the exams in our usual classroom (HS 001). There will be a make-up exam; this exam is comprehensive. Your final grade will be the best of the average of your midterm and final exams scores, and the make-up exam. Here are the dates of the exams: |
| Midterm: | Tuesday 31 May at 14:00-16:00 |
| Final: | Thursday 21 July at 14:00-16:00 |
| Make-up: | Wednesday 28 September at 14:00-16:00 |