Lecture time:  Tuesday 14:1516:00 / Thursday 14:1516:00 

Lecture room:  HS003 (E1.3) 
Lecturers:  Parinya Chalermsook and Andreas Karrenbauer 
Teaching Assistant; Tutors:  Ruben Becker; Blaga Davidova, Max John, Andreas Schmid and Daniel Vaz 
Good textbooks on the topic include: 

Tutorials: 

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.
This is a 9creditpoint core lecture ("Stammvorlesung"). There will be two lectures and one exercise session per week. We will hand out exercises every week (usually worth 40 points) 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 can also gain points by writing lecture notes of single lectures. In order to do so, you have to use our template. You gain \(\gamma\cdot 40\) points for the notes of one lecture, hereby \(\gamma\in \mathbb{R}\) denotes the quality factor in between 0 and 1 that will be determined by us. Please submit your notes by sending a zipped package that contains everything such that your tex code compiles and the pdf to Ruben not later than one week after the lecture that you took notes for. You can use the old notes from last year and the source code.
The slides of all lectures are condensed in the handout.
Date  Topic  Reference  Homework  Lecturer  Notes 

Apr 15  Overview, ILP  Exercise Sheet 1; Solution 1  Andreas  Slides  
Apr 17  ILP  Chapter 6 in [W] ; Chapter 11.8 in [BT]  Andreas  Slides; Scribe Notes  
Apr 22  Branch and Bound  Chapter 7 in [W] ; Chapter 11.2 in [BT]  Exercise Sheet 2; Solution 2  Andreas  Slides; Scribe Notes 
Apr 24  Branch and Bound, Duality Theory  see above  Andreas  Slides; Scribe Notes  
Apr 29  Duality Theory  Chapter 4.7 in [BT]  Exercise Sheet 3; Solution 3  Andreas  Slides; Scribe Notes 
May 1  No lecture (Labour Day)  
May 6  Strong Duality  Chapter 4 in [BT]  Exercise Sheet 4; Solution 4  Andreas  Slides; Scribe Notes 
May 8  Polyhedral Theory  Chapter 2 in [BT]  Andreas  Slides; Scribe Notes  
May 13  Polyhedral Theory  Chapter 2 in [BT]  Exercise Sheet 5; Solution 5  Andreas  Slides; Scribe Notes 
May 15  Simplex Method  Chapter 5 in [MG]  Parinya  Lecture Notes; Scribe Notes  
May 20  Simplex Method  Chapter 5 in [MG]; Paper by Avis and Kaluzny  Exercise Sheet 6; Solution 6  Parinya  see lecture notes above; Scribe Notes 
May 22  Ellipsoid Method  Chapter 3 in [LGS]; Chapter 7 in [MG]  Parinya  Lecture notes  
May 27  Ellipsoid Method  Chapter 3 in [LGS]; Chapter 7 in [MG]  Exercise Sheet 7; Solution 7  Parinya  see lecture notes above 
May 29  No lecture (Ascension Day)  
June 3  Interior Point Method  Chapter 9 in [BT]  Exercise Sheet 8; Solution 8  Andreas  Slides; Scribe Notes 
June 5  Interior Point Method  Chapter 9 in [BT]  Andreas  Slides  
June 10  TU Matrices  Chapter 3.2 in [W]  Exercise Sheet 9; Solution 9  Andreas  Slides ; Scribe Notes 
June 12  Network Flows  Chapter 7.3, 7.4 in [BT]; Chapter 3.3 in [W]  Andreas  Slides; Scribe Notes  
June 17  Network Flows  Chapter 7.3, 7.4 in [BT]; Chapter 3.3 in [W]  Exercise Sheet 10 Solution 10  Andreas  Slides; Scribe Notes 
June 19  No lecture (Corpus Christi)  
June 24  Matching and Vertex Cover  Chapter 8.2 in [MG]  Exercise Sheet 11; Solution 11  Parinya  Slides ; Scribe Notes 
June 26  Minimum Cuts and Shortest Paths  Parinya  Slides ; Note  
July 1  Approximation Algorithms  Exercise Sheet 12; Solution 12  Parinya  Slides; Scribe Notes  
July 3   canceled (Makeup class TBD)   Parinya  
July 8  LP/SDP for CSPs  Chapter 16.116.3 in [VV]  Exercise Sheet 13; Solution 13  Parinya  Scribe Notes 
July 10  LP/SDP for CSPs  Chapter 6.1 and 6.2 in [WS]  Parinya  
July 15  Hierarchies of Convex Relaxation  Hierarchies, Knapsack  Sample Exam  Parinya  
July 17  Hierarchies of Convex Relaxation  Decomposition Theorem, CT  Parinya  
July 22  Exam  Andreas, Parinya  
July 24  Exam Discussion  Andreas, Parinya 
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.  

Exam Information:  Your final grade will be the best of the final exam and the reexam.
You may bring one A4 cheat sheet (doublesided, in your own handwriting)
to the exams.
