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 Bund-Becker, Davis Issac, Pavel Kolev |
| Tutorials: | Mondays 10-12, E1.4 024, Sören Wednesdays 12-14, E1.4 024, Davis Fridays 12-14, 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 re-exam. You may bring one A4 cheat sheet (double-sided, in your own handwriting) to the exams. Final Exam: August 18th, 13:15 at Günter-Hotz Lecture Hall Re-Exam: September 25th, 13:15
|
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 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.
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 | Fourier-Motzkin-Elimination | 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 | Max-Flow Min-Cut | 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 | Max-Cut 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.