Schnelleres MIP‑Lösen dank sparsiger Lernmodelle für Branching

Ein neues Papier von arXiv zeigt, wie Mixed‑Integer‑Programming‑Solver schneller werden können, indem sparsere Lernmodelle für das Branching eingesetzt werden.

Machine Learning wird zunehmend genutzt, um Entscheidungen im Branch‑and‑Bound‑Algorithmus zu optimieren. Die meisten Ansätze basieren auf tiefen neuronalen Netzen, die große Trainingsdatensätze und GPU‑Ressourcen erfordern.

Die Autoren verfolgen einen anderen Weg: Sie entwickeln leichtgewichtige, interpretierbare Modelle, die starke Branching‑Scores nachbilden. Durch sparsames Lernen bauen sie Modelle mit weniger als 4 % der Parameter eines führenden Graph‑Neural‑Networks.

Trotz der geringen Parameterzahl erreichen die CPU‑basierten Modelle eine vergleichbare Genauigkeit und sind schneller als der Standard‑Solver von SCIP sowie als das GPU‑beschleunigte GNN.

Die Modelle lassen sich einfach trainieren und einsetzen und bleiben auch bei kleinen Trainingsmengen leistungsfähig – ein großer Vorteil in ressourcenarmen Umgebungen.

Umfangreiche Tests an verschiedenen Problemklassen zeigen, dass dieser Ansatz die Effizienz von MIP‑Lösungen deutlich steigert und damit einen praktischen Mehrwert für die Praxis bietet.