Ein neues Forschungsprojekt unter der Leitung von Luca Gambardella, Professor am Dalle Molle Institute for Artificial Intelligence Studies IDSIA (USI-SUPSI) und Prorektor für Innovation und Unternehmensbeziehungen, wurde vom Schweizerischen Nationalfonds (SNF) genehmigt. Die Studie mit dem Titel "Computational methods for integrality gaps analysis" befasst sich aus einer innovativen und originellen Perspektive mit der Optimierung von Algorithmen zur Bewältigung komplexer Probleme.
Das Projekt mit einer geplanten Laufzeit von vier Jahren, an dem ein Postdoktorand und zwei Doktoranden beteiligt sind, wird in Zusammenarbeit mit Professor Monaldo Mastrolilli von der SUPSI durchgeführt, der auch Mitglied des IDSIA (USI-SUPSI) ist. Die Forschung ist inspiriert von den jüngsten Fortschritten bei Algorithmen, die Techniken der künstlichen Intelligenz und approximative/exakte Methoden kombinieren. Aber anstatt die Algorithmen zu untersuchen, ändert es die Perspektive, weil es darauf abzielt, sie herauszufordern, indem es systematisch und mathematisch robuste Instanzen erzeugt, die schwierig zu lösen sind.
Herr Professor Gambardella, was versteht man unter komplexen Problemen?
Die "Komplexitätstheorie", wie sie von Oxford Languages definiert wird, untersucht Systeme, die aus einer sehr großen Anzahl von Elementen bestehen, die nach bestimmten Regeln interagieren und bestimmten Beschränkungen unterliegen. Ziel ist es, das globale Verhalten zu verstehen und die Entwicklung dieser Systeme vorherzusagen. In der Mathematik wird versucht, die minimale Anzahl von Operationen zu bestimmen, die zur Lösung solcher Probleme erforderlich sind. Ein Forschungsthema in diesem Bereich betrifft die Messung der Komplexität eines Problems, indem es nach der Anzahl der Operationen bewertet wird, die zur Lösung einer Instanz des Problems im Verhältnis zur Anzahl der Eingabedaten erforderlich sind.
Anzahl der Operationen, die vermutlich sehr hoch sein könnte.
Es gibt "einfache" Probleme, d. h. Probleme, die mit einer Anzahl von Operationen gelöst werden können, die polynomiell mit der Anzahl der Eingaben zunimmt, und "schwierige" Probleme, die wir später diskutieren werden. Ein Beispiel für ein "einfaches" Problem ist die Berechnung des kürzesten Weges zwischen zwei Punkten in einem gewichteten Graphen, z. B. die Route von Google Maps. Leider gibt es "schwierige" Probleme, für die kein polynomialer Lösungsalgorithmus bekannt ist, und es wird sogar bezweifelt, dass ein solcher Algorithmus überhaupt existiert. Die Lösung dieser Probleme erfordert den Einsatz von Algorithmen mit einer exponentiell steigenden Anzahl von Operationen im Verhältnis zu den Eingabedaten.
Können Sie ein Beispiel für ein "schwieriges" Problem nennen?
Anstatt die Route zwischen zwei Punkten auf einer Karte zu finden, denken wir darüber nach, die kürzeste Route zu berechnen, die in einer bestimmten Stadt beginnt, eine Reihe von bestimmten Städten besucht und zur Ausgangsstadt zurückkehrt. Um dieses Problem zu lösen, muss man alle möglichen Routen aufzählen und ihre Länge messen. Dies erfordert die Berechnung einer faktoriellen Anzahl von Pfaden, was zu einer exponentiellen Komplexität des Algorithmus führt (basierend auf der Stirling-Approximation). Leider werden diese exakten Methoden unpraktisch, wenn die Zahl der Städte über einige hundert hinausgeht, und wir müssen auf Methoden zurückgreifen, die nicht mehr garantieren, dass wir den kürzesten Weg erhalten, sondern ihn nur annähern.
Wie gehen Sie mit diesen Problemen um?
Die traditionelle Strategie, um zu verstehen, ob diese exakten oder approximativen Algorithmen in der Praxis funktionieren, besteht darin, eine Reihe von Instanzen des zu untersuchenden Problems zu nehmen und sie auf einem Computer zu testen. Untersucht werden die tatsächliche Berechnungszeit, um eine Lösung zu finden, und die Qualität der Lösungen, wenn die Größe des Problems zunimmt und sich seine Struktur ändert. Parallel dazu wird auf theoretischer Ebene untersucht, wie hoch das Verhältnis zwischen der Qualität der Lösung eines ganzzahligen linearen Programms, das das Problem löst, und seiner Entspannung ist(Integralitätslücke).
Um diese Studien in der Literatur zu vervollständigen, gibt es Referenzbibliotheken, die Beispiele für verschiedene Arten von Problemen enthalten, mit denen sich die Forscher auseinandersetzen und sich manchmal gegenseitig herausfordern.
Stattdessen basiert unsere Forschung auf einem anderen Ansatz, nämlich der systematischen und mathematisch robusten Generierung schwer zu lösender Instanzen mit dem Ziel, die Grenzen bestehender Algorithmen zu verstehen, um bessere Algorithmen zu entwickeln.
