Algorithm Engineering

Lecture: Tuesday 11:30-13:00, SN19.3
Exercise: Monday 15:00-16:30, SN19.2
Wir gehen aktuell von Präsenzlehre aus.

First lecture: 25.04.2022 (im Übungsslot)
First exercise class: 26.04.2022 (im Vorlesungsslot)

Kenntnis von Algorithmen und Datenstrukturen sowie Programmierkenntnisse. Kenntnisse von C++ und Python sind grundsätzlich nützlich, müssen aber nicht unbedingt mitgebracht werden. Die Vorlesung kann ausdrücklich auch von fortgeschrittenen Bachelorstudenten besucht werden. Die Prüfung kann in diesem Fall sowohl als reguläre Bachelor-Prüfung (nach §4.11 der aktuellen BPO) als auch als vorgezogene Master-Prüfung abgelegt werden.

Anmeldung und Kommunikation

Wir verwenden auch für diesen Kurs eine Mailingliste. Über diese Liste versenden wir Material und Ankündigungen, beispielsweise wenn kurzfristig eine Veranstaltung ausfallen sollte. Wir bitten daher alle Teilnehmer und Interessenten, sich möglichst auf dieser Liste anzumelden.

Inhalt

Beim Algorithm Engineering geht es grob vereinfacht gesagt darum, Algorithmen aus der Theorie möglichst effizient und robust in die Praxis umzusetzen. Dabei kann es auch vorkommen, dass man Algorithmen entwirft oder modifiziert, damit sie sich besser in die Praxis umsetzen lassen. In diesem Kurs werdet Ihr folgendes lernen.

Allgemeine Patterns und Guidelines zum Entwickeln und Tunen von Algorithmen:

• Nützliche Design Patterns und API-Design,
• Reproduzierbarkeit und strukturierte Ausführung von Experimenten (z.B. mit slurm),
• Profiling,
• Datenanalyse mit Pandas, Seaborn und Jupyter Notebooks,
• Nativen C++-Code in Python nutzen.

Effizienten Code in C++ schreiben und Performance-Pitfalls moderner Hardware vermeiden:

• Effiziente Datenstrukturen,
• Caching,
• Branch Predicition, Data Dependencies und Pipelining.

NP-Schwere kombinatorische Probleme in vielen Fällen mit wenig (Python-)Code effizient lösen:

• SAT-Solver,
• Constraint Programming (ortools),
• Mixed Integer Programming (Gurobi),
• (Meta-)Heuristiken.

Es gibt inhaltliche Überlappungen mit dem Kurs Mathematische Methoden der Algorithmik und dem Algorithmik-Teamprojekt. Für diesen Kurs solltet Ihr euch grundsätzlich zutrauen, Codebeispielen in C++ und Python zu folgen, sowie ein Interesse am Entwickeln von Algorithmen und auch am Programmieren haben. Der Schwerpunkt der Vorlesung liegt auf dem dritten Teil zu NP-schweren Problemen.

Lernziele

Einführung

In dieser Vorlesung wird ein Überblick über das restliche Semester gegeben. Erst soll gelernt werden, dass aufgrund moderner CPU-Architekturen eine gute Implementierung einen großen Unterschied machen kann und Konstanten nicht zu vernachlässigen sind. Dann soll gelernt werden, dass dank SAT, LP/MIP und CP viele NP-schwere Probleme mittlerweile gut optimiert werden können. Ein Beispiel hier ist das TSP.

CPU Architektur

Moderne CPU-Architekturen sind sehr komplex geworden und weichen mittlerweile stark vom theoretischen Modell ab. Unterschiedliche Operationen, z.B. Addition vs. Division, können nicht nur unterschiedlich lange brauchen sondern selbst die gleichen Operationen können in unterschiedlichen Kontexten unterschiedliche performant sein da sie nicht strikt sequentiell ausgeführt werden (ILP, Branch Prediction, etc.). In dieser Vorlesung sollen die Studierenden lernen, warum Programme trotz gleicher Instruktionszahl (und minimalen Cache-Misses) stark abweichende Laufzeiten haben können und wie sie dies beeinflussen können.

Memory Hierarchy

Da schneller Speicher teuer und aufwendig ist, wird das Prinzip der Lokalität genutzt und auf unterschiedliche Speicherlevel bzw. Caches gesetzt. In dieser Vorlesung sollen die Studierenden lernen, wie der Speicher funktioniert und wie sie diesen am effizientesten Nutzen. Zusätzlich werden die wichtigsten Datenstrukturen betrachtet.

Parallelisierung

Aufgrund stagnierender CPU-Frequenzen wird immer mehr auf Parallelisierung gesetzt. Parallelisierung ist aber nicht einfach und mit einigen Problem und Overheads (insb. bei der Synchronisierung) verbunden. In dieser Vorlesung soll gelernt werden, wie Parallelisierung sinnvoll implementiert weren kann und was es dabei unbedingt zu vermeiden gilt.

Linear Programming

Linear Programming ist ein mächtiges Werkzeug in vielen Kontexten: Einige Optimierungsprobleme lassen sich direkt als LP ausdrücken. Andere Optimierungsprobleme haben eine hilfreiche Linear Relaxation. Lineare Programme können sowohl in der Theorie als auch in der Praxis effizient gelöst werden. Insbesondere lassen sich LPs iterativ lösen. In dieser Vorlesung sollen die Studierenden die Grundlagen des Linear Programmings (Grundlegende Formulierung, Algorithmen, Dualität, Cutting Planes,…) und deren Nutzen lernen. Zusätzlich soll der Gurobi-Log verstanden werden.

Mixed Integer Programming

Mixed Integer Programming ist eine Technik, mit der sich viele wichtige aber NP-schwere Optimierungsprobleme optimal oder zumindest gut lösen lassen. Die Technik nutzt die Lineare Relaxierung aus um mittels Branch and Bound und Cutting Planes zur optimalen Lösung zu gelangen. In dieser Vorlesung sollen die Studierenden die umfangreichen mathematischen Modellierungsmethoden (und deren Probleme) kennen lernen, um so effiziente Modelle für diverse Probleme erstellen zu können.

Traveling Salesman Problem

Am Beispiel vom TSP soll die Funktionsweise von Mixed Integer Programming Solvern tiefer verstanden werden. Ein Großteil der Techniken die Mixed Integer Programming Solver ausmachen, wurde vorher am Traveling Salesman Problem erprobt. Dies macht es zu einem exzellenten Beispiel um Branch and Bound (schon vorher behandelt) und insbesondere Cutting Planes (die hier recht anschaulich sind) tiefer zu verstehen. Hierbei gehen wir auch ein wenig auf die theoretischen Hintergründe ein.

SAT

Moderne SAT-Solver können regelmäßig Probleme mit hunderttausenden Variablen und millionen von Klauseln für reale Anwendungen lösen. In dieser Vorlesung gehen wir auf die hierfür genutzten Techniken ein, insbesondere dem Lernen von Konfliktklauseln. Im Anschluss sollten die Studierenden genug Kenntnisse haben, um einen mäßig effizienten SAT-Solver selber implementieren zu können.

Constraint Programming

Constraint Programming erlaubt es komplexe kombinatorische Probleme zu modellieren, leider waren die Solver aber lange Zeit lang nicht sehr konkurrenzfähig (insb. im Vergleich zu MIPs). Dies scheint sich jetzt insbesondere durch CP-SAT geändert zu haben. CP-SAT nutzt als Grundtechnik einen SAT-Solver mit Lazy Clause Generation, integriert aber u.A. auch den Simplex-Algorithmus. In dieser Vorlesung sollen die Studierenden die Grundideen von CP-SAT sowie dessen Anwendungsmöglichkeiten (insb. im Vergleich zu MIPs) erlernen.

Heuristiken

Nicht immer sind MIP/SAT/CP-Solver selber in der Lage, vernünftige Lösungen zu generieren. In diesen Fällen ist die Nutzung von Heuristiken sinnvoll. Diese können dann genutzt werden um selbständig Lösungen zu finden, oder etwa den MIP-Solver zu unterstützen. In der LNS kann der MIP/CP-Solver selbst auch genutzt werden, um mit wenig Aufwand, gute Heuristiken zu bauen. Zusätzlich werden sich noch weitere Ansätze wie Reinforcement Learning sowie Heuristiken angesehen. Im Anschluss sollten die Studierenden in der Lage sein, für die meisten (kombinatorischen) Probleme eine einfache, aber brauchbare Heuristik zu bauen.