N2N: Parallel-Framework beschleunigt MILP-Lösungen auf verteilten Systemen

Parallelisierung gilt als vielversprechender Ansatz, um Mixed-Integer‑Linear‑Programming‑Probleme (MILP) schneller zu lösen. Die Komplexität des Branch‑and‑Bound‑Frameworks und die Vielzahl effektiver Algorithmen in bestehenden Solvern erschweren jedoch eine effiziente Parallelisierung. Das neue Framework N2N (Node‑to‑Node) löst dieses Problem, indem es B‑B‑Knoten gezielt auf verteilte Rechenknoten verteilt.

N2N unterstützt sowohl deterministische als auch nichtdeterministische Modi. Im deterministischen Modus sorgt ein neu entwickelter Sliding‑Window‑Algorithmus dafür, dass Aufgaben in einer festgelegten Reihenfolge erzeugt und gelöst werden. Zusätzlich nutzt das System fortschrittliche Techniken wie Constraint‑Programming‑Suche, allgemeine Primärheuristiken und adaptive Lösungsstrategien, um die Rechenressourcen optimal auszuschöpfen. Durch gezielte Optimierung der Datenkommunikation wird die Effizienz weiter gesteigert.

Der Open‑Source‑Solver SCIP wurde als Basis in N2N integriert, wodurch N2N‑SCIP entsteht. Umfangreiche Tests zeigen, dass N2N‑SCIP im nichtdeterministischen Modus mit 1.000 MPI‑Prozessen auf Kunpeng‑ und x86‑Clustern Beschleunigungen von 22,52 bzw. 12,71 erzielt – das sind 1,98‑ bzw. 2,08‑mal schneller als der aktuelle Spitzenreiter ParaSCIP. Diese Ergebnisse unterstreichen das enorme Potenzial von N2N für die Lösung großer MILP‑Probleme in verteilten Speicherumgebungen.