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:  Pavel Kolev, Sarah Mameche, Kevin Morio 
Tutorials:  Monday, 12:0014:00, room 023 Wednesday, 14:0016:00, room 024 (except 17.04.) Friday, 10:0012:00, room 023 (except 31.05.) 
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 18th, 13:30  16:30, HS 2 in E1.3 ReExam: TBA

Announcements
 If you want to participate in the course, please register to our mailing list!
 The assignment to the tutorials can be found here.
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. We also provide the supplement of last year's lecture for reference here.
Date  Topic  Reference  Homework  Notes 

Apr 09  Overview  Exercise 0, Exercise 1  Slides  
Apr 11  Polyhedra and ILPs  Chapter 6 in [W]; Chapter 11.8 in [BT]  Solution 0, Solution 1  Slides 
Apr 16  ILPs and BranchandBound  Chapter 7 in [W]; Chapter 11.2 in [BT]  Exercise 2  Slides 
Apr 18  Branch and Bound, Duality  Chapter 4.7, 11.2 in [BT]  Solution 2  Slides 
Apr 23  FourierMotzkin Elimination, Weak Duality  Chapter 2.8, 4 in [BT]  Exercise 3  Slides 
Apr 25  Strong Duality, Complementary Slackness  Chapter 4.3 in [BT]  Solution 3  Slides 
Apr 30  Vertices, Facets and Extreme Points  Chapter 2.3, 2.5, 2.6 in [BT]  Exercise 4  Slides 
May 02  Optimality of Extreme Points, A BruteForce LP algorithm  Chapter 2.6, 3.1 in [BT]  Practical Bonus Sheet, Solution 4  Slides 
May 07  The Simplex Method  Chapter 3 in [BT]  Exercise 5  Slides 
May 09  Degeneracy, Full Tableau implementation  Chapter 2.4, 3.3 in [BT]  Solution 5  Slides 
May 14  Degenerate Case, Dual Simplex  Chapter 3.4, 4.5 in [BT]  Exercise 6  Slides 
May 16  The Ellipsoid Method  Chapter 8 in [BT]  Solution 6  Slides 
May 21  The Ellipsoid Method (ctd.)  Chapter 8 in [BT]  Exercise 7  Slides 
May 23  Equivalence of Optimization/Separation  Chapter 8 in [BT]  Solution 7  Slides 
May 28  Complexity of Ellipsoid, Introduction to Interior Point Methods  Chapter 8,9 in [BT]  Exercise 8, Solution 8  Slides 
Jun 04  Interior Point Methods, central path  Chapter 9 in [BT]  Exercise 9  Slides 
Jun 06  Interior Point Methods (ctd.)  Chapter 9 in [BT]  Solution 9  Slides 
Jun 11  Integer Polyhedra  Chapter 3.2 in [W]  Exercise 10  Slides 
Jun 13  Total Unimodularity  Chapter 3.2 in [W]  Solution 10  Slides 
Jun 18  Introduction of Network Flows  Chapter 7 in [BT]  Exercise 11, Solution 11  Slides 
Jun 25  Network Simplex, Negative Cost Cycle Cancelling  Chapter 7.3, 7.4 in [BT], Chapter 3.3 in [W]  Exercise 12  Slides 
Jun 27  Negative Cost Cycle Cancelling (ctd.)  Chapter 7.3, 7.4 in [BT]  Solution 12  Slides 
Jul 02  Max Flow, Min Cut, Matching  Chapter 7.5 in [BT]  Exercise 13  Slides 
Jul 04  Matching, Approximation Algorithms  Chapter 10.3 in [BT], Chapter 4 in [W]  Solution 13  Slides 
Jul 09  Set cover, Max Cut, Quadratic Programming  Test exam  Slides  
Jul 11  Semidefinite Programming  Slides  
Jul 16  Current research topics, Outlook 
Literature
Good textbook on the topic include:
 Integer Programming by Laurence A. Wolsey.
 Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.