Optimization, Spring 2010
Lecturers
Kristoffer Arnsfelt Hansen and
Peter Bro Miltersen.
Time and Place
 Wednesdays, 14.1516, Lille Auditorium, Aabogade 15.
 Fridays, 12.1513, Lille Auditorium, Aabogade 15.
About the course
The course consists of three hours of lectures and and three hours
of exercise classes each week, throughout the third quarter (first
half of spring semester). The exam is a graded three hour written exam,
Each student must hand in satisfactory
solutions to three compulsory assignments in order to take the
exam. They should be completed individually (in Danish or English), but
disucssions on the assignments are allowed and encouraged.
The solutions should be given to the teaching assistant in person
at specific exercise classes. If you passed the compulsory program
in the course of 20052008, it can be transferred to this course,
but please send me an email to Peter Bro Miltersen requesting
such a transfer as
early as possible and before March 1. Please let the subject
header of the email be "dOpt: Transfer".
Tutorials
Tutorials will start the first week of the semester (Jan 25).
The classes can be found here.
The Monday class is run by Rasmus IbsenJensen (rij@cs.au.dk).
The Tuesday class is directed by Rocio Santillan (rocio@cs.au.dk).
The Wednesday class is commanded by Morten Schaumburg (u033306@cs.au.dk).
You can switch classes if and only if you can find somebody to switch
with.
Compulsory assignments
 Compulsory Assignment 1, hand in at the third tutorial: Solve Problem 2 of the exam of August
2008. There is a misprint in the statement of the problem. In case
of a tie, both teams get one point.
 Compulsory Assignment 2, hand in at the fifth tutorial: Solve Problem 1 of the exam of August
2008 (Originally, by an unfortunate error, the assignment was stated to be Problem 1 of the exam of March 2008. So, if you already prepared or started to prepare the solution to this problem, it is okay to hand this in instead.
But Problem 1 of August 2008 makes better training.)
 Compulsory Assignemnt 3, hand in at seventh tutorial: Solve
Problem 3 of the exam of August
2008.
Previous exams

Exam, March
2005. Correction to Question 15: The linear program should have
optimal
solution value 0 if and only if j is not exploitable.

Exam, August
2005
 Exam, March
2006.

Exam, August
2006
 Exam, March
2007 (Correction: in the second problem, all balances should be negated)
 Exam, August
2007 (Correction: in the second problem, all balances should be negated)
 Exam, March
2008.

Exam, August
2008. Correction to Problem 2: In case of a tie, both teams get
one point.
 Exam, March
2009.

Exam, August
2009
Literature
Lectures
 Wednesday, Jan. 27. The max flow problem, a gentle reminder.
Read: Cormen et al, pp. 643668. Powerpoint, slides
as pdf.
 Friday, Jan. 29. Modeling using the max flow formalism.
The rest of Cormen et al. Also, Ahuja et al, Application 6.2, 6.4,
6.5. Powerpoint, slides as pdf.
 Wednesday, Feb. 3. The min cost flow problem. Read: The virtual
handout of the same name. Also, Ahuja et al, Application 9.1, 6.6
(which we modelled as a min cost flow problem, rather than a max flow
problem) and 9.4.
Powerpoint,
Slides as pdf.
 Friday, Feb. 5. Last words on min cost flow (material and slides
as for Feb 3).
 Wednesday, Feb. 10. Guest lecturer: Thomas Dueholm Hansen.
Linear Programming. Chvatal, Chapter 1,2. Slides: Del A, Del B, Del C.
 Friday, Feb. 12. Guest lecturer: Thomas Dueholm Hansen.
Linear Programming. Chvatal, Chapter 3.
 Wednesday, Feb. 17. Linear Programming. Chvatal, Chapter 4.
Slides: Slides.
 Friday, Feb. 19. Linear Programming. Chvatal, Chapter 4.
Slides: Slides.
 Wednesday, Feb. 24. Matrix Games. Chvatal, Chapter 15. Slides
 Friday, Feb. 26. Mixed Integer Linear Programming.
Read: Virtual handout of the same name. pdf,
 Wednesday, March 3. Integer Linear Programming. Virtual handout
and Papadimitriou and Steiglitz. Powerpoint,
pdf, More pdf.
.
 Friday, March 5. Integer Linear Programming.
pdf
 Wednesday, March 10. The ellipsoid algorithm, interior point
algorithms, branch and cut. Slides: pdf.
 Friday, March 12. We talk about the exam.