Discrete Optimization (DiscOpt I)5 ECTS
(englische Bezeichnung: Discrete Optimization)

Lehrveranstaltungen:

• • Diskrete Optimierung I
    (Vorlesung, 2 SWS, Andreas Bärmann, Fr, 8:00 - 10:00, H12)

Empfohlene Voraussetzungen:

Recommended: Linear and Combinatorial Optimization

Inhalt:

Theoretical and practical fundamentals of solving difficult mixed-integer linear optimization problems (MIPs) constitute the main focus of this lecture. At first, the concept of NP-completeness and a selection of common NP-complete problems will be presented. As for polyhedral theory, fundamentals concerning the structure of faces of convex polyhedra will be covered. Building upon these fundamentals, cutting plane algorithms as well as branch-and-cut algorithms for solving MIPs will be taught. Finally, some typical problems of discrete optimization, e.g., the knapsack problem, the traveling salesman problem or the set packing problem will be discussed.

Lernziele und Kompetenzen:

Students

• will gain basic theoretical knowledge of solving mixed-integer linear

optimization problems (MIPs),

• are able to solve MIPs with the help of state-of-the-art optimization software

Literatur:

• Lecture notes

• 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

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Artificial Intelligence (Master of Science)
   (Po-Vers. 2021s | TechFak | Artificial Intelligence (Master of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
2. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2017w | NatFak | Computational and Applied Mathematics (Master of Science) | Non-Specialisation modules | Discrete optimization I)
3. 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)
4. 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)
5. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Discrete optimization I)
6. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Discrete optimization I)
7. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Non-Specialisation modules | Discrete optimization I)
8. Data Science (Master of Science)
   (Po-Vers. 2021w | Gesamtkonto | Studienrichtung Databased optimization | Discrete optimization I)
9. Informatik (Bachelor of Science)
   (Po-Vers. 2009s | TechFak | Informatik (Bachelor of Science) | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
10. Informatik (Bachelor of Science)
    (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
11. Informatik (Master of Science)
    (Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Discrete optimization I)
12. Mathematik (1. Staatsprüfung für das Lehramt an Gymnasien)
    (Po-Vers. 2019w | NatFak | Mathematik (1. Staatsprüfung für das Lehramt an Gymnasien) | Module Fachwissenschaft Mathematik | Wahlpflichtbereich Angewandte Mathematik | Discrete optimization I)
13. Mathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Mathematik (Master of Science) | alte Prüfungsordnungen | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
14. Mathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Mathematik (Master of Science) | alte Prüfungsordnungen | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
15. Mathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Mathematik (Master of Science) | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
16. Mathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Mathematik (Master of Science) | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
17. Mathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Mathematik (Master of Science) | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
18. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Studienrichtung Optimierung und Prozessmanagement | Kernmodule Studienrichtung Optimierung und Prozessmanagement | Discrete optimization I)
19. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2014w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Studienrichtung Optimierung und Prozessmanagement | Forschungsmodule Studienrichtung Optimierung und Prozessmanagement | Discrete optimization I)
20. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Wirtschaftsmathematik (Master of Science) | Studienrichtung Optimierung und Prozessmanagement | Kernmodule Studienrichtung Optimierung und Prozessmanagement | Discrete optimization I)
21. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Wirtschaftsmathematik (Master of Science) | Studienrichtung Optimierung und Prozessmanagement | Forschungsmodule Studienrichtung Optimierung und Prozessmanagement | Discrete optimization I)
22. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Wirtschaftsmathematik (Master of Science) | Mathematische Wahlmodule | Studienrichtung Modellierung, Simulation und Optimierung | Kernmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
23. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Wirtschaftsmathematik (Master of Science) | Mathematische Wahlmodule | Studienrichtung Modellierung, Simulation und Optimierung | Forschungsmodule Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
24. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Studienrichtung Optimierung und Prozessmanagement | Discrete optimization I)
25. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | Studienrichtung Modellierung, Simulation und Optimierung | Discrete optimization I)
26. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Discrete optimization I)
27. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | 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 2021/2022, 1. Wdh.: WS 2021/2022

1. Prüfer:

Andreas Bärmann

Termin: 17.03.2022, 10:00 Uhr