Graduate School in Nonlinear Science

Sponsored by the Danish Research Academy

MIDIT                               OFD                           CATS
Modelling, Nonlinear Dynamics       Optics and Fluid Dynamics     Chaos and Turbulence Studies
and Irreversible Thermodynamics     Risø National Laboratory      Niels Bohr Institute and 
Technical University of Denmark     Building 128                  Department of Chemistry
Building 321                        P.O. Box 49                   University of Copenhagen 
DK-2800 Lyngby                      DK-4000 Roskilde              DK-2100 Copenhagen Ø
Denmark                             Denmark                       Denmark


by Rainer E. Burkard
Technische Universitaet Graz,
Institut fuer Mathematik
Graz, Austria

MIDIT-seminar 452

Friday June 4, 1999, 14.00 h
at MIDIT, IMM Building 321, room 133

Abstract: Combinatorial optimization and thermodynamics seemed to be completely unrelated fields until simulated annealing, a thermodynamic simulation procedure, proved to be so successful for combinatorial optimization problems. Some combinatorial optimization problems, like quadratic assignment problems, are extremely hard to solve by exact methods, but good suboptimal solutions are fast at hand. It will be shown that this strange asymptotic behaviour of some combinatorial optimization problems can be explained by means of the Boltzmann distribution.