max planck institut
informatik
informatik
| Lecture time: | Monday 14:15-16:00 / Wednesday 10:15-12:00 |
|---|---|
| Lecture room: | HS003 (E1.3) |
| Lecturers: | Andreas Karrenbauer and Matthias Mnich |
| Textbook: |
Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis |
| Tutorial time & place: |
There are tutorials on:
|
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 NP-hard optimization problems. There will be theoretical and practical exercises.
The slides of the first 6 lectures are condensed in the handout. The condensed chapter about the Ellipsoid method can be found here. Please find the annotations below.
| Date | Topic | Reference | Homework | Lecturer | Notes |
|---|---|---|---|---|---|
| Apr 17 | Overview | Andreas | |||
| Apr 22 | Polyhedra | Exercise Sheet 1 , Solution to Sheet 1 | Andreas | annotated slides | |
| Apr 24 | Extreme Points Vertices, Basic Feasible Solutions | Andreas | annotated slides | ||
| Apr 29 | Polyhedra/Bases in Standard Form | Exercise Sheet 2 , Solution to Sheet 2 | Andreas | annotated slides | |
| May 1 | No lecture (Labour Day) | ||||
| May 6 | Optimality of Vertices, Fourier Motzkin Elimination | Exercise Sheet 3 , file for 4(b), Solution to Sheet 3 | Andreas | annotated slides | |
| May 8 | Simplex | Andreas | annotated slides | ||
| May 13 | Simplex | Exercise Sheet 4 , Solution to Sheet 4 | Andreas | ||
| May 15 | Weak and Strong Duality | Exercise Sheet 5 , Solution to Sheet 5 | Matthias | slides | |
| May 20 | No lecture (Pentecost Monday) | ||||
| May 22 | Complementary Slackness and Dual Simplex | Matthias | slides | ||
| May 27 | Sensitivity Analysis and Assignment Problem | Exercise Sheet 6 , Solution to Sheet 6 | Matthias | slides | |
| May 29 | Network Flow Problems | Matthias | slides | ||
| June 3 | The Network Simplex Method I | Exercise Sheet 7 , Solution to Sheet 7 | Matthias | slides | |
| June 5 | The Network Simplex Method II | Matthias | slides | ||
| June 10 | Negative cost cycle algorithm, Max Flows | Exercise Sheet 8 , Solution to Sheet 8 | Matthias | slides | |
| June 12 | Maximum Flows: Edmonds Karp | Matthias | slides | ||
| June 17 | The Ellipsoid Method | Exercise Sheet 9 , Solution to Sheet 9 | Andreas | ||
| June 19 | The Ellipsoid Method | Andreas | |||
| June 24 | The Ellipsoid Method | Exercise Sheet 10 , Solution to Sheet 10 | Andreas | ||
| June 26 | Equivalence of Optimization and Separation | Andreas | |||
| July 1 | Interior Point Methods | Exercise Sheet 11 , Solution to Sheet 11 | Andreas | ||
| July 3 | Integer Programming | Andreas | |||
| July 8 | Linear Programming for Fixed-Parameter Algorithms | Exercise Sheet 12 , Solution to Sheet 12 | Matthias | Research Paper | |
| July 10 | Linear Programming for Approximation Algorithms | Matthias | Research Paper | ||
| July 15 | tba | Matthias | |||
| July 17 | tba | Matthias | |||
| July 22 | Exam at 2:00 pm, building E2 5, HS I |
| 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. | ||||
|---|---|---|---|---|---|
| Policies: | This is a 9-credit-point class ("Stammvorlesung"). There will be two lectures and one exercise session per week. We will hand out exercises every week 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 may hand in the exercises in teams of two. | ||||
| Exam Information: | Your final grade will be the best of the final exam and the make-up exam.
You may bring an A4 cheat sheet (double-sided, in your own handwriting)
to the exams. Here are the exam dates:
|