Discrete Optimization

News & Log

  • 18/01: The classes are going to start on Thursday, February 22nd in MA B1 11 at 15:15.
  • 26/02: The Piazza forum of the course is available here.
  • 04/05: Since Thursday, May 10th, is a public holiday, there will be no lectures. The exercise session on Friday, May 11th, is not going to be held either. We are going to publish a mock exam in the Assignments section instead.

Description

This course is an introduction to linear and discrete optimization. We will discuss linear programming and combinatorial optimization problems like bipartite matchings, shortest paths and flows. Warning: This course is for mathematicians! Strong emphasis is put on formal mathematical proofs.

Here you can find out more about the course.

Lecture notes

The lecture notes are on GitHub. Please read the REAME.md and clone the repository.

Schedule

Lecture: Thursday 15:15 – 17:00 (MA B1 11); 
Exercises: Friday 10:15 – 12:00 (CM1221);

Office hours: Igor, Wednesdays 13h-14h, MA C1 573
                     Manuel, Wednesdays 15h-16h, MA B1 533 

Grading

Your grade will be determined by a written final exam. You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you score an average of 50% or more in the exercises, the grade of your final exam will be improved by a quarter grade. If you score an average of 90% or more, the grade of your final exam will be improved by a half grade. 

Assignments

We will publish an assignment sheet with problems and practical exercises on this website every week. You can work on the exercises, ask questions, and discuss problems during the exercise sessions.

You will have the opportunity to hand in written solutions for feedback. You can submit the assignments in groups of maximum three students. Correct solutions to selected “star” problems give bonus points. The deadline is one week after the sheet is issued. More precisely, you can either leave your solutions in the box next to office MA C1 563 (be sure you put them in the correct box) or send them via email, or hand them personally to the assistant before the exercise session starts.

We will discuss solutions during the exercise sessions. For any question about the exercises and the material, don’t hesitate to send an email or come during office hours.
 

Programming exercises

We will offer simple practical tasks in C++ and Python to enhance the intuition on the materials covered.

Literature

  1. Alexander Schrijver, Theory of Linear and Integer Programming.
  2. Dimitris Bertsimas, John N. Tsitsiklis, Introduction to Linear Optimization.

  3. Thomas Rothvoss, Discrete Optimization, Course Notes (online version).