Discrete Optimization ‒ Disopt ‐ EPFL

Lecturer

Assistants

Igor Malinovic, Jana Cslovjecsek, Moritz Venzin, Gaëtan Bossy

News & Log

05/02: The classes are going to start on Thursday, February 21st in CE1104 at 08:15.
20/02: The Piazza forum of the course is available here.
27/02: The lecture and exercise rooms are changed to CE1106 and CM1121, respectively.
01/03: Starting from Homework 2, we will only accept solutions submitted on the homework sheet.
18/04: This week there will be no exercise session. You may use the mock exam to practice. We also provide a Joker Homework due an May 3, i.e., the points attained on this homework can replace one of your past or future homeworks.
17/05: As a preparation for the exam, office hours will be organized in MA B1 524 on Tuesday, June 25, 13h-16h.
30/05: There will be no exercise session on Friday, May 31.

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 08:15 – 10:00 (CE1106);
Exercises: Friday 10:15 – 12:00 (CM1121);

Office hours: Igor, Thursdays 15h-16h, MA C1 573
Jana, Moritz, 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 homework sheets. If you score an average of 50% or more in the homework, 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 and homework problems

We will publish 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 to homework problems. You can submit the assignments in groups of maximum three students. Correct solutions to those 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

Alexander Schrijver, Theory of Linear and Integer Programming.
Dimitris Bertsimas, John N. Tsitsiklis, Introduction to Linear Optimization.
Thomas Rothvoss, Discrete Optimization, Course Notes (online version).