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

The first sample solution can be found below. Thanks to all contributors!
From now on the lecture will take place in room HS003 (E1.3). Note the exceptions that can be found in the list below.
The tutorial assignment can be found here.
To register for the course please send an email to Karl containing your name and matriculation number and indicating the tutorials that you may attend.

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	Reto
May 17	No lecture (Ascension Day)
May 22				Reto
May 24				Reto
May 29				Rob	lecture in room 024 (E1.4)
May 31				Rob
June 5				Rob
June 7	No lecture (Corpus Christi)
June 12				Rob
June 14				Rob
June 19				Rob
June 21				Rob
June 26				Rob	lecture in room 024 (E1.4)
June 28				Rob
July 3				Rob
July 5				Rob
July 10				Rob
July 12				Rob
July 17				Reto
July 19				Reto
July 24				Rob
July 26					lecture in room 024 (E1.4)

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. Here are the dates of the exams:

Final Exam:	26.07. 16:00, E2.2, written exam
Make-up Exam:	27.09. 14:00, room 023 (E1.4), written exam

More Courses of the Algorithms and Complexity Group