Lecture time:  Monday 14:1516:00 / Wednesday 10:1512:00 

Lecture room:  HS003 (E1.3) 
Lecturers:  Andreas Karrenbauer and Matthias Mnich 
Textbook: 
Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis 
Tutorial time & place: 
There are tutorials on:

This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs.
Linear optimization is a key subject in theoretical computer science. Moreover, it has many applications in practice. A lot of problems can be formulated as (integer) linear optimization problem. For example, combinatorial problems, such as shortest paths, maximum flows, maximum matchings in graphs, among others have a natural formulation as a linear (integer) optimization problem. In this course you will learn:
To this end, basic concepts from polyhedral theory will be introduced. The simplex algorithm and the ellipsoid method will be presented. The lecture concludes with exact and approximation algorithms for NPhard optimization problems. There will be theoretical and practical exercises.
The slides of the first 6 lectures are condensed in the handout. The condensed chapter about the Ellipsoid method can be found here. Please find the annotations below.
Date  Topic  Reference  Homework  Lecturer  Notes 

Apr 17  Overview  Andreas  
Apr 22  Polyhedra  Exercise Sheet 1 , Solution to Sheet 1  Andreas  annotated slides  
Apr 24  Extreme Points Vertices, Basic Feasible Solutions  Andreas  annotated slides  
Apr 29  Polyhedra/Bases in Standard Form  Exercise Sheet 2 , Solution to Sheet 2  Andreas  annotated slides  
May 1  No lecture (Labour Day)  
May 6  Optimality of Vertices, Fourier Motzkin Elimination  Exercise Sheet 3 , file for 4(b), Solution to Sheet 3  Andreas  annotated slides  
May 8  Simplex  Andreas  annotated slides  
May 13  Simplex  Exercise Sheet 4 , Solution to Sheet 4  Andreas  
May 15  Weak and Strong Duality  Exercise Sheet 5 , Solution to Sheet 5  Matthias  slides  
May 20  No lecture (Pentecost Monday)  
May 22  Complementary Slackness and Dual Simplex  Matthias  slides  
May 27  Sensitivity Analysis and Assignment Problem  Exercise Sheet 6 , Solution to Sheet 6  Matthias  slides  
May 29  Network Flow Problems  Matthias  slides  
June 3  The Network Simplex Method I  Exercise Sheet 7 , Solution to Sheet 7  Matthias  slides  
June 5  The Network Simplex Method II  Matthias  slides  
June 10  Negative cost cycle algorithm, Max Flows  Exercise Sheet 8 , Solution to Sheet 8  Matthias  slides  
June 12  Maximum Flows: Edmonds Karp  Matthias  slides  
June 17  The Ellipsoid Method  Exercise Sheet 9 , Solution to Sheet 9  Andreas  
June 19  The Ellipsoid Method  Andreas  
June 24  The Ellipsoid Method  Exercise Sheet 10 , Solution to Sheet 10  Andreas  
June 26  Equivalence of Optimization and Separation  Andreas  
July 1  Interior Point Methods  Exercise Sheet 11 , Solution to Sheet 11  Andreas  
July 3  Integer Programming  Andreas  
July 8  Linear Programming for FixedParameter Algorithms  Exercise Sheet 12 , Solution to Sheet 12  Matthias  Research Paper  
July 10  Linear Programming for Approximation Algorithms  Matthias  Research Paper  
July 15  tba  Matthias  
July 17  tba  Matthias  
July 22  Exam at 2:00 pm, building E2 5, HS I 
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 (doublesided, in your own handwriting)
to the exams. Here are the exam dates:
