max planck institut
informatik
informatik
| Lecture time: | Monday 14:00-16:00 and Wednesday 14:00-16:00 |
|---|---|
| Lecture room: | HS003, E1.3 |
| Lecturers: | Nicole Megow , Kurt Mehlhorn , and Julián Mestre |
| Tutorial 1: | Thursday 14:00-16:00 in HS 003 (Madhusudan Manjunath) |
| Tutorial 2: | Friday 14:00-16:00 in HS 001 (Megha Khosla) |
This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs. We plan to cover modeling techniques and applications, the simplex method, duality theory, integer programming concepts, branch and bound, lagrangean relaxation, cutting planes, and a brief outlook on approximation algorithms and fixed-parameter tractability.
| Date | Topic | Reference | Homework | Lecturer |
|---|---|---|---|---|
| April 12 | Introduction to linear optimization | BT 1 | Kurt | |
| April 14 | Polyhedra, extreme points, etc | BT 2 / LN 2 | HW 1 | Julian |
| April 19 | Representation of bounded polyhedra Fourier-Motzkin elimination |
BT 2 / LN 3 | Julian | |
| April 21 | Developing the simplex algorithm | BT 3 / LN 4 | HW 2 | Julian |
| April 26 | Tableau implementation of simplex | BT 3 / LN 5 | Julian | |
| April 28 | Anti-cycling rules and finding an initial solution | BT 3 / LN 6 | HW 3 | Julian |
| May 3 | Linear programming duality | BT 4 / LN 7 | Julian | |
| May 5 | Zero-sum games | LN 8 | HW 4 | Julian |
| May 10 | Assignment problem | BT 7 / LN 9 | Julian | |
| May 12 | Dual simplex | BT 4 | HW 5 | Julian |
| May 17 | Computational efficiency of the simplex algorithm
diameter of polytopes, the perfect matching polytope |
BT 3, CCPS 6 | Nicole | |
| May 19 | Implementation of the simplex algorithm | LN 12 | HW 6 | Kurt |
| May 26 | Midterm exam | |||
| May 31 | Ellipsoid method | LN 14 | Kurt | |
| June 2 | Introduction ILP, integral polyhedra, TDI | KV 5, LN 15 | HW 7 | Nicole |
| June 7 | TDI, totally unimodular matrices | KV 5, LN 16 | Nicole | |
| June 9 | Interior point method | LN 17 | HW 8 | Kurt |
| June 14 | totally unimodular matrices, cutting planes | KV 5, LN 18 | Nicole | |
| June 16 | cutting plane methods, branch and bound algorithms | KV 5, LN 19 | HW 9 | Nicole |
| June 21 | TSP comb ineq., branch and bound algorithms | CCPS 7, LN 20 | Nicole | |
| June 23 | Lagrangean relaxation, Held-Karp-Bound (TSP) | LN 21 | HW 10 | Nicole |
| June 28 | Introduction approximation algorithms | LN 22 | Nicole | |
| June 30 | LP rounding | LN 23 | HW 11 | Nicole |
| July 5 | Cutting Stock Problem | LN 24 | HW 12 | Kurt |
| July 7 | Randomized LP Algorithm | LN 25 | Kurt | |
| July 12 | Set Cover Problem | LN 26 | Kurt | |
| July 15 | Steiner Tree problem | LN 27 | Kurt | |
| July 19 | Generalized Steiner Tree problem | LN 28 | Kurt |
| 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 course. There will be homeworks due every week. Homework scores do not count towards your final grade, but you need to collect at least 50% of the homework points to be eligible to take the exams. There will be a midterm and a final exam. Your final grade will be the average of these two exams. You can improve your grade by taking an oral re-exam. In order words, your grade will be max((M+F)/2,R). | |
| References: | Introduction to Linear Optimization by Bertsimas and Tsitsiklis, Athena Scientific, 1997.
Combinatorial Optimization by Cook, Cunningham, Pulleyblank, and Schrijver, Wiley- Interscience, 1997. Combinatorial Optimization: Theory and Algorithms by Korte, Vygen, Springer, 2008. |
|
| Exam dates: | 26/05 (midterm) 21/07 (final) October 8,12 (oral re-exam) |
Below you'll find your grade for the class. These grades are based on your preformance on the midterm and final exams. If you want to impove your grade, you can take the oral re-exam in October. If you have any question regarding your grade, please get in touch with us. In order to preserve your privacy we only display the last four digits of your matriculation number.
| Matr # | Grade |
|---|---|
| 9269 | 4.0 |
| 8685 | 4.0 |
| 2997 | 1.7 |
| 9206 | 4.0 |
| 0256 | 4.0 |
| 9742 | 4.0 |
| 5506 | 4.0 |
| 0491 | 4.0 |
| 2821 | 3.0 |
| 0267 | 3.0 |
| 5251 | 3.0 |
| 3962 | 3.0 |
| 3902 | 3.0 |
| 9478 | 2.7 |
| 9104 | 2.7 |
| 8889 | 2.7 |
| 0689 | 2.7 |
| 0886 | 2.3 |
| 4992 | 2.3 |
| 9698 | 2.3 |
| 4764 | 2.0 |
| 0537 | 1.7 |
| 3509 | 1.3 |
| 5294 | 1.3 |
| 0940 | 1.3 |
| 9289 | 1.3 |
| 9146 | 1.0 |
| 0013 | 5.0 |