Dieses Modul behandelt die ganzzahlige lineare Programmierung und ihre Verwendung bei der Lösung von NP-harten (kombinatorischen Optimierungs-) Problemen. Wir werden einige Beispiele dafür behandeln, was ganzzahlige lineare Programmierung ist, indem wir Probleme wie Knapsack, Vertex Cover und Graph Coloring formulieren. Als nächstes werden wir das Konzept der Integralitätslücke untersuchen und den Spezialfall der Integralitätslücke für Vertex-Cover-Probleme betrachten. Wir schließen mit einem Tutorium zur Formulierung und Lösung ganzzahliger linearer Programme mit der Python-Bibliothek Pulp.

Wir werden Näherungsalgorithmen für die Lösung NP-schwerer Probleme vorstellen. Bei diesen Algorithmen handelt es sich um schnelle (oft gierige) Algorithmen, die zwar keine optimale Lösung liefern, aber garantieren, dass ihre Lösung nicht "zu weit weg" von der bestmöglichen Lösung ist. Wir werden einige dieser Algorithmen vorstellen, beginnend mit einer grundlegenden Einführung in die betreffenden Konzepte, gefolgt von einer Reihe von Approximationsalgorithmen für Scheduling-Probleme, das Vertex-Cover-Problem und das Problem der maximalen Erfüllbarkeit.

Wir stellen das Problem des reisenden Verkäufers (TSP) vor: ein sehr wichtiges und weit verbreitetes kombinatorisches Optimierungsproblem, seine NP-Härte und die Härte der Approximation eines allgemeinen TSP mit einem konstanten Faktor. Wir präsentieren eine ganzzahlige lineare Programmierformulierung und einen einfachen, aber eleganten dynamischen Programmieralgorithmus. Wir werden einen 3/2-Faktor-Approximationsalgorithmus von Christofides vorstellen und einige heuristische Ansätze zur Lösung von TSPs diskutieren. Abschließend stellen wir Approximationsverfahren für das Knapsack-Problem vor.