Vernetzte Rechner lösen ungeklärtes mathematisches Problem
Forscher der Universität Iowa und Argonne National Laboratory lösen NUG30, ein seit 32 Jahres ungeklärtes mathematisches Optimierungsproblem.
Forscher der Universität Iowa und dem Argonne National Laboratory lösten NUG30, ein seit 32 Jahren ungelöstes mathematisches Optimierierungsproblem. NUG-N ist ein sogenanntes quadratisches Zuweisungsproblem (QAP), bei dem N Produktionsstätten auf N Orte verteilt werden müssen, sodass die Transportkosten zwischen ihnen minimal ausfallen. Es handelt sich dabei nicht um ein rein theoretisches mathematisches Problem – es tritt häufig bei der Planung von Fabriken oder Krankenhäusern auf.
Während sich NUG-N für eine kleine Anzahl N vergleichsweise schnell lösen lässt, haben sich seit 1968 alle Computer die Zähne an NUG30 ausgebissen. Immerhin müssen zur Lösung 30! = 2,7 x 1032 Szenarien durchgerechnet werden – eine Aufgabe, die bei einer Rechenleistung von einem Teraflop immer noch über 100 Mal mehr Zeit in Anspruch nimmt als als das Universum alt ist.
Die Forscher der Universität Iowa und vom Argonne National Laboratory haben die benötigte Rechenzeit durch einen ausgeklügelten Algorithmus auf rund sieben Jahre (bei Verwendung einer einzelnen Workstation) reduziert. Um diese weiter zu minimieren, setzten Sie zeitweise über 1000 durch ein Hochgeschwindigkeitsnetz names Condor verbundene Computer ein, die das Ergebnis in nur einer Woche fanden. (vza)
