Maschinelles Lernen in Branch-Price-and-Cut-Algorithmen für Tourenplanungsprobleme

• Antragsteller: Professor Dr. Christian Tilk
• Fachliche Zuordnung: Management und Marketing
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 503190360

Das Projekt MaLeBPCTop untersucht die Integration von maschinellem Lernen in Verfahren des Operations Research zur Lösung kombinatorischer Optimierungsprobleme. Die Kernfrage ist, auf welche Weise maschinelles Lernen in Operations Research Algorithmen eingesetzt werden kann, denn kombinatorische Optimierungsprobleme unterscheiden sich stark von den meisten Problemen, die aktuell durch maschinelles Lernen gelöst werden.Der Fokus des Projekts liegt auf der exakten Lösung von Tourenplanungsproblemen mittels einer Kombination von maschinellem Lernen und Branch-Price-and-Cut (BPC). BPC ist eine der führenden Methoden zum exakten Lösen von Tourenplanungsproblemen. Es ist ein Branch-and-Bound-Verfahren, in dem jeder Branch-and-Bound-Knoten per Column-Generation gelöst wird. In BPC-Algorithmen werden einige algorithmische Entscheidungen nach dem „Greedy-Prinzip“ oder nach „Best Practice“ getroffen. Die zentrale Hypothese des Projekts MaLeBPCTop ist, dass durch die Verwendung bekannter Algorithmen des maschinellen Lernens algorithmische Komponenten durch Lernen aus zuvor gelösten Probleminstanzen konfiguriert werden können, um bessere Entscheidungen zu treffen. Ziel ist es, effektivere BPC-Algorithmen zu entwerfen, indem ausgewählte algorithmische Entscheidungen erlernt werden und gleichzeitig die Exaktheit des BPC Algorithmus erhalten bleibt.Die Bewertung einer getroffenen Entscheidung im BPC ist schwierig, selbst im Nachhinein, wenn die Instanz bereits mit BPC optimal gelöst wurde. Natürlich kann der BPC-Algorithmus mehrmals ausgeführt und jeweils verschiedene Konfigurationen für eine algorithmische Entscheidung benutzt werden, um (im Nachhinein) eine beste Entscheidung festzulegen. Für die meisten zu erlernenden algorithmischen Entscheidungen führt hohe Dimensionalität sowie wiederkehrendes Auftreten allerdings dazu, dass die sehr hohe Anzahl an notwendigen BPC-Läufen rechnerisch viel zu aufwendig ist. Daher werden im Projekt MaLeBPCTop verschiedene Strategien zur Festlegung einer zu erlernenden Entscheidung untersucht. Es werden sowohl algorithmische Entscheidungen des Masterproblems als auch Entscheidungen zur Lösung des Pricing Problems untersucht. Neben klassischen Lernverfahren wie Random Forests, werden auch Deep-Learning Verfahren basierend auf Graph Neural Networks eingesetzt. Um die Verwendung maschinellen Lernens zu beurteilen, gibt es in exakten Algorithmen wie BPC vorrangig nur ein Kriterium: Die Lösungszeit. Daher findet die zeitintensive Trainings- und Testphase der Lernalgorithmen immer außerhalb des BPC-Algorithmus statt.

• DFG-Verfahren: Sachbeihilfen