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

• Final Report Year: 2014

Final Report Abstract

Wichtige Fragestellungen bei ungeordneten Systemen in der theoretischen Physik sind nicht vollständig verstanden. Eine Analyse ihrer energieminimalen Zustande (Grundzustände) gibt jedoch Hinweise auf die zu Grunde liegende Physik. Während in der Physikliteratur häufig heuristische Methoden zur Bestimmung von Grundzuständen genutzt werden, wurden im COPhy-Projekt im Gegensatz dazu beweisbar exakte Lösungsmethoden erforscht und implementiert. Exakte Grundzustände erlauben dabei verlässlichere physikalische Analysen als heuristisch erzeugte. Im Rahmen des Projekts wurde darauf fokussiert, moderne Läsungsalgorithmen zu entwickeln, sie auf relevante physikalische Problemstellungen anzuwenden und sie öffentlich zugänglich zu machen. Es wurden sowohl Veröffentlichungen in Informatik- und Mathematikjournalen, als auch in Physikjournalen erzielt. Der Fokus lag auf Spinglasern und Potts Gläsern, deren Grundzustände sich über unterschiedliche Partitionierungsprobleme in verschiedenen Graphenklassen berechnen lassen. Einige Problemstellungen sind polynomial lösbar, andere NP-schwer. Zur Entwicklung effizienter Verfahren wurden graphentheoretische Methoden sowie polyedrische Kombinatorik genutzt. Es wurden darüber hinaus neue allgemeine Optimierungsmethoden erforscht. Die Algorithmen wurden unter Algorithm Engineering Gesichtspunkten implementiert. Für die im Antrag vorgestellten Optimierungsprobleme wurden exakte Verfahren entworfen, die oft den state-of-the-art in diesem Gebiet darstellen. Wenn möglich, wurden die Methoden auch für Problemstellungen außerhalb der Physik erweitert und genutzt. Darüber hinaus gelang die Erweiterung der Methoden für die Klasse binär quadratischer Optimierungsprobleme. Unter anderem wurden exakte Algorithmen entwickelt für maximale Schnitte in planaren Graphen, für maximale Flüsse, minimale Kostenflüsse und spezielle submodulare Funktionen (optimales Kooperationsproblem). Für verschiedene NP-schwierige Probleme wurden exakte Branch-and-Bound und Branch-and-Cut Methoden entwickelt und implementiert, insbesondere für maximale k-Schnitte, maximale Equi-Schnitte und optimale Lösungen für das Bernasconimodell. Einige der für die Physikanwendungen erforschten Methoden wurden für Anwendungen in anderen Bereichen genutzt und zu Lösungsverfahren fär binar quadratische Optimierungsprobleme verallgemeinert, wobei sowohl spezifische als auch allgemeine Lösungsmethoden entwickelt und angewandt wurden. Die Physikanwendungen wurden mit Hilfe der neuen Verfahren und Programme studiert. Die Methoden wurden Physikern über Kooperationen zugänglich gemacht. Darüber hinaus wurde insbesondere der Kölner Spinglas-Server grundlegend modernisiert und erweitert. Mittlerweile können unterschiedliche Problemstellungen gelöst werden und benutzerfreundlich weitere Programme zur Lösung anderer Problemstellungen dazugeschaltet werden. Zudem wurde ein wiki web erstellt, in dem die zum Verständnis der Verfahren notwendigen Begriffe, Algorithmen und Grundlagen für interessierte Kolleg/inn/en aus der Physik zusammengefasst und aufbereitet sind.

Publications

• (2007) Magnetic exponents of two-dimensional spin glasses. Physical Review B Vol. 76 (6). 060405
  F. Liers, O.C. Martin
  
• (2007) Zero-temperature behavior of the random-anisotropy model in the strong-anisotropy limit. Physical Review B Vol. 76 (17). 74423
  F. Liers, J. Lukic, E. Marinari, A. Pelissetto, E. Vicari
  
• (2008) Exact ground states of large two-dimensional planar Ising spin glasses. Physical Review E Vol. 78 (5). 056705
  G. Pardella, F. Liers
  
• (2008) Local Cuts Revisited. Operations Research Letters Vol. 36 (4). S. 430-433
  C. Buchheim F. Liers, M. Oswald
  
• (2010) A Fast Exact Algorithm for the Problem of Optimum Cooperation and the Structure of Its Solutions. Journal of Combinatorial Optimization Vol. 19 (3). S. 369-393
  D. Fanghänel, F. Liers
  
• (2010) Exact Bipartite Crossing Minimization under Tree Constraints. 9th International Symposium on Experimental Algorithms SEA 2010, Lecture Notes in Computer Science. 6049 Springer Verlag 2010, S. 118-128
  F. Baumann, C. Buchheim, F. Liers
  
• (2010) Speeding up IP-based Algorithms for Constrained Quadratic 0-1 Optimization. Mathematical Programming B Vol. 124 (1-2). S. 513-535
  C. Buchheim, F. Liers, M. Oswald
  
• (2011) Simplifying maximum flow computations: the effect of shrinking and good initial flows. Discrete Applied Mathematics Vol. 159 (17). S. 2187 - 2203
  F. Liers, G. Pardella
  
• (2012) Partitioning planar graphs: a fast combinatorial approach for max-cut. Computational Optimization and Applications. S. 323-344
  F. Liers, G. Pardella
  
• (2013) Engineering Branch-and- Cut Algorithms for the Equicut Problem. Discrete Geometry and Optimization, Fields Institute Communications Vol. 69 Springer 2013, S. 17-32
  M.F. Anjos, F. Liers, G. Pardella, A. Schmutzer