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)] or 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

Announcements

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

Description

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

Lectures

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	Reto
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	Reto
May 8	Simplex method: feasible directions, moving from bfs to bfs, optimality conditions	Sec. 3.1, 3.2	HW 3, Sol 3	Reto
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	Reto
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	Reto
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	Rob
June 7	No lecture (Corpus Christi)
June 12	The network simplex method	7.3	HW 8 , Sol 8	Rob
June 14	The network simplex method II	7.3		Rob
June 19	Negative cost cycle algorithm	7.4	HW 9 , Sol 9	Rob
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	Rob
July 5	Potential function algorithm			Rob
July 10	Integer programming formulations	10.1	HW 12 , Sol 12	Rob
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	Reto
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