Die Grundidee der linearen Programmierung ist die Optimierung einer linearen Funktion mit Freiheitsgraden, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Dabei ist die lineare Programmierung eines der Hauptverfahren des Operations Research.
Der Vortrag gibt einen kurzen Überblick über grundlegende Konzepte und Eigenschaften der linearen Programmierung sowie Algorithmen zur Lösung solcher Probleme. Anschließend wird – anhand des Problems des Handlungsreisenden (TSP) – die Methode der cutting planes vorgestellt, mit denen auch die (schwierigeren) diskreten linearen Optimierungsprobleme lösbar sind.
Der Vortrag entstand im Rahmen des Seminars „Intelligente Algorithmen“.