Kennen Sie das Traveling Salesperson Problem? Und noch wichtiger: Könnten Sie zu seiner Lösung beitragen?

Es geht dabei um eine Systematik, eine Reihenfolge für den Besuch verschiedenster Adressen zu finden, bei der keine Station außer der ersten mehr als einmal besucht wird. Zudem soll die gesamte Reisestrecke möglichst kurz und die erste Station auch die letzte sein. Diese, auf deutsch auch als »Botenproblem« bekannte, knifflige Aufgabe ist eine ebenso zentrale wie beispielhafte Fragestellung zur kombinatorischen Optimierung in der theoretischen Informatik.

Im Gegensatz zum Traveling Salesperson Problem ist das quadratische Zuweisungsproblem, um das es nun gehen soll, im Ansatz zwar ähnlich, aber nochmals deutlich komplexer. So komplex, dass es zur Klasse »NP-Vollständig« gehört, also zu den am schwierigsten zu lösenden Problemstellungen überhaupt. Denn es geht um die Bewältigung vielfältiger Verflechtungen und Zuordnungen, die sich – bei gebotener Effizienz der Prozesse - kaum bezwingen lassen.

Das aber könnte eigentlich nur ein Problem der Mathematik, Informatik oder ähnlicher Berufszweige sein.

Allerdings sollte und muss auch für die Behandlung des quadratischen Zuweisungsproblems dringend eine Lösung für den industriellen Alltag gefunden werden. Beispielsweise, um zeitintensive Entwicklungen von elektronischen Schaltkreisen und Komponenten zu beschleunigen. Das gilt unter anderem für einen Field Programmable Gate Array, kurz FPGA. Ein FPGA ist ein integrierter Schaltkreis, wie er in der Digitaltechnik milliardenfach verwendet wird. Davon aber später.

Zunächst müssen wir versuchen, die Dimension eines quadratischen Zuweisungsproblems besser zu verstehen.

Das quadratische Zuweisungsproblem

Helfen dabei können die anschaulichen Erklärungen von Dr. Thomas Soddemann. Er ist Physiker, Leiter des Geschäftsfelds High Performance Computing und Projektleiter am Fraunhofer-Institut für Algorithmen und Wissenschaftliches Rechnen SCAI. Er sagt: »Ein quadratisches Zuweisungsproblem kann beispielsweise beim Flottenmanagement eines Paketdienstleisters auftreten. Wegen der unterschiedlichen Absenderadressen und wechselnden Empfängeradressen können die Distributoren in der Regel keine festen Routen für die Fahrzeuge planen: Jedes Fahrzeug muss dabei die ihm zugewiesenen Empfänger*innen abfahren, um die Pakete auszuliefern. Gesucht ist nun eine Systematik, wie welche Empfänger*innen und in Abhängigkeit vom Paketvolumen (es muss ja alles ins Fahrzeug passen und es darf nicht zu schwer sein) angefahren werden sollen. Und das stets unter Berücksichtigung der Belade-Situation der anderen Fahrzeuge und vor allem der Fahrer*innen. Denn natürlich muss auch geachtet werden, welche Mitarbeiter*innen an diesem Tag zur Verfügung stehen, welches Zeitfenster sie abdecken können, und wie eine möglichst ausgewogene Arbeitsbelastung gewährleistet werden kann. Zudem ist erlaubt, dass Fahrzeuge während eines Arbeitstages auch eine zweite Route fahren können. Ziel dieses – dann nahezu perfekten – Plans ist es, die gesamte Wegstrecke und den damit verbundenen Zeitaufwand so klein wie möglich zu halten.«

Programmierung von FPGAs

Dieses Szenario final so zu berechnen, dass es zu einer optimalen Lösung kommt, ist, so Soddemann, fast unmöglich. Denn die Problemgröße und damit die Rechenzeit steige mit jedem weiteren Paket, Fahrzeug, Wegpunkt oder jedem weiteren oder jeder weiterer Fahrer*in exponentiell an. Selbst wenn für die Berechnung der nahezu Optimallösung beispielsweise für eine mittelgroße Stadt der schnellste Computer der Welt genutzt würde: Die Empfänger*innen müssten Jahre auf ihre Pakete warten. Sehr, sehr viele Jahre. Deshalb müssen sich Logistikunternehmen (und ihre Kund*innen) auch mit »guten Lösungen« zufriedengeben, also dem Versuch, in absehbarer Zeit möglichst gut an das Bestmögliche heranzukommen – ohne es erreicht zu haben.

Ähnlich – so Soddemann – ist das bei der Programmierung eines der bereits erwähnten FPGAs. »Er besitzt auf seiner Oberfläche eine Vielzahl verschiedener, elektronischer Bauteile, die ich bei Programmierung so effizient verschalten muss, dass der Daten-Input intelligent verteilt und auf kürzestem Weg so verarbeitet werden kann, dass am Ende möglichst schnell das Ergebnis an den Output-Pins wieder anliegt.«

Einsatz von Synthetisierungswerkzeugen

In der Industrie übernimmt diese Verschaltung ein sogenanntes Synthetisierungswerkzeug. Seine Arbeit ist in etwa mit einem Compiler vergleichbar, den Programmierer*innen nutzen. Compiler »übersetzen« die von den User*innen eingegebenen Codezeilen einer Programmiersprache in Nullen und Einsen, also in eine Sprache, die die Maschinen tatsächlich »verstehen« können. Ein Synthetisierungswerkzeug übersetzt aber nicht, sondern verbindet die Bauteile gemäß der Anweisung der Designer*innen auf dem FPGA so, dass die Daten erstens in der richtigen Reihenfolge abgearbeitet werden, zweitens die Fläche, die auf dem FPGA genutzt werden muss, möglichst minimiert wird und drittens die Route möglichst kurz ist. Das alles soll die Effizienz, Leistungsfähigkeit und auch die Wirtschaftlichkeit eines FPGA gewährleisten.

Im Kern muss ein Synthetisierungswerkzeug also eine ähnliche Aufgabe übernehmen, wie das im Traveling Salesperson Problem beschrieben ist. Aber die Aufgabe ist eben so kompliziert, dass aus dem Traveling Salesperson Problem ein hochkomplexes Problem der quadratischen Zuweisung wird. Und das ist – wie beschrieben – nicht optimal lösbar. Man müsste sich eigentlich also mit einer Annäherung an die Beste aller Möglichkeiten begnügen.

Es sei denn, man sprich mit Expert*innen des Verbundprojekts QuantumQAP, an dem neben der Quantum Brilliance GmbH und der Thales Deutschland GmbH auch das Fraunhofer SCAI mit Thomas Soddemann als Projektkoordinator beteiligt ist. Denn hier sieht man einer finalen Lösung des QAP (also der Quadratic Assignment Procedure oder auf deutsch des »quadratischen Zuordnungsproblems«) sehr optimistisch entgegen: »Wir gehen davon aus, dass wir einen hybriden Algorithmus zur Lösung von QAPs entwickeln können, der sowohl Quantencomputing als auch digitales Computing nutzt«, sagt Soddemann. Genutzt für die Forschungen werden solle dafür einerseits die Quantum Computing Technologie von Quantum Brilliance, die auf Entwicklungen des Fraunhofer-Instituts für Angewandte Festkörperphysik IAF und der Australian National University basiert. Und andererseits »natürlich« auch der Quantencomputer Quantum System One von Fraunhofer und IBM.

Sinnvoll oder je nach Forscher*innen-Einschätzung zwingend nötig sind solche hybriden Algorithmen zur Lösung von QAPs aber nicht nur zum Effizienzgewinn durch kurze Wege, sondern beispielsweise auch zur sicheren Kommunikation. Denn künftige, leistungsfähige Quantencomputer werden in der Lage sein, die aktuell verwendeten (und noch sicheren) Verschlüsselungsalgorithmen problemlos und de facto sogar in Echtzeit zu knacken. Ein mit der Unterstützung eines entsprechenden Synthetisierungswerkzeugs entwickelter und produzierter FPGA könnte dem einen Riegel vorschieben. Auch deshalb – so die Erwartung der Projektbeteiligten - könnte die Möglichkeit, dann sogenannte Postquantum-Kryptographie-Algorithmen produktiv zu nutzen, zu einem beispielhaften Leuchtturm-Ergebnis des Projekts »QuantumQAP« werden.

Postquantum-Kryptographie-Algorithmen

Doch auch dieses Anwendungsszenario ist nicht einfach zu erklären. Thomas Soddemann macht es so: »Heutige Algorithmen basieren auf einer extrem großen Zahl n, die das Produkt von zwei Primzahlen ist. Die Kenntnis der beiden Primzahlen ermöglicht es, Nachrichten sicher zu entschlüsseln oder digital zu unterschreiben. Allerdings könnte der Shor-Algorithmus die Sicherheit dieser Form der Verschlüsselung künftig aushebeln. Denn mit seiner Hilfe wird es möglich, einen Primfaktor dieser Zahl n zu finden. Damit wären dann beide Faktoren bekannt und die Verschlüsselung ist wertlos. Noch aber benötigt dieser Algorithmus leistungsfähige Quantencomputer, die noch nicht existieren, die es aber mit hoher Wahrscheinlichkeit in zehn bis 15 Jahren geben wird.«

Forscher*innen verschiedener Fraunhofer Institute setzen deshalb auf den Einsatz Postquantum-Kryptographie-Algorithmen, also von Verschlüsselungsalgorithmen, die mit Quantencomputern nicht angreifbar sind. Eines der zentralen Probleme dabei: Diese Algorithmen sind komplexer als die aktuell eingesetzten. Deshalb benötigen sie auch mehr Rechenzeit. Ein, mithilfe eines Synthetisierungswerkzeugs intelligent und mit maximal kurzen Routen zwischen den einzelnen Bauteilen produzierter, FPGA aber könnte zumindest einen Zwischenschritt darstellen, um der gewünschten Implementierung von Postquantum-Kryptographie-Algorithmen ein bedeutendes Stück näherzukommen. »Je komplexer das Programm, desto länger die Zeit, bis ein Test auf einem FPGA durchgeführt werden kann. Mit einem hybriden QuantumQAP Löser im Synthetisierungswerkzeug, der einen zeithungrigen Teil des Übersetzungsvorgangs erheblich beschleunigt, würden die Entwickler und Entwicklerinnen in die Lage versetzt, wesentlich effizienter zu arbeiten. Die Time-to-Market für das komplette Produkt würde erheblich verkürzt werden, was wiederum einen positiven Effekt auf den Marktanteil haben sollte«, sagt Soddemann. Deshalb sei die Arbeit mit Postquantum-Kryptographie-Algorithmen einer der zentralen (Test-) Use-Cases im Projekt QuantumQAP. Denn wenn, so die Hoffnung der Forscher*innen Prototypen für diese und einige weitere Anwendungsszenarien erfolgreich abgeschlossen sind, dann stünde einem deutlich effektiverem FPGA kaum noch etwas im Weg.

Ob sich die Erkenntnisse rund um die Transport- und Routenoptimierung dann aber nicht nur auf die Chip-Produktion, sondern auch auf einem optimierten und schnellen Post- und Paketversand auswirken, ist aktuell noch eher unwahrscheinlich. Die Leser*innen dieses Artikels werden also auch weiterhin länger auf ihre Zustellungen warten müssen, als es – rein mathematisch – nötig ist. Zeit genug also, um weiter nachzudenken. Beispielsweise über das Traveling Salesperson Problem.

(aku)