Lecture time:  Monday 14:0016:00 and Wednesday 14:0016:00 

Lecture room:  HS003, E1.3 
Lecturers:  Nicole Megow , Kurt Mehlhorn , and Julián Mestre 
Tutorial 1:  Thursday 14:0016:00 in HS 003 (Madhusudan Manjunath) 
Tutorial 2:  Friday 14:0016: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 fixedparameter 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 FourierMotzkin 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  Anticycling 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  Zerosum 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, HeldKarpBound (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 9creditpoint 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 reexam. 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 reexam) 
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 reexam 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 