Vor 10 Jahren begann die Entwicklung des Optimization.Framework, welches wir noch heute – als OPTANO Modeling – bei unseren Softwareprojekten einsetzen. Dieser Artikel beschreibt den Anlass für die Entwicklung des Optimization.Framework bzw. OPTANO Modeling[1] und den Hintergrund, wie es dazu kam.

Der Ausgangspunkt waren sogenannte „Dünne Matrizen“. Man kann sie sich als einen Sternenhimmel vorstellen: Wenige Punkte in sehr viel Raum. Die Kanten eines Netzwerkfluss-Modells wären in diesem Bild die Sternzeichen.

Die Modellformulierung mit dünnbesetzten Matrizen wird anhand der Sprachen MPL (von Maximal Software[2]), MOSEL (von FICO[3], ehemals Fair Isaac) und OPTANO Modeling[1] erläutert.

Modellierungssprache und dünne Matrizen

Zuerst die Problemstellung: Manchmal werden wir zu Rate gezogen, wenn Modelle mit kleinen Testinstanzen gut zurechtkommen, aber für größere Instanzen nicht gut skalieren (nun, selbst ohne Fehler ist polynomielle Laufzeit nicht unbedingt eine „gute“ Skalierung…). Der Grund für die schlechte Skalierung ist häufig, dass die Sparsity (Dünnheit) einer Matrix nicht richtig ausgenutzt wird.

Ein Beispiel:

Entspricht eine Variable der Transportmenge von s nach z, der Transport ist aber auf diesem Abschnitt nicht erlaubt, so ist es besser die Variable gar nicht erst zu erzeugen, als sie auf 0 zu fixieren.

Diese fixierten Variablen werden zwar von allen modernen Solvern sofort entfernt, kosten aber bei der Matrixgenerierung Arbeitsspeicher und Laufzeit. Die folgenden Beispiele zeigen, wie man in unterschiedlichen Modellierungssprachen Variablen nicht erzeugt, wenn sie nicht gebraucht werden.

Alle Beispiele beruhen auf der Annahme, dass es eine Menge der gültigen Index-Tupel gibt.

MPL-Code (Ausschnitt):

In MPL wird zunächst eine Tupel-Menge der vorhandenen Einträge erstellt, dann geladen und Variablen in Abhängigkeit von dieser Menge definiert. Die Abhängigkeiten ergänzen immer die schon vorhandenen Indizes: „Wähle z so, dass das Tupel (s, z) im Sparseindex vorkommt – wobei s schon gewählt ist“. Daher ist ein sinnvoll aufeinander aufbauender Index-Baum sehr hilfreich.

S_Z[S,Z] := DATABASE("Sparseindex_S_Z")
PARAMETER
myParameter[S, Z IN S_Z] := DATABASE("Data_V_SZ")
VARIABLE
myVariable[S, Z IN S_Z]

MOSEL-Code (Ausschnitt):

In Mosel werden in einer forall-Schleife alle Indizes genannt und dann wird mittels exist (oder einem anderen logischen Ausdruck) geprüft, ob die Variable tatsächlich erstellt werden soll. Trotz der wertvollen Unterstützung des Mosel-Supports bei dem damaligen Projekt, für den wir uns noch einmal bedanken möchten, konnten wir nicht in Erfahrung bringen, inwieweit jedes Indextupel auf Existenz geprüft wird.

declarations
mySparseIndex: dynamic array(s,z) of mpvar
end-declarations
SQLexecute("SELECT * from Data_V_SZ”, mySparseIndex)
forall (s_ in S, z_ in Z | exists(mySparseIndex(s_, z_)))
create(myVariable(s_, z_))

OPTANO Modeling-Code (Ausschnitt)

Normalerweise würde man für die implizite Erstellung der Variablen die Anlage eines Constraints nutzen. Dieses Beispiel verdeutlicht aber, wie die Objektverknüpfung ausgenutzt werden kann:

Model.AddVariables(AllS.SelectMany(s => s.TransportsToZ.Select(z=> myVariables [s,z]));

Historisches

Version One

Die erste Idee zum Optimization.Framework (damals war es eher die Model.cs-Klasse) entstand 2006 am DS&OR Lab der Uni Paderborn[6] . Wir haben dort an der mathematischen Optimierung von Materialflüssen geforscht. Die Umsetzung ging auf Multi-Commodity Network-Flows with Resource Constraints-Modelle zurück, die die unangenehme Eigenschaft haben, sehr, sehr dünn besetzte Matrizen zu erzeugen. Wir haben unterschiedliche Modellierungssprachen untersucht und herausgefunden, dass MPL den mit Abstand schnellsten Matrixgenerator hatte. Ich erinnere mich noch an eine lange Diskussion darüber mit Bjarnie Kristjansson (war’s die EURO2007 in Prag oder die IFORS2008 in Sandton?) und an seine Erzählung, wie viel Geschwindigkeits-Tuning in den MPL Code gesteckt wurde. Bei den MPL-Versionen 4.2a bis 4.2k konnten wir ihn und Sandip Pindoria vor allem durch Testen unterstützen. Bei unseren Tests kamen immer wieder Fehler auf, beispielsweise dass OPTIMAX [2] nicht thread-save war, die die beiden gefixt haben. Wilde Tage damals…

Trotz allem Tuning blieb jedoch eine Sorge: Der Aufbau der Matrizen dauerte auch mit MPL noch Stunden, manchmal Tage, beanspruchte gigabyteweise Speicher und am Ende löste der Solver die Modelle in wenigen Minuten (gut, dass die Lösung nicht auch noch Tage gedauert hat). Das Verhältnis hat uns Sorgen gemacht. Wir konnten unser Wissen über die Zusammenhänge des Modells (welcher Lieferant liefert ein Produkt, wo soll das Produkt hin, welcher Knoten kann einen anderen erreichen usw.) nur über Queries der Datenbank in MPL und damit in die Generierung bringen. Obwohl ja alles schon im Speicher lag: der Server konnte in wenigen Sekunden ein Objektmodell der Informationen aufbauen, inkl. aller Objektverknüpfungen.

Später stießen Dr. Tim Schöneberg (heute bei Volkswagen) und Dr. Kostja Siefen (heute bei Gurobi) zum Team. Wir begannen einen eigenen Matrix-Generator in c# und .net zu schreiben: Einem Modell konnten Restriktionen und Variablen hinzugefügt werden. Am Ende wurden diese als Matrix an den Solver übergeben. Das reduzierte die Zeit der Generierung auf Minuten und den Speicherbedarf auf nur ein paar hundert Megabyte. Der wesentliche Unterschied war: Der Code, um das Modell in der neuen Klasse aufzubauen, konnte Wissen über die inhaltlichen Zusammenhänge des Netzwerkes nutzen. Prozedural aufgebaut war es möglich, jedes Objekt nur einmal zu berühren, alle relevanten Informationen zusammen abzulegen. Das sparte viel Suchzeit und viel Speicher für Index-Wörterbücher (die MPL vermutlich intern anlegt).
Model.AddConstraint(new Constraint(0, binaryVariable1 + binaryVariable2 + binaryVariable3,1));
Dies ist ein Ausdruck für eine Summe über Binärvariablen, deren untere Schanke 0 und obere Schranke 1 sein sollte. Die Objektstrukturen waren noch recht einfach, der Code war auf ADO.net[4] angelegt. Aber es gab schon überladene Ausdrücke wie >=, ==, <= usw., mit denen Restriktionen formuliert werden konnten.

Version Two

Kurze Zeit später, mit Visual Studio 2008 und .net Framework 3.5 kam Linq[5]. Damit wurden neue Möglichkeiten geschaffen, Restriktionen im Code zu hinterlegen. In dieser Zeit kam Lars Beckmann (ehemals Microsoft) zum DS&OR Lab. Er hat den damaligen Code neu aufgesetzt und als alleinstehende Bibliothek zusammengefasst. Die Möglichkeiten zur Verwendung wurden deutlich erweitert. Linq machte es möglich, Restriktionen dieser Art im Code abzubilden:
mathModel.AddConstraint(Expression.Sum(multiModel.Origins.Select(orig => Transport[orig, dest, prod])) == dest.Demand[prod]);

Der Modell-Code ließ sich dadurch sehr gut lesbar darstellen. Den Nachteil schlechterer Lesbarkeit gegenüber herkömmlichen Modellierungssprachen konnte das Optimization.Framework damit mehr als wettmachen: Es gab gute Code-Editoren, gut lesbaren Code und sogar Typensicherheit.

Darüber hinaus wurden:

  • Weitere Solver angebunden: neben CPLEX[7], XPRESS[3] und MOPS[8] aus den ersten Jahren, konnten nun auch Gurobi[9], GLPK[10] und weitere angesprochen werden (die Liste lässt sich leicht erweitern…)
  • Semantische Informationen wie AND und OR für Restriktionen lassen sich eingeben und werden vom Optimization.Framework in die bestmögliche Formulierung für den jeweiligen Solver übersetzt.
    AddOrConstraints(var1 == 1 | var2 == 2, "Either var1 equals 1 or var2 equals 2"));
  • Viele unterschiedliche Ansätze zum Speichermanager wurden evaluiert.
  • Funktionen wie das Lesen und Schreiben von lp- und mps-Dateien wurden hinzugefügt.

2016 wurde aus Optimization.Framework im Zuge eines Rebrandings OPTANO Modeling.

Mittlerweile wird unser Modellierungssystem in tausenden Projekten verwendet: das nuget-Package wurde bereits über 20.000mal heruntergeladen (Stand Februar 2016)!

Mit der Weiterentwicklung von OPTANO wird auch OPTANO Modeling kontinuierlich optimiert.