# 186.835 Mathematical Programming This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});});

2019S, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise

## Aim of course

• 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

## Subject of course

• 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

## Course dates

DayTimeDateLocationDescription
Thu17:00 - 19:0014.03.2019 - 13.06.2019Seminarraum FAV 05 (Seminarraum 186) Lecture
Mathematical Programming - Single appointments
DayDateTimeLocationDescription
Thu14.03.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu21.03.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu28.03.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu04.04.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu11.04.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu02.05.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu09.05.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu16.05.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu23.05.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu06.06.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture
Thu13.06.201917:00 - 19:00Seminarraum FAV 05 (Seminarraum 186) Lecture

## Examination modalities

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

Homework Assignments

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.

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

## Course registration

Begin End Deregistration end
31.01.2019 12:00 31.03.2019 23:59 31.03.2019 23:59

## Literature

No lecture notes are available.

## Previous knowledge

• 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

## Language

if required in English