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.