max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Optimization (Summer 2010)

Announcements [RSS feed]

  • 23-Sep: The oral re-exam (duration:30 minutes) shall take place on October 8 and 12. The available time slots are 14:00-17:00 on both the dates. You should register yourself for the exam by sending an e-mail to our secretary, Christina Fries (chfries@mpi-inf.mpg.de) with your preferred date.
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.


More Courses of the Algorithms and Complexity Group


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