max planck institut
informatik

# Optimization (SoSe 2011)

## Basic Information

Lecture time: Tuesday 14:00-16:00 / Thursday 14:00-16:00 HS 001, Campus E 13 Khaled Elbassioni and Anke van Zuylen "Introduction to Linear Optimization" by Bertsimas and Tsitsiklis Monday 16:00-18:00, room 024 E 14. (Exception: the tutorial on Monday May 23 will be held in Room 323 of Building E 1 7) Thursday 9:00-10:00, room 024 E 14. Fahimeh Ramezani, Philipp Klodt

### Description

This course provides an introduction to fundamental concepts and algorithmic methods for solving linear and integer linear programs.

### Announcements

The Makeup exam will be on September 28, from 14-16. Location: Campus E1 4, Room 022. It is a comprehensive written exam. You are allowed to bring a small cheat sheet. The cheat sheet must be no larger than half of an A4 (one sided) and must be hand written (and it has to be written by you, not by a friend with tiny handwriting).

The final exam on Thursday July 21 will be held in our regular lecture room HS 001, E 13. The exam will start at 14:00.
You are allowed to bring a small cheat sheet. The cheat sheet must be no larger than half of an A4 (one sided) and must be hand written (and it has to be written by you, not by a friend with tiny handwriting).

## Lectures

Date Topic Reference Homework Lecturer
Apr 14 Introduction to linear optimization Ch. 1 Anke
Apr 19 What does the feasible region of an LP look like?
Polyhedra and convex sets. Vertices, extreme points and basic feasible solutions.
Sec. 2.1, 2.2 HW 1 Anke
Apr 21 Representation of bounded polyhedra, polyhedra in standard form. Sec. 2.7, 2.3 Anke
Apr 26 Polyhedra in standard form, developing the simplex method. Sec. 2.3, example 3.1,LN 4 Anke
Apr 28 An iteration of the simplex method. Sec. 3.1-3.2,LN 5 HW 2 Anke
May 3 Implementation of the Simplex Method - Revised Simplex and Tableaus. Sec. 3.3,LN 6 Anke
May 5 Initialization, Anti-Cycling and Number of Iterations. Sec. 3.4, 3.5, 3.7,LN 7 Anke
May 10 Linear Programming Duality. Sec. 4.1-4.3,LN 8 HW 3 Anke
May 12 Duality, Shortest Path, Complementary Slackness. Sec. 4.1-4.3,LN 9 Anke
May 17 Dual Simplex Method and Sensitivity Analysis. Sec. 4.4-4.5, 5.1,LN 10 HW 4 Anke
May 19 The Assignment Problem and Primal-Dual Algorithms. LN 11 Anke
May 24 The network flow problem and the network simplex algorithm Sec. 7.1-7.3 Khaled
May 26 The network simplex algorithm and the negative cost cycle algorithm Sec. 7.3,7.4 HW 5 Khaled
June 7 The negative cost cycle algorithm and the max flow problem Sec. 7.4,7.5 Khaled
June 9 The max flow min cut theorem Sec. 7.5 HW 5: new version Khaled
June 14 The Ellipsoid method Ch. 8 Khaled
June 16 The Ellipsoid method Ch. 8 HW 6 Khaled
June 21 The Ellipsoid method, Introducion to Interior point methods Sec. 8.5, 9.1 Khaled
June 28 Affine scaling algorithm, potential reduction algorithm Sec. 9.1, 9.3 Khaled
June 30 The potential reduction algorithm Sec. 9.3 HW 7 Khaled
July 5 Integer programming formulations Ch. 10 Khaled
July 7 Integer prorgamming methods Sec. 11.1, 11.2, 11.4 HW 8 Khaled
July 12,14 Dealing with NP-hardness LN23 Anke
July 14 Approximation Algorithms for metric TSP Mömke-Svensson paper Anke
July 7 Single machine scheduling Sec. 12.5 Khaled
 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, Grundzüge von Algorithmen und Datenstrukturen. This is a 9-credit-point class. There will be two lectures and one exercise session per week. Your final grade will be based on your performance in the midterm and final exams---each is worth half of the final grade. You need to get at least 50% of the exercise credit to be able to take the final exam. We will have the exams in our usual classroom (HS 001). There will be a make-up exam; this exam is comprehensive. Your final grade will be the best of the average of your midterm and final exams scores, and the make-up exam. Here are the dates of the exams: Tuesday 31 May at 14:00-16:00 Thursday 21 July at 14:00-16:00 Wednesday 28 September at 14:00-16:00

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)