Discrete Optimization

Lecturer

Prof. Rom Pinchasi

Assistants

Rebeka Raffay

Eleonore Bach

News & Log

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, the simplex method and way more fun stuff! Warning: This course is for mathematicians! Strong emphasis is put on formal mathematical proofs.

Schedule

Lecture: Tuesdays 10:15 – 11:45 (CM1105)

Exercises: Tuesdays 8:30 – 10:00 (CM1105)

Exam

There will be no midterm exam. There will be a written final exam after the end of the semester. 

Homework problems

We will publish problems on this website every week. You can work on the exercises and ask questions during the exercise sessions. There will be no assignments.

Exercise_1,Solution 1

Exercise 2, Solution 2

Exercise 3,Solution 3

Exercise 4, Solution_4

Exercise_5, Solution_5

Exercise_6, Solution_6

Exercise_7, Solution_7

Exercise 8, Solution 8

Exercise 9, Solution_9

Exercise_10

Literature

These notes are suggestions. They do not exactly cover the contents of the classes and also contain some content not covered by the classes. They do not replace the classes.

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