Algorithmikpraktikum: Solving NP-hard Problems in Practice

In diesem Praktikum geht es darum, bestimmte Instanzen eines NP-schweren Problems optimal zu lösen (es sind grundsätzlich verschiedene Probleme denkbar). Das geschieht mit Hilfe mächtiger Tools, guter Software und vor allem durch die Kombination von Theorie und Praxis. Insbesondere werden vorhandene Integer Programming Solver wie IBM CPLEX oder Gurobi benutzt. Dies bildet den Kern des Praktikums; darüber hinaus gibt es verschiedene Vertiefungsmöglichkeiten:

• Den 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.