Optimization
Core Course, 4+2
Postponed by 4 weeks!
Please note that on 11.3., the entire Saarland university has postponed the start of the semester by 4 weeks. This also affects this course. We will update the information below as soon as we can.
Basic Information
Lecturer:  Andreas Karrenbauer 

Lectures:  Wednesday + Thursday, 14:00  16:00, E1.4 room 024; 
Teaching Assistant:  TBA 
Tutors:  TBA 
Tutorials:  TBA

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: TBA ReExam: TBA

Announcements
 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.
Lectures
Literature
Good textbook on the topic include:
 Integer Programming by Laurence A. Wolsey.
 Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis.