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

Lectures:  Tuesday + Thursday, 14:00  16:00, E1.3 HS003; first lecture on Apr 20 
Teaching Assistant:  Bojana Kodric 
Tutors:  Sören BundBecker, Davis Issac, Pavel Kolev 
Tutorials:  Mondays 1012, E1.4 024, Sören Wednesdays 1214, E1.4 024, Davis Fridays 1214, E1.4 024, Pavel 
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. Final Exam: August 18th ReExam: September 25th

If you want to participate in the course, please register to our mailing list!
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.
Students will also have the chance to gather points by contributing to a wiki. Bonus points will be awarded for contributions to the wiki, i.e., for
 correction of typos
 fixing flaws
 filling gaps
The number of awarded bonus points will be determined in the following way: 10 points per 1k characters, further multiplied with a quality factor between 0 and 1.
Lectures
The slides of all lectures condensed in a handout can be found here.
Date  Topic  Reference  Homework  Notes 

Apr 20  Overview  Sheet 0, Solution 0  Slides  
Apr 25  Integer Programming  Chapter 6 in [W]; Chapter 11.8 in [BT]  Sheet 1, Solution 1  Slides 
Apr 27  Branch and Bound  Chapter 7 in [W] ; Chapter 11.2 in [BT]  Slides  
May 2  Duality  Chapter 4.7 in [BT]  Slides  
May 4  Farkas' Lemma, Strong Duality  Chapters 4.6 and 4.3 in [BT]  Slides  
May 9  FourierMotzkinElimination  Chapter 2.8 in [BT]  Slides  
May 11  Facets, Vertices, Extreme Points, Basic Feasible Solutions  Chapter 2.2 in [BT]  Slides  
May 16  Optimality of Extreme Points, Standard Form  Chapters 2.6 and 2.3 in [BT]  Slides  
May 18  Degeneracy, Basic (Feasible) Directions, Reduced Costs  Chapters 2.4 and 3.1 in [BT]  Slides  
May 23  Optimal Bases, Development of the Simplex Method  Chapters 3.1 and 3.2 in [BT]  Slides  
May 25  Public Holiday  Bonus sheet  
May 30  Simplex  The full tableau implementation  Chapter 3.3 in [BT]  Slides  
Jun 1  Introduction to the Ellipsoid Method  Volume of Polyhedra  Chapter 8 in [BT]  Slides  
Jun 6  The Ellipsoid Method  Chapter 8 in [BT]  Slides  
Jun 8  The Ellipsoid Method  Chapter 8 in [BT]  Slides  
Jun 13  Introduction to the Interior Point Method  Chapter 9 in [BT]  Slides  
Jun 15  Public Holiday  
Jun 20  The Interior Point Method  Chapter 9 in [BT]  Slides  
Jun 22  Integer Optimization, Generalization to Polyhedra  Chapter 3.2 in [W]  Slides  
Jun 27  Unimodular Matrices, Total Unimodularity  Chapters 7.3,7.4 in [BT]  Slides  
Jun 29  Total Unimodular Matrices, Network Flows  Chapters 7.3,7.4 in [BT]; Chapters 3.2, 3.3 in [W]  Slides  
Jul 4  Network Flows  Chapters 7.3,7.4 in [BT]; Chapter 3.3 in [W]  Slides  
Jul 6  Network Flows  Chapters 7.3,7.4 in [BT] ; Chapter 3.3 in [W]  Slides  
Jul 11  MaxFlow MinCut  Chapter 8.2 in [MG]  Slides  
Jul 13  Bipartite Matching  Chapter 8.2 in [MG]  Slides  
Jul 18  Hall's Theorem, Matching Polytopes  Chapter 8.2 in [MG]  Test Exam  Slides 
Jul 20  Matching Polytopes  Chapter 8.2 in [MG]  Slides  
Jul 25  Approximation Algorithms  Chapter 25 in [S]  Slides  
Jul 27  MaxCut and SDP relaxations  Slides 
Literature
Good textbook on the topic include:
 Integer Programming by Laurence A. Wolsey.
 Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.