Algorithmikpraktikum: Solving NP-hard Problems in Practice

In diesem Praktikum geht es darum, bestimmte Instanzen eines NP-schweren Problems optimal zu lösen. Das geschieht mit Hilfe mächtiger Tools, guter Software und vor allem durch die Kombination von Theorie und Praxis. Es werden verschiedene mächtige Werkzeuge zum Lösen NP-schwerer Probleme vorgestellt und benutzt; dazu zählen Integer Programming Solver wie IBM CPLEX oder Gurobi, (inkrementelle) SAT-Solver und Constraint Programming Solver benutzt. Dies bildet den Kern des Praktikums; darüber hinaus gibt es verschiedene Vertiefungsmöglichkeiten:

• Die im Praktikum entwickelten Solver so weit wie möglich optimieren, sodass größere und schwerere Instanzen gelöst werden können. In Experimenten auf verschiedenen Instanzen evaluieren, wie sich Optimierungen auf Laufzeit und Speicherverbrauch auswirken.
• Besonders schwere oder interessante Instanzen erzeugen und die Performance des Solvers darauf evaluieren.
• Heuristische Ansätze entwickeln, die bei Instanzen zum Einsatz kommen können, die nicht mehr exakt gelöst werden können. Experimente durchführen, um diese heuristischen Ansätze bezüglich verschiedener Kriterien zu vergleichen.
• Visualisierung von Instanzen, Lösungen und experimentellen Ergebnissen.