Optimierungsalgorithmen in Naturwissenschaft und Industrie: Themenliste

Themenkreis: Anwendungen aus der Physik

1. Grundzustände dreidimensionaler Spingläser und Cluster-exakte Approximation
   • A.K. Hartmann
     Cluster-exact approximation of spin glass ground states
     Physica A 224, 480 (1996)
   • A.K. Hartmann
     Scaling of stiffness energy for 3d +/- J spin glasses
     Phys. Rev. E 59 , 84 (1999)
2. Untersuchung des Phasenraums von Spingläsern mittels eines branch-and-bound Verfahrens
   • A. Hartwig, F. Daske und S. Kobe
     A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models
     Comp. Phys. Commun. 32, 133 (1984)
   • T. Klotz und S. Kobe
     "Valley Structures" in the phase space of a finite 3d Ising spin glass with +-I interactions
     J. Phys. A 27 L95 (1994)
3. Zweidimensionale Random-Bond Modelle: Grundzustände und angeregte Zustände über Matching-Verfahren (Betreuer: Carlo Amoruso)
   • I. Bieche, R. Maynard, R. Rammal, and J.P. Uhry, J. Phys. A 13, 2553 (1980)
   • The stiffness exponent of two-dimensional Ising spin glasses for non-periodic boundary conditions using aspect-ratio scaling,
     A.K. Hartmann, A.J. Bray, A.C. Carter, M.A. Moore, und A.P. Young, Phys. Rev. B 66, 224401 (2002)
   • Corrections to Scaling are Large for Droplets in Two-Dimensional Spin Glasses,
     A.K. Hartmann and M.A. Moore, Phys. Rev. Lett. 90, 127201 (2003)

   Themenkreis: Phasenübergänge in Optimierungsproblemen

4. Phasenübergänge im Erfüllbarkeitsproblem (Betreuer: Martin Weigt )
   • Can't get no satisfaction
     B. Hayes, American Scientist 85 108 (1997)
   • Analytic and Algorithmic Solution of Random Satisfiability Problems
     M. Mézard, G. Parisi and R. Zecchina, Science 297, 812 (2002)
5. Die optimale Bewachung von Museen: ein hartes Problem? (Betreuer: Wolfgang Barthel )
   • The number guards needed by a museum -- a phase transition in vertex covering of random graphs ,
     M. Weigt and A.K. Hartmann, Phys. Rev. Lett. 84, 6118 (2000)
   • The typical-case complexity of a vertex-covering algorithm on finite-connectivity random graphs,
     M. Weigt and A.K. Hartmann, Phys. Rev. Lett. 86, 1658 (2001)
6. Computer-Complexität der Barrierenbewegung
   • A. A. Middleton
     Computational complexity of determining the barriers to interface motion in random systems
     Phys. Rev. E 59, 2571-2577 (1999)

Themenkreis: Anwendungen aus der Biologie/Chemie

7. Atomare/molekulare Systeme und Vergleich von Optimierungsverfahren basierend auf Monte-Carlo Simulationen
   • K.K. Bhattacharya und J.P. Sethna
     Multicanonical Methods vs. Molecular Dynamics vs. Monte Carlo: Comparison for Lennard-Jones Glasses
     Phys. Rev. E 57, 2553 (1998)
   • U.H.E. Hansmann und Y. Okamoto
     Comparative Study of Multicanonical and Simulated Annealing Algorithms in the Protein Folding Problem
     Konrad-Zuse-Zentrum Berlin, Preprint SC 92-20 (1994)
   • S. Kirkpatrick, C.D. Gelatt Jr. und M.P. Vecci
     Optimization by Simulated Annealing
     Science 220, 671 (1983)
8. Stochastische Optimierungsverfahren in der Medikamentenentwicklung (Betreuer: Bernd Burghardt)
   • A review of protein-small molecule docking methods
     R.D. Taylor, P.J. Jewsbury, and J.W. Essex, Journal of Computer-Aided Molecular Design, 16(3), 151-166, (2002)
   • Comparison of stochastic optimization methods for receptor-ligand docking
     H. Merlitz and W. Wenzel, Chem. Phys. Lett., 362(3-4),271-277 (2002)
9. Proteinverleich mittels Alignment und seltene Ereignisse
   • S.B. Needleman and C.D. Wunsch, J. Mol. Biol. 48, 443 (1970)
   • T.F. Smith and M.S. Waterman, J. Mol. Biol. 147, 195 (1981)
   • Sampling rare events: statistics of local sequence alignments,
     A.K. Hartmann, Phys. Rev. E 65, 056102 (2002)

   Themenkreis: Anwendungen aus der Industrie

10. Lösung von Transportproblemen mit dem Simplexverfahren
    • D. Goldfarb und M.J. Todd
      Linear Programming
      in: G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J.Todd: Optimization, North-Holland 1989
    • C.H. Papadimitriou und K. Steiglitz
      Combinatorial Optimization
      Dover Publications, Mineola (New York) 1998
11. Entwurf von elektronischen Komponenten unter Verwendung von Heuristiken
    • M. Jünger, A. Martin, G.Reinelt und R. Weismantel
      Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits
      Math. Prog. 63, 257 (1994)
    • G. Reinelt
      Kombinatorische Optimierung und VLSI-Entwurf
      in: A.Bachem, M.Jünger, R.Schrader: Mathematik in der Praxis 237, Springer Verlag (1995)
12. Entwurf von Stundenplänen mittels genetischer Algorithmen
    • W. Junginger
      Course Scheduling by Genetic Algorithms
      in: J. Biethahn und V. Niessen (Hrsg): Evolutionary Algorithms in Management Applications
    • V. Nissen und J. Biethan
      An Introduction to Evolutionary Algorithms
      in: J. Biethahn und V. Niessen (Hrsg): Evolutionary Algorithms in Management Applications

Allen Vortragenden wird empfohlen auch in der Datenbank INSPEC (nur lokal zugänglich) zu recherchieren. Eine sehr aktuelle Quelle stellt der Preprint-Server dar. Alle dort gespeicherten Artikel lassen sich direkt herunterladen. Allgemeine Informationen und Lehrbücher zu dem Thema finden sich unter:

• A.K. Hartmann und H. Rieger
  Optimization Algorithms in Physics
  Wiley-VCH, Berlin 2001
• C.H. Papadimitriou und K. Steiglitz
  Combinatorial Optimization
  Prentice-Hall 1982
• T.H. Cormen, S. Clifford, C. E. Leiserson, R. L. Rivest
  Introduction to Algorithms
  MIT Press 2001
• D. Jungnickel
  Graphen, Netzwerke und Algorithmen
  BI Wissenschaftsverlag 1994
• H. Rieger
  Frustrated Systems: Ground State Properties via Combinatorial Optimization
  in: J. Kertesz and I. Kondor, Lecture Notes in Physics 501, Springer-Verlag, Heidelberg 1998
• M.R. Garey und D. S. Johnson
  Computers and intractability
  Freeman, New York, 1979