Forge: Neue Methode nutzt Graph-Embeddings zur Optimierung von MIP-Problemen

Forscher haben mit dem neuen Ansatz Forge einen Weg gefunden, die Lösung von kombinatorischen Optimierungsproblemen zu beschleunigen, ohne dabei auf aufwendige Trainingsdatensätze angewiesen zu sein. Durch das Vortrainieren eines vektorquantisierten Graph-Autoencoders auf einer großen, vielfältigen Sammlung von Mixed-Integer-Programming (MIP)-Instanzen kann Forge ein diskretes Vokabular aus Codezuweisungen erzeugen, das jede Optimierungsinstanz präzise beschreibt.

Im unsupervised Setting zeigt Forge, dass die erzeugten Embeddings unterschiedliche Probleminstanzen effektiv voneinander trennen und in sinnvolle Cluster gruppieren. Für das supervised Setting werden die Embeddings feinjustiert, sodass ein einzelnes Modell gleichzeitig die Warm-Start-Variablen und die Integrality-Gaps für die Cut‑Generation vorhersagen kann. Diese beiden Vorhersagen führen zu einer spürbaren Leistungssteigerung bei einem führenden, kommerziellen Optimierungs-Solver.

Die Autoren stellen den Code sowie die vortrainierten Forge‑Gewichte frei, um weitere Forschung und praktische Anwendungen von MIP‑Embeddings auf Instanzebene zu fördern. Das Projekt ist unter https://github.com/skadio/forge/ verfügbar.