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.

DateTopicReferenceHomeworkNotes
Apr 09Overview Exercise 0, Exercise 1Slides
Apr 11Polyhedra and ILPsChapter 6 in [W]; Chapter 11.8 in [BT]Solution 0, Solution 1Slides
Apr 16ILPs and Branch-and-BoundChapter 7 in [W]; Chapter 11.2 in [BT]Exercise 2Slides
Apr 18Branch and Bound, DualityChapter 4.7, 11.2 in [BT]Solution 2Slides
Apr 23Fourier-Motzkin Elimination, Weak DualityChapter 2.8, 4 in [BT]Exercise 3Slides
Apr 25Strong Duality, Complementary SlacknessChapter 4.3 in [BT]Solution 3Slides
Apr 30Vertices, Facets and Extreme PointsChapter 2.3, 2.5, 2.6 in [BT]Exercise 4Slides
May 02Optimality of Extreme Points, A Brute-Force LP algorithmChapter 2.6, 3.1 in [BT]Practical Bonus Sheet, Solution 4Slides
May 07The Simplex MethodChapter 3 in [BT]Exercise 5Slides
May 09Degeneracy, Full Tableau implementationChapter 2.4, 3.3 in [BT]Solution 5Slides
May 14Degenerate Case, Dual SimplexChapter 3.4, 4.5 in [BT]Exercise 6Slides
May 16The Ellipsoid MethodChapter 8 in [BT]Solution 6Slides
May 21The Ellipsoid Method (ctd.)Chapter 8 in [BT]Exercise 7Slides
May 23Equivalence of Optimization/SeparationChapter 8 in [BT]Solution 7Slides
May 28Complexity of Ellipsoid, Introduction to Interior Point MethodsChapter 8,9 in [BT]Exercise 8, Solution 8Slides
Jun 04Interior Point Methods, central pathChapter 9 in [BT]Exercise 9Slides
Jun 06Interior Point Methods (ctd.)Chapter 9 in [BT]Solution 9Slides
Jun 11Integer PolyhedraChapter 3.2 in [W]Exercise 10Slides
Jun 13Total UnimodularityChapter 3.2 in [W]Solution 10Slides
Jun 18Introduction of Network FlowsChapter 7 in [BT]Exercise 11, Solution 11Slides
Jun 25Network Simplex, Negative Cost Cycle CancellingChapter 7.3, 7.4 in [BT], Chapter 3.3 in [W]Exercise 12Slides
Jun 27Negative Cost Cycle Cancelling (ctd.)Chapter 7.3, 7.4 in [BT]Solution 12Slides
Jul 02Max Flow, Min Cut, MatchingChapter 7.5 in [BT]Exercise 13Slides
Jul 04Matching, Approximation AlgorithmsChapter 10.3 in [BT], Chapter 4 in [W]Solution 13Slides
Jul 09Set cover, Max Cut, Quadratic Programming Test examSlides
Jul 11Semidefinite Programming  Slides
Jul 16Current research topics, Outlook   

Literature

Good textbook on the topic include: