Mathematik, Arbeitsrichtung Diskrete Optimierung
Mathematik, Arbeitsrichtung Diskrete Optimierung

Flow-Preserving Graph Contractions

MATH+ Kennung
AA3-4

Projektleitung
Max Klimm, Torsten Mütze, Guillaume Sagnol, Martin Skutella

Beteiligt
Frieder Smolny, Philipp Warode

Zeitraum
Januar 2019 – Dezember 2021

Projektbeschreibung

Logistiknetzwerke wachsen fortlaufend in Größe und Komplexität, was tradionelle Optimierungsansätze ineffizient werden lässt. Wir untersuchen ein Kontraktionsframework, welches die Netzwerke, auch bei dynamischen Änderungen, auf handhabare Größen reduziert und dabei weiterhin die Beförderung von Gütern zu gegebenen Kosten ermöglicht.

Netzwerke sind ein fundamentales Werkzeug um Daten zu repräsentieren, zu organisieren und zu verarbeiten. In den letzten Jahren fordern zwei neuartige Trends tradionelle Methoden der Netzwerkoptimierung neu heraus. Einerseits wächst die Menge der zu verarbeitenden Daten fortwährend an, sodass Speicherkapazitäten normaler Computer überschritten werden. Andererseits macht die fortschreitende Diversität der verfügbaren Arten von Daten in Netzwerken die direkte Anwendung von standardisierten Lösungen unmöglich. Exemplarisch für diese Entwicklungen sind Logistiknetzwerke, in denen die Komplexität aus drei verschiedenen, unabhängigen Entwicklungen entsteht.

Erstens sorgt die wachsende Nachfrage für individuelle Lieferungen für einen Zuwachs von Direktverbindungen in Netzwerken. Zweitens wird die Menge und die Arten von verfügbaren Daten durch das stetige Sammeln von Sensordaten, die die Verarbeitung und Lieferzeiten von verschickten Gütern überwachen, massiv erhöht. Drittens schlägt sich der hohe Konkurrenzdruck der Logistikbranche in komplexen Preisstrukturen nieder, welche sich nur schwer in mathematischen Modellen darstellen lassen.

In diesem Projekt wollen wir diese Herausforderungen mittels Netzwerkkontraktionen lösen. Die grundlegende Idee hinter Netzwerkkontraktionen ist, passende Approximationen der zugrundeliegenden Netzwerkstrukturen algorithmisch zu bestimmen, die eine geringere Komplexität aufweisen. Dann wird das vorliegende Optimierungsproblem für das kontrahierte Netzwerk gelöst. Schließlich wird die Teillösung für das kleinere Netzwerk auf das gesamte Netzwerk ausgeweitet. Im Gegensatz zu bisherigen Methoden zur Ausdünnung von Graphen (engl. graph sparsification), die sich auf die Erhaltung von Entfernungen (spanners) oder Schnitten (spectral sparsifiers) beschränkten, zielt dieses Projekt darauf ab, komplexere Strukturen des Graphs zu erhalten.

Ausgewählte Veröffentlichungen

  • Travelling on Graphs with Small Highway Dimension (Y. Disser, A. E. Feldmann, M. Klimm, and J. Koenemann)
    Proc. 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 175-189, 2019.
  • Distance-Preserving Graph Contractions (A. Bernstein, K. Däubel, Y. Disser, M. Klimm, T. Mütze and F. Smolny)
    SIAM J. Discrete Math. 33(3): 1607-1636, 2019
  • The cone of flow matrices: Approximation hierarchies and applications (G. Sagnol, M. Blanco and T. Sauvage)
    Networks 72(1):128-150, 2018