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).
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.
Some basic knowledge of algorithms, graph theory and linear algebra is required to follow the course. Students who are not familiar with these subjects may consult the chapter "Mathematical Background" (Appendix VIII) in the book [CLRS09] (see reference list below). The material presented in this chapter constitutes a good basis and actually covers much more than we will need in the course.
The course consists of 13 lectures and takes place every Monday, 13:15-15:00. The lectures will be given at Utrecht University.
UPDATE (29/9): Please check below for the new room schedule:
Prof. Dr. Guido Schäfer
Email: g dot schaefer at cwi dot nl
Dr. Cristobal Guzman (last three lectures)
Email: c dot a dot guzman at cwi dot nl
Centrum Wiskunde & Informatica
Networks and Optimization Group
Science Park 123, 1098 XG Amsterdam
Office hours by appointment
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 grade 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 graded assignments. The final grade is given as an integer from 1 through 10.
Both the exam and the re-exam will be written examinations. Students who passed the exam are free to participate in the re-exam (to improve their final grade). Note however that in this case the grade of the re-exam counts for the final grade (not the maximum grade achieved for the exam and re-exam).
Assignments will be issued on a weekly basis; solutions will be provided one week later. We will issue a total of 11 assignments:
Among these 11 assignments you are supposed to hand in your solutions for three of them, namely for Assignment 3, Assignment 7 and Assignment 10. These assignments will be graded and their average grade will constitute 40% of the final grade. Please note that you are required to obtain an average grade of at least 5.5 on these graded assignments in order to be able to participate in the exam (and re-exam).
We advise you to also work intensively on the assignments that are not graded. The final exam will be similar in flavor to the assignments and it needs some exercising to get familiar with the used concepts, proof techniques, formalisms, etc. Also note that all material covered in the assignments will be relevant for the final exam.
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 general, all your algorithms should be efficient (run in polynomial time).
We encourage you to work in groups of size 2 to solve and hand-in the assignments.
The assignments have to be handed in in paper form or by email before the lecture (i.e., on due date, before 13:15). Please make sure that hand-written solutions are clearly legible. The assignments will be corrected by Pieter Kleer (email: kleer at cwi dot nl). If you want to hand-in your solutions by email, then please send them directly to Pieter (at the latest on due date, before 13:15). Please ensure that scans of hand-written solutions have a sufficiently high resolution for printing.
UPDATE: We would like everybody to hand in Assignment 10 electronically!
Pieter will then grade it and provide feedback electronically (annotated PDF). Even if you prefer a hand-written solution, please scan (or photograph) these and hand them in by email. Please generate a single PDF file of your solutions.
In case you feel that you should have been awarded more points for your solution, please send a correction request to Pieter: This request should consist of a scan of the relevant part of your answer and explain why you think that you deserve more points. Pieter will then reconsider the marking in light of your remarks and provide feedback.
If such a correction request is submitted more than two weeks after the return date of the graded assignments, Pieter will only check whether he overlooked something in your solution, but there is no room for further discussion.
In general, correction requests (for any of the three hand-in assignments) can be sent in until January 4, 2016.
All material that is covered in the Lecture Notes (including the separate part on max-cut) and the assignments will be relevant for the exam. The only exception is Chapter 8 "Integrality of Polyhedra" which will not be relevant. In addition, material that you are supposed to learn by yourself through reading exercises will be relevant as well.
Material you may use during the exam: Only printouts of the Lecture Notes (files Lecture-Notes.pdf and Lecture-Notes-Max-Cut.pdf) and the assignments incl. solutions (files Assignment{1-11}-Sol.pdf) are allowed to be used during the exam. The Lecture Notes may contain annotations that you made during the lectures. NO additional material is permitted. All electronic equipment must be switched off.
Both the exam and the re-exam will be written examinations.
The exams are scheduled as stated below.
| Date/Time: | Monday, January 11, 2016, 10:00-13:00 |
| Location: | Utrecht University, EDU Alfazaal |
The re-exam is scheduled on:
| Date/Time: | Monday, February 1, 2016, 10:00-13:00 |
| Location: | Utrecht University, EDU Alfazaal |
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 |
The online material of the course can be found here (password protected). All assignments, slides and the current version of the Lecture Notes of the course can be found there.
Note: The 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).