max planck institut
informatik

# Optimization (SoSe 2013)

## Basic Information

Lecture time: Monday 14:15-16:00 / Wednesday 10:15-12:00 HS003 (E1.3) Andreas Karrenbauer and Matthias Mnich Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis There are tutorials on: Tuesdays 4:00 PM in Building E 1.4 Room 023 with Pavel Kolev Thursdays 4:00 PM in Building E 1.4 Room 022 with Ruben Becker Fridays 4:00 PM in Building E 1.4 Room 023 (except on July, 5th, where the tutorial takes place in Building E 1.7 Seminar Room 010 (cluster building) at 2:00 PM) with Philipp Müller

### Announcements

• The exam on July 22 will take place in building E2 5, HS I, starting at 14:00
• Every participant shall register to the mailing list! This is non-binding and does not replace your official registration according to your study rules.

### 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.

## Lectures

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:
Final Exam: July 22, 2:00 pm, written exam (2 hours), building E2 5, HS I September 30, 2pm, building E2 2, Günter-Hotz-Hörsaal

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)