Robust Optimization

Note that meetings will be always either during the time slot on Monday, 16:15 - 18:00 or on Wednesday, 16:15 - 18:00. We will make sure that the Wednesday meetings do not collide with the OR courses meetings. It will be announced in advance on this website and via mail when meetings are scheduled and how they are happening (on-site, webex or both).

Lecture

List of lecture videos

Title Content Slides Video
00 Intro Introduction to robust optimization; discrete uncertainty sets, interval uncertainty sets Download Video
01 Recap: LP and MIP Recap of some basic facts about LP and MIP Download Video
02 Discrete Cost Uncertainty in Combinatorial Optimization NP-hardness and K-Approximation Download Video 01
strong NP-hardness; pseudopolynomial algorithm for constant K Video 02
connection to multi-objective optimization Video 03
Robust Global Minimum Cut Video 04
FPTAS Meta-Theorem tba.
03 Regret Robustness Introduction into the concept of regret Download Video 01
04 Interval Uncertainty Basic results about interval uncertainty Download Video 01
Approximation and Complexity Download Video 02
Spanning tree NP-hardness Download Video 03
Spanning tree MIP + structure Download 02 Video 04 Video 05 Video 06
05 Budgeted interval uncertainty sets and extensions Download Video 01 Video 02 Video 03

Grading

Via an oral exam after the end of the course.

Exercises

Thinking Assignments

Contribution to each "Thinking Assignment" is mandatory for all participating students. You may miss up to 3 such assignments and still pass the course. There will be extra points for great contributions to "Thinking Assignments".
Lecture Slides Question Discussion Meeting
01 Intro What other ideas do you have for modelling uncertainty using uncertainty sets? Monday, October 12, 2020, 16:15 at AE06 and Webex

Exercise Assignments

You should be ready to present some of the exercises during the stated "Discussion Meeting". For each exercise you present you can recive up to 3 points. The total number of points recived via exercises is bounded by 30.
Exercise Sheet Topic Discussion Meeting
Sheet 01 LP and MIP recap Monday, October 12, 2020, 16:15 at AE06 and Webex
Sheet 02 Discrete Uncertainty Wednesday, October 28, 2020, 16:15 via Webex
Sheet 03 Interval Uncertainty Wednesday, November 18, 2020, 16:15 via Webex
Sheet 04 Interval Uncertainty Monday, December 7, 2020, 16:15 via Webex
Sheet 05 Budgeted Interval Uncertainty Wednesday, January 27, 2020, 16:15 via Webex

Project

There will be a theory or implementation student to be done by every student. You will recive up to 70 points for this project.

Grading Scheme

Let P be the total number of points.