Seriation : exakte und heuristische Lösungsmethoden

Abstract

Seriation ist der Prozess des Anordnens einer Reihe von Objekten nach Ähnlichkeiten oder Unterschieden. Die Aufgabenstellung ist ein elementarer Bestandteil der Datenanalyse und stellt ein kombinatorisches Optimierungsproblem dar. Die Seriation findet ihre Ursprünge im Bereich der Archäologie, wo Fundstellen und -objekte nach deren Chronologie untersucht werden. Obwohl das Seriationsproblem recht schnell formuliert ist, gestaltet sich die Lösung als äußerst komplex, da die Anzahl der möglichen Anordnungen der Objekte sehr schnell ansteigt und das Lösen damit äußert rechenaufwendig wird. Genau hier setzt das Operations Research mit seiner Vielzahl an exakten und heuristischen Lösungsmethoden an. Es existieren verschiedene OR-Methoden zur Lösung des Seriationsproblems und wir wollen diese Verfahren hinsichtlich Rechenaufwand, Qualität, theoretischem Hintergrund und Verbesserungsmöglichkeiten genau betrachten.<br />

Seriation describes the process of ordering a series of objects by similarity or dissimilarity. This Problem first occured in archaeology, where artifacts have to be ordered by their chronological appearance. Nowadays, Seriation takes part in a wide range of applications and is a basic tool for combinatorial data analysis.<br />Although the problem is simple in its formulation, possible solutions grow rapidly as the number of objects raise, so effective algorithms for solving this NP-hard problem are needed. In this paper some common methods of Operations Research are presented that can be effectively used for Seriation. Alongside exact algorithms some efficient heuristics and two special methods, a hierarchical clustering approach and the formulation of the Seriation Problem as a Traveling Salesman Problem are presented.