Diese Vorlesung führt in Optimierungsprobleme und einige Optimierungstechniken anhand des Knapsack-Problems ein, einem der bekanntesten Probleme auf diesem Gebiet. Es wird erörtert, wie man Optimierungsprobleme am Beispiel des Knapsack-Problems formalisiert und modelliert. Anschließend wird die Anwendung der dynamischen Programmierung und des Branch-and-Bound-Verfahrens auf das Knapsack-Problem besprochen, wobei diese beiden grundlegenden Optimierungstechniken erläutert werden. Das Konzept der Entspannung und der Suche wird ebenfalls besprochen.

Die Constraint-Programmierung ist eine Optimierungstechnik, die aus dem Bereich der künstlichen Intelligenz hervorgegangen ist. Sie ist durch zwei Schlüsselideen gekennzeichnet: Das Optimierungsproblem auf einer hohen Ebene auszudrücken, um seine Struktur zu offenbaren, und Constraints zu verwenden, um den Suchraum zu verkleinern, indem Werte, die in den Lösungen nicht vorkommen können, aus den Variablenbereichen entfernt werden. Diese Vorlesungen behandeln die Constraint-Programmierung im Detail. Sie beschreiben die Sprache der Constraint-Programmierung, das ihr zugrunde liegende Berechnungsparadigma und wie sie in der Praxis angewendet werden kann.

Die lokale Suche ist wahrscheinlich die älteste und intuitivste Optimierungstechnik. Sie besteht darin, von einer Lösung auszugehen und diese zu verbessern, indem (in der Regel) lokale Störungen (oft als Züge bezeichnet) durchgeführt werden. Die lokale Suche hat sich in den letzten Jahrzehnten erheblich weiterentwickelt, wobei der Frage, welche Züge zu untersuchen sind, viel Aufmerksamkeit gewidmet wurde. Diese Vorlesungen befassen sich mit der Theorie und Praxis der lokalen Suche, vom Konzept der Nachbarschaft und der Konnektivität bis hin zu Meta-Heuristiken wie der Tabu-Suche und dem Simulated Annealing.

Die lineare Programmierung ist und bleibt ein Arbeitspferd der Optimierung. Sie besteht in der Optimierung eines linearen Ziels mit linearen Beschränkungen, lässt effiziente algorithmische Lösungen zu und ist oft ein wichtiger Baustein für andere Optimierungstechniken. In diesen Vorlesungen werden die grundlegenden Konzepte der linearen Programmierung behandelt, einschließlich des berüchtigten Simplex-Algorithmus, des Simplex-Tableaus und der Dualität. .

Die gemischt-ganzzahlige Programmierung verallgemeinert die lineare Programmierung, indem sie ganzzahlige Variablen zulässt, was die Komplexität der Probleme dramatisch verändert, aber auch die Anwendungsmöglichkeiten erheblich erweitert. In diesen Vorlesungen wird besprochen, wie Probleme in der gemischt-ganzzahligen Programmierung modelliert werden und wie gemischt-ganzzahlige Programme mit Hilfe von Branch and Bound gelöst werden können. Auch fortgeschrittene Techniken wie Schnittebenen und polyedrische Schnitte werden behandelt.

Diese Vorlesungen behandeln einige fortgeschrittene Konzepte der Optimierung. Sie stellen Constraint-Programmierungstechniken für die Terminplanung und das Routing vor.

In diesen Vorlesungen werden einige fortgeschrittenere Konzepte der Optimierung behandelt. Sie stellen die Suche in großen Nachbarschaften vor, die oft eine Kombination aus Constraint-Programmierung und lokaler Suche ist, sowie die Spaltengenerierung, die ein Optimierungsmodell in ein Master- und ein Preisproblem zerlegt und dabei komplexere Variablen verwendet.