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

Lehrveranstaltungen:

• • Diskrete Optimierung 1
    (Vorlesung, 2 SWS, Andreas Bärmann, Do, 14:00 - 16:00, H12)
  • Übung zu Diskrete Optimierung 1
    (Übung, 1 SWS, Andreas Bärmann, jede 2. Woche 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:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

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)
3. Informatik (Master of Science)
   (Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
4. Mathematik (Master of Science)
   (Po-Vers. | NatFak | Mathematik (Master of Science) | Masterprüfung | Studienrichtung Modellierung, Simulation und Optimierung | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung)
5. Mathematik (Master of Science)
   (Po-Vers. | NatFak | Mathematik (Master of Science) | Masterprüfung | Studienrichtung Modellierung, Simulation und Optimierung | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung)
6. Mathematik (Master of Science)
   (Po-Vers. 2014w | NatFak | Mathematik (Master of Science) | Masterprüfung | Studienrichtung Modellierung, Simulation und Optimierung | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung)
7. Mathematik (Master of Science)
   (Po-Vers. 2014w | NatFak | Mathematik (Master of Science) | Masterprüfung | Studienrichtung Modellierung, Simulation und Optimierung | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung)
8. Mathematik (Master of Science)
   (Po-Vers. 2014w | NatFak | Mathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule)
9. Technomathematik (Master of Science)
   (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung | Kernmodule Studienrichtung Optimierung)
10. Technomathematik (Master of Science)
    (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung | Forschungsmodule Studienrichtung Optimierung)
11. Technomathematik (Master of Science)
    (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Kernmodule Studienrichtung Optimierung und Prozessmanagement)
12. Technomathematik (Master of Science)
    (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Forschungsmodule Studienrichtung Optimierung und Prozessmanagement)
13. Technomathematik (Master of Science)
    (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung)
14. Technomathematik (Master of Science)
    (Po-Vers. | NatFak | Technomathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung)
15. Technomathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Technomathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung | Kernmodule Studienrichtung Optimierung)
16. Technomathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Technomathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung | Forschungsmodule Studienrichtung Optimierung)
17. Technomathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Technomathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule)
18. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung und Prozessmanagement | Kernmodule Studienrichtung Optimierung und Prozessmanagement)
19. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung und Prozessmanagement | Forschungsmodule Studienrichtung Optimierung und Prozessmanagement)
20. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Kernmodule Studienrichtung Optimierung)
21. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Forschungsmodule Studienrichtung Optimierung)
22. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung)
23. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung)
24. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung und Prozessmanagement | Kernmodule Studienrichtung Optimierung und Prozessmanagement)
25. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Studienrichtung Optimierung und Prozessmanagement | Forschungsmodule Studienrichtung Optimierung und Prozessmanagement)
26. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Wirtschaftsmathematik (Master of Science) | Masterprüfung | Mathematische Wahlmodule)

Studien-/Prüfungsleistungen:

Diskrete Optimierung 1 (Prüfungsnummer: 758644)

(diese Prüfung gilt nur im Kontext der Studienfächer/Vertiefungsrichtungen [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26])

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

Anteil an der Berechnung der Modulnote: 100.0 %

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

1. Prüfer:

Andreas Bärmann

Discrete optimization I (Prüfungsnummer: 59171)

(englischer Titel: Discrete optimization I)

(diese Prüfung gilt nur im Kontext der Studienfächer/Vertiefungsrichtungen [1], [2], [3])

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

Anteil an der Berechnung der Modulnote: 100.0 %

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

1. Prüfer:

Andreas Bärmann