Johanna Sommer

Kombinatorische Probleme stehen im Mittelpunkt unzähliger Aufgaben, von Sudoku über alltägliche Rechenaufgaben bis hin zu milliardenschweren Operationen. Herausforderungen wie die Weiterleitung von Lieferungen, die Planung des Zugriffs auf ein Netzwerk und der Entwurf von Schaltkreisen lassen sich alle auf dieselben Konzepte reduzieren. Das Besondere an dieser Klasse von Problemen, die auch als kombinatorische Probleme bezeichnet werden, ist ihr hoher Rechenaufwand. Es gibt zwar Lösungsansätze, aber sie beruhen oft auf handgefertigten, anwendungsspezifischen Heuristiken. Daher wurden mehrere Ansätze vorgeschlagen, bei denen (geometrisches) Deep Learning zum Einsatz kommt, um Problemeigenschaften disziplinübergreifend zu lernen und solche Probleme zu lösen.

Diese transdisziplinäre Problemlösung klingt vielversprechend, da sie es uns z. B. ermöglichen würde, ein neuronales Graphennetz auf Straßenkartendaten zu trainieren und dann Lösungen für andere Bereiche wie boolesche Schaltungen abzuleiten. Allerdings ist die Strategie, mit der solche Trainingsdaten erstellt werden, von zentraler Bedeutung für die Praxistauglichkeit des resultierenden Modells. Wenn ein neuronaler Lösungsalgorithmus auf einer Reihe von Problemen aus demselben Bereich trainiert und bewertet wird, können wir nicht darauf schließen, wie gut er Probleme aus anderen Bereichen lösen kann.

Im Rahmen meines Promotionsstudiums untersuche ich, inwieweit sich die derzeitigen Ansätze tatsächlich disziplinübergreifend verallgemeinern lassen. Indem ich zum Beispiel Methoden aus dem Bereich der Robustheit von neuronalen Netzen verwende, kann ich spezifische Probleminstanzen identifizieren, die für das Modell schwer zu lösen sind. Das Wissen um solche "blinden Flecken" kann dann die Konstruktion besserer neuronaler Lösungsalgorithmen leiten. Das Wissen um solche "blinden Flecken" kann dann die Konstruktion besserer neuronaler kombinatorischer Löser leiten.