Discrete Optimization

Lecturer

Prof. Friedrich Eisenbrand

Assistants

Manuel Aprile

Igor Malinović

Sarah Morell

Etienne Petit

Théophile Thiery

News & Log

  • 14/02: The classes are going to start on Thursday, February 23rd in CM1 at 08:15.
  • 03/03: Assignment 2 got updated.
  • 22/03: A programming exercise got published, more details on Piazza.
  • 30/03: Programming exercise 2 is on the server (Simplex algorithm).
  • 05/04: Bonus points are published in the assignment section. Please write to Igor if there are mistakes.
  • 10/05: Additional materials on connected layer families can be found here.
  • 15/05: The detailed guidelines have been added for the star problem in Assignment 9; see the assignment section below. Its deadline has been extended until Monday, May 22 18:00. Any further questions could be posed on Piazza. The deadline for the star problem of Assignment 10 is still May 19 12:00 noon.
  • 07/06: The final list of bonus points is published. Please write to Igor if there are mistakes.

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 (CM1); 
Exercises: Friday 10:15 – 12:00, rooms:
                   CM012: Students with family name A-G,
                   CM1113: H-L,
                   CM1221: M-Z;

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

For those who are interested in practical exercises we provide an online programming platform. You can log into the server under http://mathaapc36.epfl.ch:8000/ (Note that the server is only accessible over the EPFL network/VPN). For more details please check the piazza forum.

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).