Constraint Streams in OptaPlanner: Eine performante und intuitive Alternative ohne Drools?

Planungsprobleme finden sich bei Unternehmen überall – sei es die Schichtenplanung des Personaleinsatzes bei Callcentern oder die Tourenplanung zur Auslieferung von Gütern. Die Komplexität dieser Probleme macht den Einsatz geeigneter Software im operativen Geschäft notwendig. Für die Entwicklung solcher Software in Java ist OptaPlanner das Mittel der Wahl, um Planungsprobleme abzubilden und lösen zu lassen.

OptaPlanner verwendet sogenannte "heuristische Lösungsverfahren", um eine möglichst gute Problemlösung in akzeptabler Zeit bereitstellen zu können. Solche Verfahren arbeiten inkrementell, indem abwechselnd neue Lösungen, wie zum Beispiel ein möglicher Schichtplan oder eine Fahrzeugroute, generiert und in ihrer Güte bewertet werden. Der Nutzer kann unter anderem festlegen, nach welchem Zeitraum die beste Lösung bereitgestellt werden soll. Je mehr Lösungen in diesem Zeitraum ausprobiert werden können, desto bessere Ergebnisse können erwartet werden (da die Lösungsfindung ein stochastischer Prozess ist, ist dies natürlich nicht sichergestellt).

Bewertung von Lösungen – wichtig und komplex

Während die Generierung einer neuen Lösung schnell gemacht ist – bei einer Schichtplanung müssen lediglich zwei Mitarbeiter für eine Schicht ausgetauscht werden, um eine neue Lösung zu erhalten –, ist die Bewertung einer Lösung deutlich aufwendiger.

Denn die Bewertung sollte beispielsweise bei der Schichtenplanung berücksichtigen, ob die gesetzlichen Ruhezeiten beachtet werden oder die Flexibilität bei plötzlichen Krankheiten gewährleistet ist. Ebenso ist die Fairness für die Mitarbeiterakzeptanz relevant.

Für die Qualität des Planungsergebnisses ist die Geschwindigkeit der Bewertungsberechnung extrem wichtig. Da die Bewertungsfunktion naturgemäß problembezogen ist, muss diese vom Nutzer von OptaPlanner selbst implementiert werden. Hierfür stellt OptaPlanner verschiedene APIs zur Verfügung, die sich in Ausführungsgeschwindigkeit und Implementierungsaufwand relevant unterscheiden.

Zuletzt wurde OptaPlanner um die sogenannten „Constraint Streams“ erweitert, welche durch Ähnlichkeit zur Stream-API die Implementierung der Bewertung einer Problemlösung für Java-Entwickler besonders intuitiv machen und dabei auch performant sein sollen. Die folgende Analyse dient dem Vergleich der verschiedenen Bewertungsverfahren und bietet somit eine Entscheidungsgrundlage für Entwickler bei der Auswahl des geeigneten Verfahrens für ihren Use Case.

Easy Score Calculation

Die Easy Score Calculation von OptaPlanner ist – wie der Name vermuten lässt – die einfachste Variante, eine Bewertungsfunktion zu implementieren. Hier wird bei jedem Aufruf die gesamte Lösung erneut bewertet. Bei der Schichtplanung würden beispielsweise alle Ruhezeiten geprüft und die Fairness für jeden Mitarbeiter bewertet werden. Die Bewertung einzelner Verletzungen von Bedingungen (sogenannte „Soft“ oder „Hard Constraints“) sowie positiver Effekte wird vom Entwickler festgelegt und für eine Gesamtbewertung der Lösung aggregiert.

Diese Variante ist sehr einfach zu implementieren, aber in realistischen Anwendungsfällen vergleichsweise langsam. Es kann interessant sein, diese Variante für die erste Umsetzung zu nehmen, um den Mehrwert des Aufwands komplexerer Varianten zu demonstrieren und die fachliche Güte der Bewertungsfunktion zu testen.

Incremental Score Calculation

Um die Performance zu erhöhen, verwendet die Incremental Score Calculation wie alle weiteren Varianten denselben Trick: Wenn sich ein Teil der Lösung ändert, muss auch nur dieser Teil neu bewertet werden.
Wenn beispielsweise zwei Mitarbeiter für eine Schicht ausgetauscht werden, muss die gesetzliche Ruhezeitprüfung nur für diese beiden Mitarbeiter und ihre angrenzenden Schichten ausgeführt werden. Andere Schichten und die Schichten anderer Mitarbeiter sind noch genauso gut oder schlecht wie vorher und müssen nicht erneut bewertet werden. Dies bringt einen erheblichen Geschwindigkeitsgewinn. Die Incremental Score Calculation ist dabei – wenn korrekt implementiert – potenziell immer die schnellste Variante, da sehr problemspezifische Performance-Tricks angewendet werden können.

Unglücklicherweise hat die Geschwindigkeit einen Preis: Der Entwicklungsaufwand ist verhältnismäßig hoch. Zunächst muss identifiziert werden, wie sich die Bewertung bei Änderung einer oder mehrerer Variablen ändert (Beispiel: Welche Ruhezeiten müssen neu bewertet werden, wenn zwei Schichten getauscht werden?). Um die Erkenntnisse über die Abhängigkeiten nutzen zu können, muss ein komplexes Interface  implementiert werden.

Die Implementierung ist technisch anspruchsvoll, da sehr viele Zwischeninformationen zur schnellen Berechnung vorgehalten werden müssen. Die Implementierung ist dabei stark zustandsbehaftet. Beispielsweise muss zur schnellen Bestimmung von Ruhezeitverletzungen der Nachfolger jeder Schicht schnell verfügbar sein. Dies kann beispielsweise in einer Map vorgehalten werden. Nun muss für jede mögliche Änderung geprüft werden, inwieweit sie sich auf die Nachfolger aller beteiligten Schichten auswirkt. Fehler (beispielsweise ein vergessener Randfall) sind hierbei nicht offensichtlich und können sich aufgrund der Wiederverwendung der Zwischenergebnisse erst spät bemerkbar machen.

Aus diesem Grund sind nach der Implementierung auch aufwendige Tests auf Korrektheit notwendig. Leider können auch Anpassungen sehr aufwendig werden.

Drools Score Calculation

Ein Kompromiss zwischen Implementierungskomplexität und Geschwindigkeit kann über die Score Calculation mit Drools  erreicht werden. Hier wird die Bewertungsfunktion in der Drools-eigenen Regelsprache DRL ausgedrückt. Drools ist selbstständig in der Lage, bei Änderungen nur einen Teil der Bewertungsfunktion neu zu berechnen.

Hierdurch kann der Geschwindigkeitsvorteil einer inkrementellen Bewertungsfunktion genutzt werden, ohne diese aufwendig selbst implementieren zu müssen. Obgleich die Umsetzung auch kleinere Herausforderungen bereithält, ist sie in Bezug auf die zu beherrschende Komplexität deutlich näher an der Easy Score Calculation als an der Incremental Score Calculation dran. Dafür muss ein Java-Entwickler aber auch eine neue Sprache lernen, die ihre eigenen Herausforderungen bietet. Es folgt ein Beispiel der Drools Score Calculation, bei welchem auf Einhaltung der Ruhezeiten geprüft wird.

rule "Ruhezeit wird eingehalten"
    when
        $schicht : Schicht($datumVorherig : datum)
        $naechsteSchicht : Schicht(datum == $datumVorherig.plusDays(1))
        Boolean($schicht.ruhezeitVerletzt($naechsteSchicht))
    then
        scoreHolder.addHardConstraintMatch(kcontext, SimpleLongScore.ONE);
end

Im obigen Beispiel werden alle Schichten gesucht, welche einen Nachfolger am nächsten Tag haben. Diese werden dann auf Ruhezeitverletzungen der Mitarbeiter geprüft. Jede gefundene Verletzung wird in der Bewertungsfunktion entsprechend negativ bewertet.

Constraint Streams Score Calculation

Seit kurzer Zeit gibt es einen neuen Stern am OptaPlanner-Himmel: Constraint Streams. Dieser – sich derzeit in der aktiven Entwicklung befindliche – Ansatz orientiert sich an den mit Java 8 eingeführten Streams. Im Gegensatz zu den Java-8-Streams werden bei Änderungen allerdings nur die relevanten Teile des Streams neu berechnet.

private Constraint ruhezeit(ConstraintFactory factory) {
 return factory.fromUniquePair(Schicht.class, Joiners.equal(
         schicht -> schicht.getDatum().plusDays(1),
         schichtNaech -> schichtNaech.getDatum()))
    .filter((schicht, schichtNaech) -> schicht.ruhezeitVerletzt(schichtNaech))
    .penalize("Ruhezeit zur nächsten Schicht verletzt", SimpleLongScore.ONE);
}

Constraint Streams lesen sich für Java-Entwickler relativ natürlich – das obige Beispiel ist die entsprechende Variante des vorherigen Drools-Beispiels. Diese „natürliche“ Umsetzbarkeit von Constraint Streams ist ein nicht zu unterschätzender Vorteil. Für Java-Entwickler ist die Verwendung der API intuitiv und benötigt kürzere Einarbeitungszeiten als die DRL von Drools.

OptaPlanner stellt zwei Implementierungen für Constraint Streams bereit. Eine Variante basiert intern auf der Drools-Engine, die andere ist eine auf Performance optimierte Neuentwicklung mit dem Namen Bavet. Aktuell sind weder die Arbeiten an der API noch an beiden Implementierungen abgeschlossen – bei manchen Anwendungsfällen wird es noch Lücken oder rohe Kanten geben.

Score Calculation Benchmarking

Die für einen Anwendungsfall „beste“ Implementierung wird immer aus einem Kompromiss zwischen Wartungsaufwand und Performance bestehen: Bei manchen kleinen Problemen reicht schon die Easy Score Calculation völlig aus, bei anderen Problemen wird nur die Incremental Score Calculation eine Lösung in akzeptabler Zeit bringen.

Da die Performance für die Lösungsverfahren extrem wichtig ist, stellt OptaPlanner umfangreiche Benchmark-Funktionalitäten  zur Verfügung. Mit diesen können beispielsweise verschiedene Bewertungsfunktionen, Datensets oder Heuristiken für ein Problem miteinander verglichen werden, damit die für das eigene System beste Umsetzung gefunden werden kann.

Weiterhin bietet OptaPlanner eine eigene Benchmark-Suite für vordefinierte Probleme. Die genauen Geschwindigkeiten sind – wie bei jedem Benchmark – von vielen Faktoren abhängig. Dennoch können allein aus einem Vergleich der Größenordnungen der Geschwindigkeiten interessante Erkenntnisse gezogen werden.

Die Benchmarking-Suite enthält die Probleme „NQueens“ sowie „Cloud Balancing“, für welche Implementierungen aller Bewertungsfunktion-Varianten vorliegen, weshalb im Folgenden auf diese eingegangen wird.

OptaPlanner Benchmark, Problem "NQueens": Anzahl Bewertungen pro Sekunde, höher ist besser.

NQueens ist ein Problem mit wenigen, eher einfachen Bedingungen: N Damen sollen auf einem N*N-Schachbrett so verteilt werden, dass sie sich nicht schlagen. Die Härte gibt hierbei die Anzahl der Damen an – einfach sind 32 Damen, mittel 64 und hart sind 256.

OptaPlanner Benchmark, Problem "CloudBalancing": Anzahl Bewertungen pro Sekunde, höher ist besser.

Cloud Balancing hat im Gegensatz hierzu eher komplexere Bedingungen: Es gibt Computer mit einer bestimmten Menge an verfügbaren Ressourcen (CPU, RAM, Netzwerk) und Prozesse, die einen Teil ebenjener Ressourcen benötigen. Optaplanner soll die Prozesse so den Computern zuweisen, dass möglichst wenige Computer genutzt werden (bzw. dass die Wartungskosten, die fix pro eingeschaltetem Computer definiert sind, minimiert werden). Die Problemhärte bezieht sich hierbei auf die Anzahl an Computern und Prozessen.

Schlussfolgerungen

Wie erwartet zeigt das Benchmarking für die beispielhaften Probleme, dass die Easy Score Calculation nicht mit der Problemgröße skaliert: Die Geschwindigkeit nimmt mit wachsender Problemgröße signifikant ab. Für kleine Probleme kann die Easy Score Calculation jedoch sogar schneller als die meisten Alternativen sein – der Overhead für die Implementierung der inkrementellen Berechnung via Constraint Streams oder Drools Score Calculation lohnt sich hier nicht.

Die anderen Bewertungsfunktionen haben bei wachsender Problemgröße deutlich geringere Abnahmen der Lösungsgeschwindigkeit, sie skalieren aufgrund der inkrementellen Berechnung deutlich besser bzw. skalieren überhaupt.

Die Geschwindigkeit der Incremental Score Calculation ist überraschend: In der OptaPlanner-Dokumentation wird die Performance primär in langsam (Simple Score) und schnell (alle anderen) geteilt. Dass die Incremental Score Calculation um ganze Größenordnungen schneller als die Alternativen sein kann, geht nicht so deutlich hervor.

Beim Vergleich von Constraint Streams mit Drools Score Calculation fällt auf, dass beide ähnlich schnell sein können (NQueens), es aber auch durchaus deutliche Unterschiede geben kann (CloudBalancing). Das komplexere CloudBalancing-Problem zeigt auch eine der Lücken von der Bavet-Implementierung von Constraint Streams: Die Umsetzung ist derzeit einfach nicht möglich, da die groupBy-Operation noch nicht implementiert ist.

Ausblick

Wir sind gespannt auf die Weiterentwicklung der Constraint-Streams-Funktionalität durch OptaPlanner. Für Java-Entwickler bietet sie eine intuitive und leicht zu wartende Alternative zu Incremental Score Calculation oder Drools Score Calculation, welche die Easy Score Calculation in vielen Fällen übertrumpfen kann.

In jedem Fall: Die Vor- und Nachteile der Alternativen sind Use Case spezifisch und wir empfehlen, ein geeignetes Benchmarking durchzuführen, um die beste Lösung für das eigene Projekt zu finden. Dabei sollte auch der Entwicklungs- und Wartungsaufwand für die verschiedenen Alternativen betrachtet werden. So könnte es zum Beispiel Sinn machen, mit der Easy Score Calculation anzufangen und zu prüfen, ob die Performance für den Use Case bereits ausreichend ist.

Für Entwickler, welche zusätzlich die neue Berechnungsalternative über Constraint Streams für ihr eigenes Projekt ausprobieren möchten, verweisen wir an dieser Stelle gerne auf unsere beispielhafte Umsetzung zur Lösung eines Raum- und Terminplanungsproblems für Universitätsvorlesungen in unserem GitHub Repository.

Die Autoren Magdalena Lang und Hauke Husstedt haben einige Erfahrung mit Optimierungsverfahren und insbesondere dem Produktiveinsatz des OptaPlanner gesammelt. Tauschen wir uns gern einmal dazu aus!

Hauke Husstedt ist Berater bei der viadee IT-Unternehmensberatung mit einem Schwerpunkt auf Softwareentwicklung mit Java und Spring. Sein besonderes Interesse gilt technisch anspruchsvollen Problemstellungen aus den Bereichen künstliche Intelligenz und Optimierung.

Als Beraterin bei der viadee IT-Unternehmensberatung ist Magdalena Lang inbesondere in den Kompetenzbereichen Business Intelligence und Künstliche Intelligenz aktiv. Dabei bringt sie vor allem Erfahrung mit Problemstellungen des Operations Research und der Optimierung mit, sowohl durch Forschungstätigkeiten als auch aus dem Praxiseinsatz.