max planck institut
mpii logo Minerva of the Max Planck Society

Optimization (SoSe 2012)

Basic Information

Lecture time: Tuesday 10:15-12:00 / Thursday 12:15-14:00
Lecture room: HS003 (E1.3) [execpt on May 29, June 26, and July 26., when we are in room 024 (E1.4)]
Lecturers: Reto Spöhel and Rob van Stee
Textbooks: Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis (Main reference)
Combinatorial Optimization: Algorithms and Complexity by Christos H. Papadimitriou and Kenneth Steiglitz (Secondary reference)
For the first part of the course, we also recommend Anke van Zuylen's notes from last year. (There are a few minor typos.)
Tutorial time & place: Wednesday 10:15-12:00, with Ruben, room 001 (E1.7, cluster building) [except on June 20, when we are in room 008 (E1.7)]
Wednesday 14:15-16:00, with Karl, room 023 (E1.4) [except on May 2, when we are in room 022 (E1.4) and on May 16, when we are in room 019 (E1.4)]
The tutorials start on May 2
Tutors: Karl Bringmann, Ruben Becker


  • If you want to take part in the re-exam, please register till September 23 by sending a short mail to Karl.


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


Date Topic Reference Homework Lecturer Notes
Apr 17 Introduction to linear optimization Sec. 1.2, 1.4, Slides (PPTX, PDF) Reto
Apr 19 Matrix notation; general form and standard form of an LP Sec. 1.1, 1.5, Slides (PPTX, PDF) Reto
Apr 24 Polyhedra and convex sets; vertices, extreme points and basic feasible solutions Sec. 2.1, 2.2 HW 1,
Sol 1
Apr 26 Vertices, extreme points and bfs's; degeneracy; linear independency assumption for LP's in standard form Sec. 2.2 - 2.4 Reto
May 1 No lecture (Labour Day)
May 3 Basic (feasible) solutions of LP's in standard form; basic and non-basic variables etc. Sec. 2.3, 2.4 HW 2,
Sol 2
May 8 Simplex method: feasible directions, moving from bfs to bfs, optimality conditions Sec. 3.1, 3.2 HW 3,
Sol 3
May 10 Simplex method: anticycling (Bland's rule), finding an initial bfs Sec. 3.4, 3.5 Reto
May 15 Simplex method: revised simplex method, full tableau implementation Sec. 3.3 HW 4 ,
Sol 4
May 17 No lecture (Ascension Day)
May 22 Simplex method: number of iterations, Hirsch conjecture etc.; introduction to duality Sec 3.7; 4.1 - 4.2 HW 5 ,
Sol 5
May 24 Weak and strong duality Sec. 4.3 Reto
May 29 Complementary slackness, dual simplex Sec. 4.3 - 4.5 HW 6 ,
Sol 6
Rob lecture in room 024 (E1.4)
May 31 Sensitivity analysis Sec. 5.1 Rob
June 5 Network flow problems Sec. 7.1 - 7.2 HW 7 ,
Sol 7
June 7 No lecture (Corpus Christi)
June 12 The network simplex method 7.3 HW 8 ,
Sol 8
June 14 The network simplex method II 7.3 Rob
June 19 Negative cost cycle algorithm 7.4 HW 9 ,
Sol 9
June 21 Maximum flow and the ellipsoid method 7.5, 8.1 Rob
June 26 The ellipsoid method 8.2 (LN KM), LN HW 10 ,
Sol 10
Rob lecture in room 029 (E1.5)
June 28 The ellipsoid method 8.3 - 8.5 Rob
July 3 Affine scaling algorithm 9.1 HW 11 ,
Sol 11
July 5 Potential function algorithm Rob
July 10 Integer programming formulations 10.1 HW 12 ,
Sol 12
July 12 Integer programming methods 11 Rob
July 17 Integer programming duality in action: The Held-Karp lower bound 11.4, in particular Example 11.10 HW 13 ,
Sol 13
July 19 Held-Karp continued; integrality gap; Christofides' 3/2-appproximation for metric TSP 11.4, Wikipedia Reto
July 24 Research Talk: Polynomial-time approximation schemes for NP-hard geometric problems Slides (PPTX, PDF); Paper Reto
July 26 Exam in building E2.2, 16:00
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 (single-sided, in your own handwriting) to the exams. Here are the exam dates:
Final Exam: 26.07. 16:00, E2.2, written exam (2 hours)
Make-up Exam: 27.09. 14:00, room 023 (E1.4), written exam (2 hours)

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)