186.835 Mathematical Programming
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2020S, VU, 2.0h, 3.0EC

Merkmale

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

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • das Gebiet der mathematischen Optimierung mit Fokus auf Mixed Integer Linear Programming (MIP) zu überblicken,
  • sowohl akademische als auch real-world Entscheidungsprobleme als MIP zu modellieren,
  • verschiedene MIP Formulierungen für ein Problem theoretisch zu analyiseren und zu vergleichen,
  • die allgemeinen Lösungsmethoden für MIPs zu verstehen,
  • praktische Lösungsalgorithmen basierend auf state-of-the-art MIP frameworks zu entwickeln.

Inhalt der Lehrveranstaltung

  • Overview on mathematical optimization (focus on mixed integer linear models, but also discussing 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 (Lagrangian 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)
  • Stochastic and robust optimization
  • Further issues in MIP computation and components of modern MIP solvers (presolving, primal heuristics, symmetry, frameworks)

Methoden

  • Lecture based on slides
  • Introduction to the usage of a state-of-the-art MIP solution framework (CPLEX)
  • Homework exercises
  • Programming exercises

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Estimated effort:

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

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.16:00 - 18:0009.03.2020Seminarraum FAV EG B (Seminarraum von Neumann) Lecture

Leistungsnachweis

  • Homework exercises (max. 20 points): Exercises are done at home and solutions are uploaded in TUWEL.
  • Programming Exercises (max. 40 points): Different MIP formulations for a specified optimization problem are designed and implemented. You can (optionally) join in groups of two. Your solutions are uploaded in TUWEL.
  • Written exam (max. 40 points)

Grading

The mark you receive depends on the total points collected for all tasks, but you need at least 30 points in the exercise part (including homework and programming exercises) and at least 20 points in the written exam to finish positive. The final grade is obtained by the following mapping:

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

LVA-Anmeldung

Von Bis Abmeldung bis
30.01.2020 12:00 06.04.2020 23:59 06.04.2020 23:59

Curricula

Literatur

all material is available in TUWEL

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 some language, e.g., Java, C++, Python
  • Basic knowledge of linear algebra and graph theory

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen

Sprache

Englisch