Announcements:

Course Description:

simplex

Discrete Optimization is about the problem of finding a best solution among a typically very large (but discrete) set of feasible solutions. A notorious example is the traveling salesman problem, where we are asked to find a shortest tour among all tours that visit every node of a given graph exactly once. Yet another example is linear programming, which can be interpreted as the problem of finding a best among a finite number of vertices of a polyhedron. The course introduces some of the most relevant problems from the area, as well as algorithms to solve them.

The course content depends a bit on the background of the participants. The following are potential topics:

The course accounts for 6 credit points. Besides the material that we cover in class, we will also ask you to study some material on your own and to solve take-home assignments.

This course is part of the Dutch Master's Degree Programme in Mathematics (Mastermath) and the Dutch Network on the Mathematics of Operations Research (LNMB).

Aim and Prerequisites:

The aim of the course is to provide a solid foundation in Discrete Optimization. A particular focus will be given to the design and analysis of algorithms and to computational complexity. Knowledge of linear algebra and graph theory is advantageous.

Time and Location:

The course consists of 12 lectures and takes place every Monday, 13:15-15:00. The lectures will be given at Utrecht University, almost always in room MIN208 (Minnaert building) with the following exceptions:

Lecturer:

Prof. Dr. Guido Schäfer
Email: g dot schaefer at cwi dot nl

Office hours by appointment

Office at CWI:

Centrum Wiskunde & Informatica
Networks and Optimization Group
Science Park 123, 1098 XG Amsterdam
Room: M235

Assessment:

The final grade of the course depends on two parts: assignments (40%) and exam (60%). In order to pass the course you will need to achieve an average score of at least 5.5, both in the assignments and the exam. The average is taken with respect to the total number of points over all assignments.

Assignments:

Assignments will be issued on a weekly basis. The assignments have to be handed in at the beginning of the next lecture or by email (on due date, before 13:15).

PLEASE(!) WORK IN GROUPS OF 2-3 STUDENTS TO SOLVE AND HAND IN THE ASSIGNMENTS. You may use the list of participants (with email addresses) to find potential collaborators, or send us a message and we will match you.

The assignments will be corrected by Mona Rahn and Irving van Heuven van Staereling (email: i dot i dot van dot heuvenvanstaereling at vu dot nl). If you want to hand-in your solutions by email, then please send them directly to Irving (at the latest on due date, before 13:15). Please ensure that scans of hand-written solutions have a sufficiently high resolution for printing.

In general, please provide formal proofs to your answers. If you are asked to give/derive/develop an algorithm, then this also involves proving its correctness.

In case you feel that you should have been awarded more points for your solution, please send a scan of the relevant part of your answer to Mona or Irving and explain why you think that you deserve more points. Mona and Irving will then reconsider their marking in light of your remarks.

Exam:

All the material that we cover in the Lecture Notes and the assignments will be relevant for the exam. In addition, material that you are supposed to learn by yourself through reading exercises will be relevant as well. Note: Only print outs of Lecture Notes and the assignments (incl. solutions) are allowed to be used during the exam. NO additional material will be permitted. The Lecture Notes may contain some annotations that you made during the lectures. For the assignments, you are allowed to bring a print out of the assignments with solutions; you are not allowed to bring the solutions that you handed in.

Both the exam and the re-exam will be written examinations.

The exam is scheduled on:

Date/Time: Monday, January 6, 2014, 13:30-16:30
Location: Educatorium, room Gamma

The re-exam is scheduled on:

Date/Time: Monday, January 27, 2014, 14:00-17:00
Location: Buys Ballot Building, room BBL001

References and Links:

We will use selected chapters from several books listed below.

[AMO93] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows, Prentice Hall, 1993. ISBN 0-13-617-549.
[CCPS98] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, 1998. ISBN 0-471-55894-X
[CLRS01] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001. ISBN10 0262531968
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009. ISBN10 0262531968
[KV08] B. Korte and J. Vygen, Combinatorial Optimization - Theory and Algorithms, 4th ed., Springer, 2008. ISBN10 3-540-25684-9.
[PS82] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization; Algorithms and Complexity, Prentice-Hall, 1982. ISBN 0-13-152462-3
[Tar83] R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1983. ISBN 0-89871-187-8
[Vaz01] V. V. Vazirani, Approximation Algorithms, Springer, 2001

Course Material:

The online material of the course can be found here (password protected).

Here is the current version of the Lecture Notes.

Note: These lecture notes will be updated as we proceed. Make sure that you always have the latest version (see "document last modified" date in upper right corner of the pdf file).

Lecture 1 (Sep. 23)

Lecture 2 (Sep. 30)

Lecture 3 (Oct. 7)

Lecture 4 (Oct. 14)

Lecture 5 (Oct. 21)

Lecture 6 (Oct. 28)

Lecture 7 (Nov. 4)

Lecture 8 (Nov. 11)

Lecture 9 (Nov. 18)

Lecture 10 (Nov. 25)

Lecture 11 (Dec. 2)

Lecture 12 (Dec. 9)