Lecture time:  Tuesday 10:1512:00 / Thursday 12:1514:00 

Lecture room:  HS003 (E1.3) [execpt on May 29, June 26, and July 26., when we are in room 024 (E1.4)] 
Lecturers:  Reto Spöhel and Rob van Stee 
Textbooks: 
Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis (Main reference) Combinatorial Optimization: Algorithms and Complexity by Christos H. Papadimitriou and Kenneth Steiglitz (Secondary reference) For the first part of the course, we also recommend Anke van Zuylen's notes from last year. (There are a few minor typos.) 
Tutorial time & place:  Wednesday 10:1512:00, with Ruben, room 001 (E1.7, cluster building) [except on June 20, when we are in room 008 (E1.7)] or Wednesday 14:1516:00, with Karl, room 023 (E1.4) [except on May 2, when we are in room 022 (E1.4) and on May 16, when we are in room 019 (E1.4)] The tutorials start on May 2 
Tutors:  Karl Bringmann, Ruben Becker 
This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs.
Date  Topic  Reference  Homework  Lecturer  Notes 

Apr 17  Introduction to linear optimization  Sec. 1.2, 1.4, Slides (PPTX, PDF)  Reto  
Apr 19  Matrix notation; general form and standard form of an LP  Sec. 1.1, 1.5, Slides (PPTX, PDF)  Reto  
Apr 24  Polyhedra and convex sets; vertices, extreme points and basic feasible solutions  Sec. 2.1, 2.2  HW 1, Sol 1 
Reto  
Apr 26  Vertices, extreme points and bfs's; degeneracy; linear independency assumption for LP's in standard form  Sec. 2.2  2.4  Reto  
May 1  No lecture (Labour Day)  
May 3  Basic (feasible) solutions of LP's in standard form; basic and nonbasic variables etc.  Sec. 2.3, 2.4  HW 2, Sol 2 
Reto  
May 8  Simplex method: feasible directions, moving from bfs to bfs, optimality conditions  Sec. 3.1, 3.2  HW 3, Sol 3 
Reto  
May 10  Simplex method: anticycling (Bland's rule), finding an initial bfs  Sec. 3.4, 3.5  Reto  
May 15  Simplex method: revised simplex method, full tableau implementation  Sec. 3.3  HW 4 , Sol 4 
Reto  
May 17  No lecture (Ascension Day)  
May 22  Simplex method: number of iterations, Hirsch conjecture etc.; introduction to duality  Sec 3.7; 4.1  4.2  HW 5 , Sol 5 
Reto  
May 24  Weak and strong duality  Sec. 4.3  Reto  
May 29  Complementary slackness, dual simplex  Sec. 4.3  4.5  HW 6 , Sol 6 
Rob  lecture in room 024 (E1.4) 
May 31  Sensitivity analysis  Sec. 5.1  Rob  
June 5  Network flow problems  Sec. 7.1  7.2  HW 7 , Sol 7 
Rob  
June 7  No lecture (Corpus Christi)  
June 12  The network simplex method  7.3  HW 8 , Sol 8 
Rob  
June 14  The network simplex method II  7.3  Rob  
June 19  Negative cost cycle algorithm  7.4  HW 9 , Sol 9 
Rob  
June 21  Maximum flow and the ellipsoid method  7.5, 8.1  Rob  
June 26  The ellipsoid method  8.2 (LN KM), LN  HW 10 , Sol 10 
Rob  lecture in room 029 (E1.5) 
June 28  The ellipsoid method  8.3  8.5  Rob  
July 3  Affine scaling algorithm  9.1  HW 11 , Sol 11 
Rob  
July 5  Potential function algorithm  Rob  
July 10  Integer programming formulations  10.1  HW 12 , Sol 12 
Rob  
July 12  Integer programming methods  11  Rob  
July 17  Integer programming duality in action: The HeldKarp lower bound  11.4, in particular Example 11.10  HW 13 , Sol 13 
Reto  
July 19  HeldKarp continued; integrality gap; Christofides' 3/2appproximation for metric TSP  11.4, Wikipedia  Reto  
July 24  Research Talk: Polynomialtime approximation schemes for NPhard geometric problems  Slides (PPTX, PDF); Paper  Reto  
July 26  Exam in building E2.2, 16:00 
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, and Grundzüge von Algorithmen und Datenstrukturen.  

Policies:  This is a 9creditpoint class ("Stammvorlesung"). There will be two lectures and one exercise session per week. We will hand out exercises every week and each student should score at least 50% in the first half of the course (first 6 exercise sheets) and 50% in the second half in order to be allowed to take the exam. You may hand in the exercises in teams of two.  
Exam Information:  Your final grade will be the best of the final exam and the makeup exam. You may bring an A4 cheat sheet (singlesided, in your own handwriting) to the exams. Here are the exam dates:
