Optimization
Core Course, 4+2
Basic Information
Lecturer:  Andreas Karrenbauer 

Lectures:  Tuesday + Thursday, 14:00  16:00, E1.4 room 024; 
Teaching Assistant:  Maximilian John 
Tutors:  Ahmed Abbas, Sören BundBecker 
Tutorials:  Monday, 1012, room 024, E1 4 (except on May, 7 and May, 22: room 021, E1 4) Friday, 1214, room 024, E1 4 
Credits:  9 
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:  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. Exams might be oral if there is only a small number of registered participants. Final Exam: July 27th, 13:30  16:30, GüntherHotzHörsaal ReExam: TBA

Announcements
 If you want to participate in the course, please register to our mailing list!
 The tutorial assignment is finished and can be found here.
 The lectures are permanently moved to room 024 in E1.4.
 The tutorial on Pentecost Monday (21st of May) is going to be moved to Tuesday (22nd of May), same time (1012) to room 021 in E1 4.
Description
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:
 how to optimize a linear function subject to linear constraints
 how to formulate combinatorial problems as (integer) linear optimization problems
 how to solve them
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.
Policies
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.
Lectures
The slides of all lectures condensed in a handout can be found here. The supplement containing important definitions, theorems and proofs can be found here.
Date  Topic  Reference  Homework  Notes 

Apr 10  Overview  Sheet 0, Solution 0  Slides  
Apr 12  Polyhedra and Integer Optimization  Chapter 6 in [W]; Chapter 11.8 in [BT]  Slides  
Apr 17  Integer Optimization and Applications  Chapter 7 in [W]; Chapter 11.2 in [BT]  Sheet 1, Solution 1  Slides 
Apr 19  Branch and Bound, Duality  Chapter 4.7, 11.2 in [BT]  Slides  
Apr 24  FourierMotzkin Elimination, Weak/Strong Duality  Chapter 2.8, 4 in [BT]  Sheet 2, Solution 2  Slides 
Apr 26  Complementary Slackness, Vertices and Facets  Chapter 2.6, 2.3 in [BT]  Slides  
May 3  Existence and Optimality of Extreme Points  Chapter 2.5, 2.6 in [BT]  Sheet 3, Solution 3  Slides 
May 8  Bruteforce LP algorithm, degeneracy, basic directions  Chapter 3.1, 3.2 in [BT]  Sheet 4, Solution 4  Slides 
May 15  The Simplex method  Chapter 3 in [BT]  Sheet 5, Solution 5  Slides 
May 17  Degeneracy, Full Tableau implementation  Chapter 2.4, 3.3 in [BT]  Slides  
May 22  Introduction to the Ellipsoid method  Chapter 8 in [BT]  Sheet 6, Solution 6  Slides 
May 24  The Ellipsoid method  Chapter 8 in [BT]  Slides  
May 29  The Ellipsoid method  Chapter 8 in [BT]  Sheet 7, Solution 7  Slides 
Jun 5  Ellipsoid  Complexity and Equivalence of Optimization/Separation  Chapter 8 in [BT]  Sheet 8, Solution 8  Slides 
Jun 7  Introduction to Interior Point methods  Chapter 9 in [BT]  Slides  
Jun 12  Interior Point methods, central path  Chapter 9 in [BT]  Sheet9, Solution 9  Slides 
Jun 14  Integer Polyhedra  Chapter 3 in [W]  Slides  
Jun 19  Total unimodularity, MinCost flow  Chapter 3.2 in [W]  Sheet10, Solution 10  Slides 
Jun 21  Network flows  Chapter 7 in [BT]  Slides  
Jun 26  Network simplex, negative cost cycle canceling algorithm  Chapter 7.3, 7.4 in [BT], Chapter 3.3 in [W]  Sheet 11, Solution 11  Slides 
Jun 28  Max Flow, Min Cut, Matching  Chapter 7.5 in [BT]  Script  
Jul 3  Approximation algorithms, Matching vs Vertex Cover  Chapter 10.3 in [BT], Chapter 4 in [W]  Sheet 12, Solution 12  Script 
Jul 5  Video lecture on matching  Chapter 8.2 in [MG]  Bonus sheet  
Jul 10  Set cover  Script  
Jul 12  Video lecture on SAT problems  Script  
Jul 17  Max Cut and Semidefinite Programming  Script  
Jul 19  Max Cut and Semidefinite Programming  Script 
Literature
Good textbook on the topic include:
 Integer Programming by Laurence A. Wolsey.
 Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.