DPG Phi
Verhandlungen
Verhandlungen
DPG

Münster 1999 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 37: Allgemeine Statistische Physik II

DY 37.1: Talk

Wednesday, March 24, 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 Dueck21Institut 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.

100% | Mobile Layout | Deutsche Version | Contact/Imprint/Privacy
DPG-Physik > DPG-Verhandlungen > 1999 > Münster