• Get a broader knowledge in the area of mathematical optimization with focus on (mixed) integer linear programming (MIP)
• Be able to model both academic and real world problems as MIPs
• Be able to theoretically analyze and compare different mathematical programming formulations for a problem
• Have knowledge on common methodology for solving MIPs
• Be able to develop practical solution algorithms using state-of-the-art MIP frameworks

• Overview on mathematical optimization (focus on mixed integer models, but also including non-linear and non-deterministic models)
• Modeling (real world) problems as MIPs (basic techniques, modeling with exponentially many constraints and / or variables)
• Solution methods for MIPs
  - Cutting plane method, branch-and-cut
  - Decomposition approaches (Langrangian decomposition, Dantzig-Wolfe decomposition) and corresponding solution methods (subgradient method, column generation, branch-and-price)
• Theory of valid inequalities and further theoretical concepts
  - (Strong) valid inequalities (Chvatal-Gomory cuts, Gomory cuts, mixed integer cuts, cover cuts, theoretical concepts such as dominance, redundancy, facet defining cuts)
  - "Well-solved" problems (properties, total unimodularity, optimization = separation)
• Further issues in MIP computation and components of modern MIP solvers (presolving, primal heuristics, symmetry, frameworks)
• Overview on further methods and extensions (stochastic- and robust optimization, non-linear programming, multiobjective optimization)

Estimated effort:

Hours | Purpose
20       | Lecture
15       | Homework exercises 
25       | Programming exercise
15       | Exam preparation and exam
--------------------------------------
75       | Overall

In addition to the lectures, there will be optional homework assignments and a mandatory programming exercise.

Homework Assignments

Specifications will be made available for download in TISS.

Programming Exercise

You will have to design and implement different integer programming formulations for a specified optimization problem. Specifications and the framework will be available for download in TISS. You should join in groups of two for this programming exercise and send your results by mail to us (deadlines will be announced).

Final Exam

Dates for the final oral exam will be available in June and also in summer if required. Details will be announced here.

• Each team (w.r.t. the programming exercise) should choose a common date / timeslot for the exercise (unless there are good reasons not to do so).
• You should register for the exam by email (to both of us). In this email please specify who is going to take the exam (you and your partner), the date and constraints regarding the concrete time (as we will try to schedule the exams such that there are not too long breaks for us). For each group of two we will reserve 45 minutes and for a single student we will reserve 30 minutes.
• The concrete location of the exam will be announced to you by mail.

Grading

The mark you receive depends on the total points collected for all tasks:

• (optional) homework exercises: max. 30 points
• programming exercise: at least 20 points, max. 35 points
• final oral exam: at least 25 points, max. 50 points

The grade is obtained by the following mapping:

1: 89+ points
2: 76 - 88
3: 63 - 75
4: 50 - 62
5: 0 - 49

• Basic knowledge of (integer) linear programming (modeling, LP based Branch-and-Bound) as e.g. taught in Algorithmics
• Knowledge of basic algorithms and data structures
• Programming skills in some language, e.g., Java, C++, Python
• Basic knowledge of linear algebra and graph theory