Der Schwerpunkt der Vorlesung „Diskrete Optimierung (Optimierung II)“ ist die Theorie und Lösung ganzzahliger und kombinatorischer Optimierungsprobleme. Es werden Schnittebenenverfahren, Augmentierungsmethoden, Approximationsalgorithmen sowie Dynamische Programmierung behandelt. Klassische Probleme der Diskreten Optimierung wie das Rucksack-Problem, das Traveling Salesman Problem oder das Setpacking Problem finden ebenfalls Beachtung.
Datum:
Dozenten: Prof. Dr. Alexander Martin
Semester: SoSe 2009
Themenbereiche: Naturwissenschaften
Bereiche: Mathematik
Sprache: deutsch
Links:
Vorlesungen:
- Exakte Verfahren II: Dynamische Programmierung, Anwendungen Approximationsalgorithmen 01.04.2009
- Primal-Dual-Approximationsalgorithmen I 01.04.2009
- NP-Vollstaendigkeit, Totale Unimodularitaet 01.04.2009
- Randomisierte Approximationsalgorithmen 01.04.2009
- Ein FPAS für das Rucksackproblem 01.04.2009
- Implementierung von MIP Lösern Teil 1 01.04.2009
- Primal-Dual-Approximationsalgorithmen II 01.04.2009
- Ganzzahlige Polyeder, Zulaessige Mengen 01.04.2009
- Exakte Verfahren I: Branch & Bound, Dynamische Programmierung 01.04.2009
- Allgemeine Schnittebenen: Chvatals geometrischer Ansatz 01.04.2009
- Dantzig-Wolfe Dekomposition 01.04.2009
- Implementierung von MIP Lösern Teil 3 01.04.2009
- Grundlagen der Polyedertheorie, Projektion 01.04.2009
- Anwendungen der TDI-Eigenschaft, Relaxierungen 01.04.2009
- Totale Duale Integralität 01.04.2009
- Heuristiken, Der Greedy-Algorithmus 01.04.2009
- Anwendungen von Totaler Unimodularitaet, Hermitesche Normalform 01.04.2009
- Ungleichungen mit Struktur: Das Rucksack und Set Packing Polytope 01.04.2009
- Implementierung von MIP Lösern Teil 2 01.04.2009
- Ganzzahliges Analogon des Farkas-Lemmas, Totale Duale Integralität 01.04.2009
- Gomorys algorithmischer Ansatz 01.04.2009
- Lagrange Relaxierung 01.04.2009
- Einführung – Beispiele und Formulierungen 01.04.2009
- Darstellungssaetze 01.04.2009
- Benders Dekomposition, Vergleich der Relaxierungen 01.04.2009
- Fourier-Motzkin Elimination, Satz von Weyl 01.04.2009
- Lokale Suche 01.04.2009