Master Course: Discrete Optimization (Fall 2011)

 

Announcements:

  1. •Feb 3, 2012: Results and solutions of the re-exam are online.

  2. •Jan 24, 2012: The re-exam will take place on Jan. 30, 2012, 15:00-18:00 in the Buys Ballot Laboratorium, room 061, Utrecht University (see location via google maps and this website). Note: Only the Lecture Notes are allowed to be used during the exam; NO additional material will be allowed. The material contained in the Lecture Notes and Assignments 1-5 are relevant for the exam.

  3. •Jan 16, 2012: Results and solutions of the exam are online.

  4. •Jan 10, 2012: The re-exam will take place on Jan. 30, 2012, 15:00-18:00 at Utrecht University. More details will be announced shortly.

  5. •Jan 4, 2012: Lecture Notes have been updated (changes are documented on page 2 of the Lecture Notes).

  6. •Dec 20, 2011: The written exam will take place on Jan. 9, 2012, 15:00-18:00 in the Educatorium, Thetazaal (θ), Utrecht University (see location via google maps). Note: Only the Lecture Notes are allowed to be used during the exam; NO additional material will be allowed. The material contained in the Lecture Notes and Assignments 1-5 are relevant for the exam.

  7. •Dec 20, 2011: Lecture Notes have been updated. (I guess most of you will have printed the Lecture Notes of December 6, 2011. I will therefore keep track of all changes that I made since then on page 2 of the Lecture Notes.)

  8. •Dec 16, 2011: Final scores of the assignments are online.

  9. •Dec 16, 2011: Solutions for Assignment 5 and the grading scheme are available online.

  10. •Dec 6, 2011: Your feedback for the course is very welcome: Please fill in the Mastermath evaluation form and hand it in!

  11. •Dec 6, 2011: We have an extra session on Dec. 19, 13:15-15:00, in MIN 208 to discuss whatever you would like to discuss. Please send me an email if you would like me to discuss a specific topic, exercise, etc.

  12. •Dec 5, 2011: Lecture Notes have been updated. The slides are available online.

  13. •Nov 30, 2011: Solutions for Assignment 4 and the grading scheme are available online.

  14. •Nov 22, 2011: We decided to have an extra session on Dec. 19, 13:15-15:00, in MIN 208.

  15. •Nov 22, 2011: Lecture Notes have been updated. The slides are available online.

  16. •Nov 22, 2011: Assignment 5 has been issued and is due Dec. 5.

  17. •Nov 18, 2011: Solutions for Assignment 3 and the grading scheme are available online.

  18. •Nov 11, 2011: If there is sufficient interest, we could arrange an extra “tutorial session” to discuss whatever you would like to discuss on Dec. 19. We will decide next time (Nov. 21) whether this session is going to happen or not.

  19. •Nov 11, 2011: Sample exam (from last year’s course) is available; see “Exam” section below.

  20. •Nov 8, 2011: Lecture Notes have been updated. The slides are available online.

  21. •Nov 8, 2011: Assignment 4 has been issued and is due Nov. 21.

  22. •Nov 2, 2011: Solutions for Assignment 2 and the grading scheme are available online.

  23. •Oct 28, 2011: Problems 6 and 7 of Assignment 3 are about matchings which we will cover next time. Please consider these problems as optional. They will become part of Assignment 4 and you can either solve them for Assignment 3 or later for Assignment 4.

  24. •Oct 25, 2011: Lecture notes have been updated (note also the short section on linear programming in the Preliminaries). The slides are also available online.

  25. •Oct 25, 2011: We decided to give 12 extra points to everyone who handed in Assignment 1 because of the misunderstanding that deriving an algorithm should always come with a correctness proof.

  26. •Oct 25, 2011: The deadline for handing in Assignment 2 has been extended to Oct. 25, 2011 (23:59). Please make sure that you always provide correctness proofs of your algorithms. You may hand in your assignment electronically (scan, photograph as long as it is readable) by sending them to Bart (email: bdekeijzer at gmail dot com).

  27. •Oct 25, 2011: Assignment 3 has been issued and is due Nov. 7.

  28. •Oct 21, 2011: Solutions for Assignment 1 and the grading scheme are available online.

  29. •Oct 11, 2011: Lecture notes have been updated. The slides of yesterday’s lectures are also available online.

  30. •Oct 11, 2011: Assignment 2 has been issued in class and is due Oct. 24.

  31. •Sep 26, 2011: Assignment 1 has been issued in class today and is due Oct. 10. PLEASE(!) work in groups of 2-3 students to solve and hand-in the assignment. You may use the list of participants (with email addresses) to find potential collaborators (see online material).

  32. •Sep 26, 2011: Lecture notes have been updated.

  33. •Sep 19, 2011: Note: The next lecture takes place next Monday (Sep. 26), 11:00-12:45, Aard Klein (see “Lecture dates” below).

  34. •Sep 19, 2011: If you like to “play” with the red and blue rule presented today, then try to do Homework 1 and 2 (both optional) stated below.

  35. •Sep 19, 2011: Lecture notes of today’s class (and parts of next class) are online (see “Course Material” below).

  36. •Sep 15, 2011: Lecture notes will be provided throughout the course. In addition, we will use selected chapters from the books mentioned below.

  37. •Aug 8, 2011: Course starts on September 19, 2011: 13:15-15:00 (MIN 211).


Course Description:

Discrete Optimization is about the problem of finding a best solution among a set of feasible solutions. The set of feasible solutions might be astronomically large but is assumed to be discrete (finite or countably infinite), which also constitutes the major difference to Continuous Optimization. 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 following topics will be treated

  1. •Introduction to Algorithms & Analysis

  2. •Minimum Spanning Trees & Matroids

  3. •Shortest Path Algorithms

  4. •Maximum Flows & Minimum Cuts

  5. •Minimum Cost Flows

  6. •P, NP, coNP, NP-completeness

  7. •Integer Linear Programming & Total Unimodularity

  8. •Approximation Algorithms

  9. •Primal-Dual Algorithms

  10. •Inapproximability & Approximation Schemes


The course is organized by the Dutch Network on the Mathematics of Operations Research (LNMB) and is part of the Dutch Master’s Degree Programme in Mathematics (Mastermath). The course counts 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 5 take-home assignments.


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 (2h + 5x4h + 2h) and takes place every second Monday (alternating with Continuous Optimization). The lectures will be given at Utrecht University. A detailed schedule (including room information) is given below.


Lecture dates:

  1. 1.September 19, 2011, 13:15-15:00 (MIN 211)

  2. 2.September 26, 2011, 11:00-12:45 (Aard Klein), 13:15-15:00 (MIN 211)

  3. 3.October 10, 2011, 11:00-12:45 (Aard Klein), 13:15-15:00 (MIN 211)

  4. 4.October 24, 2011, 11:00-12:45 (Aard Klein), 13:15-15:00 (MIN 211)

  5. 5.November 7, 2011, 11:00-12:45 (MIN 211), 13:15-15:00 (MIN 211)

  6. 6.November 21, 2011, 11:00-12:45 (MIN 211), 13:15-15:00 (MIN 211)

  7. 7.December 5, 2011, 13:15-15:00 (MIN 211)

  8. 8.December 19, 2011, 13:15-15:00 (MIN 208) (extra session)


Lecturer:

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

Office hours by appointment


Office at CWI:

Centrum Wiskunde & Informatica
Algorithms, Combinatorics and Optimization
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.


Assignments:

Five take-home assignments will be issued on a bi-weekly basis. The assignments have to be handed in at the beginning of the next lecture or by email (due date, before 11am). PLEASE(!) work in groups of 2-3 students to solve and hand-in the assignment. You may use the list of participants (with email addresses) to find potential collaborators (see online material).


  1. •Assignment 1 (issued Sep. 26), due Oct. 10.

  2. •Assignment 2 (issued Oct. 10), due Oct. 24.

  3. •Assignment 3 (issued Oct. 24), due Nov. 7.

  4. •Assignment 4 (issued Nov. 7), due Nov. 21.

  5. •Assignment 5 (issued Nov. 21), due Dec. 5.


The assignments will be corrected by Bart de Keijzer (email: bdekeijzer at gmail dot com). If you want to hand-in your solution by email, then please send them directly to Bart (before 11am).


The grading scheme for each assignment will be published online. If you seriously think that you deserve more points for an answer you have given, then please send to Bart a scan of the respective exercise together with an explanation of why you think you should get more points.


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


Exam:

The exam is scheduled on:


Date/Time: January 9, 2012, 15:00-18:00

Location: Educatorium, Thetazaal (θ), Utrecht University (see location via google maps).


The re-exam is scheduled on:


Date/Time: January 30, 2012, 15:00-18:00

Location:  Buys Ballot Laboratorium, room 061, Utrecht University (see location via google maps and this website).


Note: Only the Lecture Notes are allowed to be used during the exam and re-exam. NO additional material will be allowed.


Relevant material: The material contained in the Lecture Notes and Assignments 1-5 are relevant for the exam.


Sample exam: In order to get an idea of how the final exam might look like, please have a look at the one of last year (kindly provided by Marc Uetz): exam2010.pdf. Note that this is really just meant to give you an idea. The focus of the final exam might be different.


References and Links:

We will use selected chapters from several books listed below.


  1. •[AMO93]: R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows, Prentice Hall, 1993. ISBN 0-13-617-549.

  2. •[CCPS98]: W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, 1998. ISBN 0-471-55894-X

  3. •[CLRS01]: T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001. ISBN10 0262531968

  4. •[KV08]: B. Korte and J. Vygen, Combinatorial Optimization - Theory and Algorithms, 4th ed., Springer, 2008. ISBN10 3-540-25684-9.

  5. •[PS82]: C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization; Algorithms and Complexity, Prentice-Hall, 1982. ISBN 0-13-152462-3

  6. •[Tar83]: R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1983. ISBN 0-89871-187-8

  7. •[Vaz01]: V. V. Vazirani, Approximation Algorithms, Springer, 2001


Course Material:

Current version of the Lecture Notes of this course. 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).


Additional online material can be found here.


Lecture 1 (2h, Sep. 19):

  1. •Topics: Introduction & organizational issues, preliminaries, minimum spanning tree

  2. •Homework 1 (optional): At the end of today’s class we argued that the Color Invariant remains valid after the application of the blue rule (first part of the inductive argument of the proof of Thm. 2.1). Try to complete the argument for the red rule by yourself (before reading the Lecture Notes). Also argue that eventually all edges are colored.

  3. •Homework 2 (optional): Use the red and/or blue rule to develop an algorithm for the MST problem and analyze its running time.


Lectures 2 & 3 (4h, Sep. 26):

  1. •Topics: Minimum spanning tree (continued), greedy algorithm & matroids

  2. •Homework: Assignment 1 (due Oct. 10). Note that part of Assignment 1 is to get acquainted with asymptotic notation of functions and depth-first search and breadth-first search. Please read the corresponding chapters if you are not familiar with this material.


Lectures 4 & 5 (4h, Oct. 10):

  1. •Topics: Shortest paths and maximum flows

  2. •Homework: Assignment 2 (due Oct. 24).

  3. •Please also read the proof of Theorem 5.3 in the Lecture Notes by yourself. I am not planning to come back to this at the beginning of the next lecture.


Lectures 6 & 7 (4h, Oct. 24):

  1. •Topics: Minimum cost flows

  2. •Homework: Assignment 3 (due Nov. 7).

  3. •If you are not familiar with linear programming, there are various online resources that you can consult (have a look, e.g., at the Lecture Notes by Michel Goemans on this topic). A short exposition can also be found in Chapter 12 of [Vaz01].


Lectures 8 & 9 (4h, Nov. 7):

  1. •Topics: Matchings and integral polyhedra

  2. •Homework: Assignment 4 (due Nov. 21).


Lectures 10 & 11 (4h, Nov. 21):

  1. •Topics: Complexity theory and approximation algorithms

  2. •Homework: Assignment 5 (due Dec. 5).


Lecture 12 (2h, Dec. 5):

  1. •Topics: Approximation algorithms

  2. •Homework: prepare for the exam


Extra Session (2h, Dec. 19):

  1. •On request, we have an extra session on Dec. 19 to discuss whatever you would like to discuss. Please send me an email if you would like me to discuss a specific topic, exercise, etc.