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:00-14:00, room 023 Wednesday, 14:00-16:00, room 024 (except 17.04.) Friday, 10:00-12: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 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 18th, 13:30 - 16:30, HS 2 in E1.3 Re-Exam: September 30th, 13:30 - 16:30, Günther-Hotz-Hörsaal
|
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 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. 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 Branch-and-Bound | 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 | Fourier-Motzkin 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 Brute-Force 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.