[Diese Seite ist derzeit noch in Bearbeitung und wird nach und nach ergänzt.]
CG:SHOP ist ein Forschungsprojekt zur Entwicklung neuer Methoden für schwierige geometrische Optimierungsprobleme. Das Projekt wird seit 2020 unter Federführung der Technischen Universität Braunschweig und in Zusammenarbeit mit verschiedenen internationalen Kooperationspartnern durchgeführt, wobei die erste Förderphase bereits erfolgreich abgeschlossen wurde. Derzeit befindet sich CG:SHOP unter Förderung der Deutschen Forschungsgemeinschaft in der zweiten Förderphase. Ziel des Projekts ist es, theoretische Ansätze der Computational Geometry mit praktischen Methoden aus dem Algorithm Engineering zu verbinden, um leistungsfähige Verfahren für reale Problemgrößen zu entwickeln.
Neben den ursprünglichen Forschungszielen wurde im Rahmen der ersten Förderphase außerdem die jährlich stattfindende CG:SHOP Challenge ins Leben gerufen, ein internationaler Wettbewerb, in dem ausgewählte geometrische Optimierungsprobleme bereitgestellt werden und Forschungsteams neue algorithmische Lösungsansätze entwickeln und praktisch evaluieren. Weitere Informationen zur CG:SHOP Challenge können der offiziellen Internetseite entnommen werden.
Ein Forschungsschwerpunkt im Bereich der geometrischen Strukturprobleme beschäftigte sich mit der Polygonisierung von Punktmengen. Dabei ging es darum, aus einer gegebenen Menge von Punkten ein einfaches Polygon zu konstruieren, welches alle Punkte als Eckpunkte umfasst und bestimmte Optimierungskriterien erfüllt, wie entweder den Flächeninhalt maximiert (MAX-AREA) oder minimiert (MIN-AREA). S. P. Fekete et al. führten eine systematische Untersuchung verschiedener exakter Lösungsverfahren für das MIN-AREA und MAX-AREA Problem durch. Dafür wurden insbesondere zwei unterschiedliche ganzzahlige Optimierungsmodelle, zum einen eine kantenbasierte und eine triangulationsbasierte Formulierung, entwickelt und miteinander verglichen.
S. P. Fekete et al. konnten mithilfe der verbesserten Formulierungen gegenüber bisherigen Ansätzen eine größere Zahl von Instanzen optimal lösen. Zusätzlich verdeutlichten ihre Ergebnisse, dass Polygonisierungsprobleme wie MIN-AREA und MAX-AREA praktisch anspruchsvoller sind als klassische Optimierungsprobleme wie beispielsweise das euklidische Traveling-Salesman-Problem.
Ein weiterer Forschungsschwerpunkt im Bereich der Touringprobleme war das Lawn-Mowing-Problem. Dabei wird für eine durch ein Polygon beschränte Region eine möglichst kurze Rundtour gesucht, sodass jeder beliebige Punkt in dieser Region innerhalb eines vorgegebenen Maximalabstands von der Tour liegt. Intuitiv lässt sich dies so verstehen, dass sich entlang der Tour eine Kreisscheibe mit diesem Maximalabstand als Radius bewegt und dabei jeder Punkt der Region mindestens einmal von dieser Kreisscheibe überdeckt wird. Dieses Problem verallgemeinert mehrere bekannte geometrische Optimierungsprobleme und tritt in zahlreichen praktischen Anwendungen auf, etwa in der Robotik oder in Fertigungsprozessen.
S. P. Fekete et al. konnten mit ihrer Arbeit zum Lawn-Mowing-Problem, welche mit dem Best Paper Award der ALENEX 2023 ausgezeichnet wurde, weitreichende Ergebnisse erzielen. Sie zeigten zunächst, dass optimale Rundtouren stets aus einem Kantenzug mit endlich vielen Knotenpunkten bestehen. Damit können beliebig viele Punkte innerhalb der abzudeckenden Region durch eine endliche Menge von Knotenpunkten repräsentiert werden, was den Lösungsraum erheblich einschränkt und die Grundlage für algorithmische Ansätze schafft.
Zusätzlich entwickelten sie einen Primal-Dual-Algorithmus, der iterativ eine initiale, endliche Menge von „Witness Points“ erweitert, für diese eine Näherungslösung mittels eines Close-Enough-TSP berechnet und dadurch sowohl eine obere Schranke, also eine zulässige Tour, als auch eine untere Schranke für die optimale Tour liefert. Jede Iteration reduziert den verbleibenden Optimality Gap und ermöglicht so nachweisbar beinahe optimale Lösungen für große Instanzen.
Aufbauend auf den Erfolgen der ersten Förderphase verfolgt CG:SHOP2 das Ziel, neue Methoden für die Berechnung nachweisbar optimaler oder nahezu optimaler Lösungen für eine breite Klasse geometrischer Optimierungsprobleme zu entwickeln. Dabei werden weiterhin konkrete Problemklassen aus der ersten Förderphase, etwa Strukturprobleme, Touringprobleme und Packungsprobleme, untersucht, während gleichzeitig allgemeine algorithmische Werkzeuge und Analysemethoden entwickelt werden.
Eine besondere Initiative, die aus der ersten Förderphase hervorgegangen ist, ist die seit 2019 jährlich stattfindende CG:SHOP Challenge. Dabei handelt es sich um einen internationalen Wettbewerb, in dem jeweils ein schwieriges geometrisches Optimierungsproblem ausgewählt wird. Forschungsteams ebenso wie einzelne Teilnehmer entwickeln dafür neue algorithmische Ansätze und vergleichen ihre Methoden auf gemeinsamen Benchmark-Instanzen. Die CG:SHOP Challenge verbindet dabei theoretische Fragestellungen der Computational Geometry mit praktischer Algorithmik und realistischen Problemgrößen.
Die CG:SHOP Challenge hat sich schnell zu einem wichtigen Treffpunkt der internationalen Forschungscommunity entwickelt. Durch diesen offenen Wettbewerb entstehen neue Datensätze, Implementierungen und algorithmische Ideen, die häufig zu wissenschaftlichen Publikationen führen. Gleichzeitig bietet die Challenge eine Plattform für Nachwuchswissenschaftler, ihre Methoden zu präsentieren und mit etablierten Forschungsteams zu vergleichen.
Prof. Dr. Sándor P. Fekete
Abteilung Algorithmik
Technische Universität Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Telefon: +49 (0)531 391 311 1
Telefax: +49 (0)531 391 310 9
E-Mail: s.fekete@tu-bs.de
Internet: Webseite Prof. Dr. Fekete bei der TU Braunschweig