Polyhedral Combinatorics

Worum geht's

Du lernst, wie man kombinatorische Optimierungsprobleme über die Geometrie von Polyedern angeht: Darstellung von Polytope, Zusammenhang zwischen Geometrie und Optimierung linearer Funktionen, sowie moderne Algorithmen wie Branch-and-Cut und Trennung/Optimierung. Am Ende kannst Du die Methoden auf typische Probleme (z. B. Matching-, TSP-Polytope) anwenden und ihre Grenzen im Kontext NP‑Härte einschätzen.

Was du danach kannst

• Verständnis der Darstellung und Eigenschaften von Polytope
• Kenntnis von Simplex-Laufzeitaspekten und Polytop-Durchmesser
• Anwendung von Branch-and-Cut-Methoden und Trennungsalgorithmen
• Verknüpfung zwischen geometrischer Struktur und Optimierung linearer Zielfunktionen
• Einschätzung von Grenzen aufgrund NP‑Härte
• Vertrautheit mit facettiellen Beschreibungen grundlegender kombinatorischer Polytope
• Einblick in erweiterte Formulierungen (extended formulations)

Aus was das Modul besteht

• VorlesungVermittlung der Theorie und Konzepte; Vorlesungsunterlagen werden als PDFs bereitgestellt
• Übungen / Hands-onAnwendung der Methoden in Übungsaufgaben und Hausaufgaben

Lehrmethode

• Vorlesung (PC-basiert, handschriftlich erstellt)Erklärung der Theorie und Bereitstellung der Vorlesungsnotizen als PDFs
• Übungsaufgaben / HausaufgabenFestigung des Stoffes durch praktische Aufgaben und Anwendung