Mathematische Optimierung mittels OptaPlanner

Im Rahmen des Maschine Learning werden Verfahren, wie neuronale Netze oder Decision Tree Algorithmen eingesetzt, und es werden damit in vielen Fällen gute Erfahrungen gesammelt.

Für manche Problemstellungen bieten sich aber nach wie vor Optimierungsverfahren aus dem Bereich des Operation Research an. OptaPlanner ist eine offene und dabei mächtige Bibliothek.

Typische Use-Cases

Mit dem Ziel, entscheidungsunterstützende Systeme zu entwerfen, experimentiere ich derzeit mit den diversen Techniken des Machine Learning an realen Daten. Dabei fallen mir und meinen Kollegen unterschiedliche Use Cases ein.

Bei der Umsetzung merkt man schnell, daß sich manche dieser Problemstellungen nur schwer mittels Machine Learning bearbeiten lassen. Dafür erscheinen aber für manche dieser Use Cases Verfahren der Constraint Programmierung erfolgsversprechender zu sein.

Laut Wikipedia sind lineare Gleichungssysteme, lineare Optimierungen, oder kombinatorische Probleme bzw Probleme mit boolschen Constraints typische Constraints-Probleme.

Ein Beispiel ist für eine solche Problemstellung ist das Cloud-Balancing, bei dem es darum geht, Prozesse so auf unterschiedlichen Rechnern zu verteilen, daß die Betriebskosten minimal sind und Rechenleistung und RAM möglichst optimal genutzt werden. Ein anderes Beispiel ist die Mitarbeitereinsatzplanung unter zeitlichen Restriktionen.

OptaPlanner

Über die Januarausgabe des Computermagazins IX aus dem Heise Verlag bin ich auf eine quelloffene Bibliothek gestoßen, die genau diese Art der Optimierung unterstützt. Anbei finden Sie den Verweis aus den kostenpflichtigen Artikel (Einsatznotizen zu Red Hats OptaPlanner 6.5.0 – Schneller, kürzer, billiger geschrieben von Jochen Stärk), der mich auf diesen Ansatz gebracht hat.

In dem Artikel beschreibt der Autor zur Einführung zwei unterschiedliche Optimierungsprobleme und deren Realisierung in OptaPlanner. Einmal geht es um eine Abwandlung des Cloud-Balancing Problems, und dann um ein Unterproblem des bekannten Travelling Salesmen Problems.

Leider sind die Softwaredownloads schon nicht mehr verfügbar. Daher muss der im Text rudimentär abgedruckte Code reichen, um diese Bibliothek zu beurteilen. Und das was man sieht, sieht interessant aus.

Die Bibliothek ist in Java geschrieben und erfordert eine definierte Struktur. So gibt es Klassen wie Planning-Entity, oder Judge, in denen die Planungsobjekte beschrieben werden und die Bewertungsverfahren. Generell benötigt man also für seine eigenen Aufgaben ähnliche Strukturen.

Die Bibliothek selbst wird relativ detailliert in der Projektdokumentation behandelt. Dort findet man auch Schulungsvideos und Beispiel-Programme.

Ich hatte bisher noch nicht die Zeit dort im Detail zu lesen, jedoch habe ich mir vorgenommen, mir diese Bibliothek genauer zu Gemüte zu führen, da sie sich sehr gut für bestimmte Optimierungsproblem eignet.

Weiterführende Informationen

Das Original dieses Artikels ist auf →Der Produktmanager erschienen (©Andreas Rudolph). Folgeartikel zum Thema gibt es über die (→Mailingliste), oder indem Sie →mir auf Twitter folgen.

In der Online Version des Artikels finden Sie hier die versprochenen weiterführenden Links: