Münster 1999 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Dynamik und Statistische Physik
DY 37: Allgemeine Statistische Physik II
DY 37.1: Vortrag
Mittwoch, 24. März 1999, 17:00–17:15, R1
Record Breaking Optimization Results – Using the Ruin & Recreate Principle — •Johannes Schneider1, Gerhard Schrimpf2, Hermann Stamm-Wilbrandt2, Ingo Morgenstern1, and Gunter Dueck2 — 1Institut für Theoretische Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — 2IBM Scientific Center Heidelberg, Vangerowstr. 18, D-69115 Heidelberg, Germany
A new optimization principle is presented. Solutions of problems are partly, but significantly, ruined or destroyed and rebuilt or recreated afterwards. Performing this type of change frequently, one can obtain astounding results for classical optimization problems. The new method is particularly suited for more complex optimization problems (“discontinuous” ones, problems with hard-to-find admissible solutions, problems with complex objectives or many constraints). The method is an all-purpose-heuristic. Numerical results are given for the Traveling Salesman Problem and for the Vehicle Routing Problem with Time Windows. Numerical evidence for the quality of the proposed principle is given. For most of the instances of a research library of problems, the R&R implementation achieved the best published results. For many instances, better or much better solutions could be found.