Neues Lernverfahren steigert Branching-Genauigkeit bei MILP-Optimierung

Die Optimierung von Mixed Integer Linear Programming (MILP) bleibt ein zentrales Problem in Forschung und Praxis. Durch den Branch-and-Bound-Ansatz werden MILPs gelöst, wobei die Auswahl des Branching-Knotens entscheidend für die Laufzeit ist. Neu entwickelte neuronale Lernframeworks verbessern diese Auswahl, stoßen jedoch noch immer an Grenzen: semantische Unterschiede zwischen Knoten auf unterschiedlichen Tiefen, ein Mangel an Daten an oberen Knoten und der hohe Aufwand für starke Branching-Beispiele.

Um diese Herausforderungen zu überwinden, stellt das Team ein neues Verfahren vor: Dynamisches stratifiziertes kontrastives Lernen für MILP-Branching. Das System gruppiert Knoten anhand ihrer Merkmalsverteilungen und trainiert ein Graph-Convolutional-Neuronales Netzwerk, das die Knoten schrittweise voneinander trennt. Gleichzeitig wird ein Upstream-Daten-Augmentation-Ansatz eingesetzt, der theoretisch äquivalente und leicht veränderte MILP-Instanzen erzeugt, um Datenknappheit und Ungleichgewicht an oberen Knoten zu kompensieren.

Ergebnisse aus umfangreichen Tests an Standard-MILP-Benchmarks zeigen, dass das Verfahren die Branching-Genauigkeit deutlich steigert, die Lösungszeit verkürzt und sich zuverlässig auf bisher unbekannte Instanzen überträgt. Damit eröffnet es neue Möglichkeiten, MILP-Probleme effizienter zu lösen und die Grenzen neuronaler Branching-Strategien zu erweitern.