Diskrete Optimierung I (DiskOpt I)5 ECTS
(englische Bezeichnung: Discrete optimization I)
(Prüfungsordnungsmodul: Discrete optimization I)

Lehrveranstaltungen:

• • Diskrete Optimierung I
    (Vorlesung, 2 SWS, Frauke Liers, Mi, 10:00 - 12:00, H12)
  • Tutorial zu Diskrete Optimierung I
    (Übung, 1 SWS, Mi, 14:00 - 16:00, Übung 5 / 01.254-128)

Empfohlene Voraussetzungen:

Lineare Algebra, Kombinatorische Optimierung

Inhalt:

Die Vorlesung behandelt theoretische und praktische Grundlagen zur Lösung schwieriger gemischt-ganzzahliger linearer Optimierungsprobleme (MIPs). Zunächst werden Kerndefinitionen der NP-Vollständigkeit behandelt und einige der bekannten NP-vollständigen Probleme vorgestellt. Im Bereich der Polyedertheorie werden die Grundlagen der Seitenstruktur konvexer Polyeder behandelt. Darauf aufbauend werden Schnittebenenverfahren sowie Branch-and-Cut Verfahren zur Lösung von MIPs gelehrt. Abschließend studieren wir einige klassische Probleme der Diskreten Optimierung wie das Rucksack-Problem, das Traveling-Salesman-Problem oder das Set-Packing-Problem.

Lernziele und Kompetenzen:

Die Studierenden

• verfügen über grundlegende theoretische Erkenntnisse zur Lösungemischt-ganzzahliger linearer Optimierungsprobleme (MIPs),

• können MIPs mittels verfügbarer Standard Software lösen.

Literatur:

• Vorlesungsskript zu diesem Modul

• Conforti, Cornuéjols, Zambelli: Integer Programming, Springer 2014

• B. Grünbaum, Convex Polytopes, Springer, 2003

• B. Korte, J. Vygen: Combinatorial Optimization, Springer 2005

• G. L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization, Wiley 1994

• A. Schrijver: Theory of Linear and Integer Programming, Wiley 1986

• L.A. Wolsey: Integer Programming, Wiley 1998

• G. Ziegler, Lectures on Polytopes, Springer, 1995

Bemerkung:

• Wahlmodul: Master Mathematik, Technomathematik und Wirtschaftsmathematik

• Kern-/Forschungsmodul Master Mathematik Studienrichtung „Modellierung, Simulation, Optimierung“, Master Technomathematik Studienrichtung „Optimierung“, Master Wirtschaftsmathematik Studienrichtung „Optimierung und Prozessmanagement“

Organisatorisches:

Neben der Vorlesung werden Übungen angeboten, in denen die Studierenden von einem Übungsgruppenleiter betreut werden. Anhand von Präsenz- und Hausaufgaben werden wesentliche Lerninhalte geübt.

Bis WS 14/15 hieß das Modul "Theoretische Grundlagen der Diskreten Optimierung"!

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2017w | NatFak | Computational and Applied Mathematics (Master of Science) | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Discrete optimization I)
2. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2017w | NatFak | Computational and Applied Mathematics (Master of Science) | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Discrete optimization I)

Studien-/Prüfungsleistungen:

Discrete optimization I (Prüfungsnummer: 59171)

(englischer Titel: Discrete optimization I)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 15, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: WS 2018/2019, 1. Wdh.: WS 2018/2019

1. Prüfer:

Frauke Liers