Combinatorial Optimization as a Means for Studying Theoretical Physics Problems

• Applicant: Professorin Dr. Frauke Liers
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 35142532

Seit dem 30.11.2006 leite ich eine Nachwuchsgruppe, in der wir zusammen mit zwei Mitarbeitern, einer studentischen Hilfskraft und Diplomand/inn/en Algorithmen zur Lösung relevanter Probleme in der theoretischen Physik entwickeln, implementieren und verbessern. Zusammen mit Kolleg/inn/en aus der theoretischen Physik analysieren wir die mit den Algorithmen erzeugten Resultate. In der Erstantragstellung habe ich Personal- und Reisekosten beantragt, die von der DFG auch genehmigt wurden. Zum Zeitpunkt der Erst anträgst eilung war für mich leider nicht abzusehen, dass es für die Arbeit der Gruppe notwendig ist, weitere Hardware zu Verfügung zu haben. Das möchte ich im Folgenden begründen. Die für uns interessanten Probleminstanzen sind häufig durch Wahrscheinlichkeitsverteilungen bestimmt. Um verläßliche Aussagen über die dem System zugrundeliegende Physik treffen zu können, muss man der Wahrscheinlichkeitsverteilung gemäß viele Realisierungen des Systems erzeugen, das dem System zugeordnete Problem algorithmisch lösen und die Mittelwerte der Ergebnisse analysieren. Je größer die Stichprobe und je größer die gelösten Systeme, desto aussagekräftiger sind die Ergebnisse. In den aktuellen Veröffentlichungen von Physikern werden in diesem Gebiet bis zu einer zweistelligen Zahl an CPU-Jahren investiert, gerechnet auf großen Compute-Clustern in physikalischen Instituten. Beispielhaft seien hierfür die neueren Arbeiten von .A.K. Hartmann, H. Katzgraber, und A.P. Young, genannt [HOO], [KY03] und [LY07]. Bei der Grundzustandsbestimmung von Spingläsern in verschiedenen Modellen ist meines Wissens nach unser exaktes Verfahren deutlich schneller als gute heuristische, solange die Instanzgrößen in vernünftiger Zeit eine exakte Lösung erlauben. Aber auch hier werden für die Erstellung einer guten Stichprobe mehrere CPU-Monate Rechenzeit benötigt, siehe zum Beispiel [LM07] und [LLMPV07]. Innerhalb eines Branch-and-Cut Algorithmus werden viele linearen Programme (LP) gelöst. Die zur Zeit schnellsten Löser für LPs sind in der kommerziellen Bibliothek CPLEX [CPLEX] implementiert. Bisher habe ich die Ergebnisse vor allem auf dem Linuxcluster cliot des Rechenzentrums in Köln berechnet (128 Knoten, je 2 Prozessoren), und einige Berechnungen auf dem Cluster der Gruppe von Prof. E. Speckenmeyer durchgeführt (5 Knoten, je 2 Prozessoren). In der Gruppe von Prof. M. Jünger, der unserer Gruppe die Grundausstattung zu Verfügung stellt, gibt es außer den Arbeitsplatzrechnern keine Compute-Knoten. Auch der Spinglas-Server läuft auf den Arbeitsplatzrechnern. Es wird von der AG Jünger mittelfristig keine neue Hardware in größerem Umfang angeschafft, da ihr Bedarf an Compute-Knoten eher gering ist und es dort nicht zu Engpässen kommt. Vor und zur Zeit der Antragstellung konnte ich das Cluster im Rechenzentrum gut nutzen, da es relativ wenige Nutzer aufwies. Mittlerweile wird cliot jedoch viel benutzt. Vor allem für die Berechnungen in [LLMPV07] mußte ich mehrmals mehrere Tage warten, bevor einer der ca. 30 Jobs startete. Aller Voraussicht nach wird die Auslastung von cliot in Zukunft nicht geringer werden, sondern im Zweifelsfall weiter steigen. Da das Cluster im universitätsweiten Service angeboten wird, kann man unserer Gruppe verständlicherweise keine speziellen Nutzungsrechte einräumen. Mittelfristig werden auch meine beiden Mitarbeiter steigenden Bedarf an Rechenkapazitäten haben. Bei Ausweitung des Spinglas-Servers für andere physikalische Problemstellungen steigt der Bedarf nochmals.

• DFG Programme: Independent Junior Research Groups