Der Handlungsreisende in der Physik
Die Physiker der Universität erhielten eine großzügige Spende der Computer-Industrie. Mit Hard- und Software im Wert von 95000 DM unterstützt die Firma Sun Microsystems (Palo Alto, Kalifornien) ein Forschungsprojekt am Institut für Theoretische Physik. Thema des Projektes ist die detaillierte Untersuchung von kombinatorischen Optimierungsproblemen, die sowohl in der Grundlagenforschung als auch in industriellen Anwendungen eine große Rolle spielen.
Das bekannteste Problem in der kombinatorischen Optimierung ist das Problem des Handlungsreisenden, der seine Rundreise durch eine Anzahl von Städten so planen möchte, daß die dabei zurückgelegte Strecke möglichst kurz ist. Höchst praxisnah, schnell formuliert und scheinbar harmlos, ist diese Problem schon für ein paar hundert Städte so schwierig, daß auch die schnellsten Supercomputer viele Stunden nach der optimalen Lösung suchen müssen. Die benötigte Rechenzeit wächst mit der Anzahl der Städte so schnell an, daß Probleme mit mehreren tausend Städten als unlösbar gelten.
Trotz jahrzehntelanger, intensiver Bemühungen, hat man bis heute weder für das Problem des Handlungsreisenden noch für viele verwandte Optimierungsprobleme effiziente Lösungen gefunden. Die Physiker machen sich nun eine überraschende Ähnlichkeit zwischen Optimierungsproblemen und physikalischen Systemen wie Gläsern oder magnetischen Legierungen zunutze. Die physikalische Herangehensweise liefert eine tiefere Einsicht in die Struktur dieser Optimierungsprobleme, aber auch verbesserte Lösungsverfahren.
Wie in der Physik üblich werden die theoretischen Untersuchnungen durch Experimente ergänzt. Das Labor ist der Computer. Viele große Beispielprobleme müssen numerisch gelöst werden, um die typischen Eigenschaften eines Problems zu messen und mit den Vorhersagen der Theorie zu vergleichen. Die interessanten Probleme aber sind gerade die, die nur mit sehr viel Computereinsatz zu lösen sind. Die Magdeburger Physiker haben daher ihre vorhandenen Computer zu einem leistungsfähigen Parallelrechner zusammengeschaltet. Mit der Spende der Firma Sun wird dieser Rechnerverbund um zwei schnelle Maschinen verstärkt, und die gespendete Software unterstützt den Betrieb vernetzter Computer als Parallelrechner.
Die Zusammenarbeit von Informatikern, Mathematikern und Physikern auf dem Gebiet der kombinatorischen Optimierung steckt noch in den Kinderschuhen, aber es fanden bereits die ersten interdisziplinären Konferenzen statt. Weltweit entstehen Forschergruppen, die alte Probleme mit den neuen Methoden angehen. Die Magdeburger Forscher möchten ihre vorhandene Rechnerleistung zur Lösung großer kombinatorischer Optimierungsprobleme diesen Forschergruppen über das Internet zur Verfügung stellen.