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 Bund-Becker |
| Tutorials: | Monday, 10-12, room 024, E1 4 (except on May, 7 and May, 22: room 021, E1 4) Friday, 12-14, 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 re-exam. You may bring one A4 cheat sheet (double-sided, 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ünther-Hotz-Hörsaal Re-Exam: 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 (10-12) 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 NP-hard optimization problems. There will be theoretical and practical exercises.
Policies
This is a 9-credit-point 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 | Fourier-Motzkin 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 | Brute-force 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, Min-Cost 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.