Optaplanner - große Datensätze mit Millionen von Zeilen

Question

Es gibt ein paar Threads, die die Skalierbarkeit von Optaplanner diskutieren, und ich frage mich, was ist der empfohlene Ansatz, um mit sehr großen Datensätzen umzugehen, wenn es um Millionen von Zeilen geht?

Wie dieser Blog diskutiert, verwende ich bereits Heuristik (Simulated Annealing + Tabu Search). Der Suchraum des Cloud-Balancing-Problems ist c^p, aber der mögliche Raum ist unbekannt/NP-vollständig.

http://www.optaplanner.org/blog/2014/03/27/IsTheSearchSpaceOfAnOptimizationProblemReallyThatBig.html

Das Problem, das ich zu lösen versuche, ist ähnlich Ausgleich trüben. Aber der Hauptunterschied liegt in den Eingabedaten, neben einer Liste von Computern und einer Liste von Prozessen gibt es auch eine große zweidimensionale "Trefferliste/Tabelle", die die Bewertungen für jede mögliche Kombination hat, die in den Speicher geladen werden muss.

Mit anderen Worten, mit Ausnahme der Einschränkungen zwischen Computern und Prozessen, die die Planung erfüllen muss, ergeben unterschiedliche gültige Kombinationen verschiedene Werte und je höher der Wert, desto besser.

Es ist ein einfaches Problem, aber wenn es um Hunderte von Computern geht, 100k + Prozesse und die Scoretabelle hat eine Million + Kombinationen, es braucht viel Speicher. Obwohl ich mehr Speicher zuweisen könnte, um die Größe des Heapspeichers zu erhöhen, könnte die Planung sehr langsam und mühsam werden, da die Schritte mit benutzerdefinierten Planvariablen/Entity-Vergleichsklassen sortiert werden.

Eine einfache Lösung besteht darin, den Datensatz in kleinere Teilmengen zu unterteilen, jede einzeln auszuführen und dann die Ergebnisse zu kombinieren, sodass mehrere Maschinen gleichzeitig ausgeführt werden können und jede Maschine auf mehreren Threads ausgeführt wird . Der größte Nachteil dieses Ansatzes ist, dass das Ergebnis weit entfernt von optimal ist.

Ich frage mich, gibt es noch andere bessere Lösungen?

Answer 1

Das MachineReassignment-Beispiel hat auch eine große "Score-Kombination" -Matrix. OptaPlanner kümmert sich nicht darum - das sind nur Problemfakten und das DRL passt schnell zu den Kombinationen, die für eine Aufgabe ausgewählt werden. Die Solver.solve() verursacht keinen großen Speicherverbrauch oder Leistungseinbußen. jedoch das Problem in Ihrem Code zu laden (vor Solver.solve() Aufruf) tut Ursache ein großer Speicherverbrauch: das versteht, wenn n = 20k, dann n² = 400m und ein int bis 4 Bytes nimmt, so dass für 20 000 Elemente, die Matrix 1.6 GB in seiner effizientesten unkomprimierten Form int[][] (sowohl in Java und C++!). Also für 20k Reserve 2GB RAM, für 40k Reserve 8GB RAM für 80k Reserve 32 GB RAM. Das ist schlecht skalierbar.

Für den Umgang mit diesen großen Problemen verwende ich Kombinationen von Techniken wie Nearby Selection (siehe meinen Blogartikel), Partitioned Search (was Sie beschrieben, wird es aus der Box in 7 unterstützt werden, aber ich habe es für Kunden in einer CustomPhase implementiert), Limited Selection Construction Heuristiken (müssen weiter recherchieren, die Installation ist da, meist Overkill), ... Partitioned Search schließt zwar optimale Lösungen aus, aber über 10k Planning Entities off-Qualität vs Zeit, die eindeutig begünstigt Partitioned Search gegeben eine angemessene Lösungszeit (Minuten/Stunden/Tage statt Millenia). Der Trick ist, die Größe jeder Partition groß genug zu halten, über 1k Entitäten (daher die Verwendung von NexySelection). Score-Berechnung Geschwindigkeit spielt natürlich auch eine Menge Rolle.