|
|
Diskrete Optimierung I (DiskOpt I)5 ECTS
(englische Bezeichnung: Discrete optimization I)
(Prüfungsordnungsmodul: Discrete optimization I)
Modulverantwortliche/r: Alexander Martin
Lehrende:
Lars Schewe, Frauke Liers
| Start semester: |
WS 2018/2019 | Duration: |
1 semester | Cycle: |
jährlich (WS) |
| Präsenzzeit: |
45 Std. | Eigenstudium: |
105 Std. | Language: |
Deutsch |
Lectures:
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:
- 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)
- 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)
Dieses Modul ist daneben auch in den Studienfächern "Informatik (Bachelor of Science)", "Informatik (Master of Science)", "Mathematik (Master of Science)", "Technomathematik (Master of Science)", "Wirtschaftsmathematik (Master of Science)" verwendbar. Details
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
|
|
|