# 186.835 Mathematical Programming Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_22",{id:"j_id_22",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2022S 2021S 2020S 2019S 2018S 2017S 2016S 2015S 2014S 2013S 2012S

2018S, VU, 2.0h, 3.0EC, wird geblockt abgehalten

## Merkmale

• Semesterwochenstunden: 2.0
• ECTS: 3.0
• Typ: VU Vorlesung mit Übung

## Ziele der Lehrveranstaltung

• 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

## Inhalt der Lehrveranstaltung

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

## Weitere Informationen

Estimated effort:

Hours | Purpose
16       | Lecture
10       | Homework exercises
30       | Programming exercise
19       | Exam preparation and exam
--------------------------------------
75       | Overall

## Vortragende Personen

• Leitner, Markus

## LVA Termine

TagZeitDatumOrtBeschreibung
Mi.16:00 - 19:0007.03.2018Seminarraum FAV EG B (Seminarraum von Neumann) Introduction, Programming Exercise
Mi.16:00 - 19:0014.03.2018 - 23.05.2018Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Mathematical Programming - Einzeltermine
TagDatumZeitOrtBeschreibung
Mi.07.03.201816:00 - 19:00Seminarraum FAV EG B (Seminarraum von Neumann) Introduction, Programming Exercise
Mi.14.03.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Branch-and-Cut
Mi.11.04.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Branch-and-Price
Mi.02.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Lagrangian Relaxation, Stochastic and Robust Optimization
Mi.09.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) (Strong) Valid Inequalities, Total Unimodularity
Mi.16.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) MIP Computation
Mi.23.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) (reserve)
LVA wird geblockt abgehalten

## Leistungsnachweis

In addition to the lectures, there will be homework assignments and a 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 May and 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 final exam (50%) and your accomplishments in the homework assignments (15%) and the programming exercise (35%).

## LVA-Anmeldung

Von Bis Abmeldung bis
01.02.2018 12:00 05.04.2018 23:59 05.04.2018 23:59

## Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

## Vorkenntnisse

• 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 Java or C++
• Basic knowledge of linear algebra and graph theory

## Sprache

bei Bedarf in Englisch