Datum
20.12.2013
Dieser Beitrag wurde verfasst von:
Pünktlich zur Weihnachtszeit gibt es auch für Mathematiker wieder etwas auszupacken! IBM hat soeben die neueste Version von ILOG CPLEX STUDIO herausgegeben, mittlerweile handelt es sich um die Version 12.6.
Wie üblich wurden letztes Jahr, mit CPLEX 12.5, neue Funktionen eingeführt, während die Version 12.5.1 einige Monate später hauptsächlich Performanceoptimierungen lieferte. Es war mit diesem neuen Release also mal wieder Zeit für neue Features!
Neue Features, neue Möglichkeiten
Natürlich kann ich hier nicht jede einzelne Neuerung vorstellen, und das möchte ich auch gar nicht. Natürlich sind bei einem ordentlichen Weihnachtspaket auch Unmengen an Schokolade, Printen, Lebkuchen und Marzipan enthalten, aber sie müssen nicht einzeln aufgeführt werden, auch wenn sie uns das Leben versüßen. Entsprechendes gilt hier beispielsweise für die Entwicklungsumgebung. Die verbesserte code completion erleichtert uns den Modellier-Alltag. Neue Scripting-Funktionalitäten eröffnen uns neue Möglichkeiten. Ein LP-File-Viewer erleichtert und die Analyse von Modellen, etc. All das sind natürlich nützliche Dinge und auch Wert, genauer betrachtet zu werden – meinen Fokus lege ich diesmal aber auf andere Funktionen
Optimieren mit High-Speed Rechenleistung
In Zeiten von Cloud-Diensten liegt es nahe, auch in der Optimierung nicht mehr nur auf den eigenen Rechnern zu optimieren, sondern die Rechenleistung von großen Servern auszunutzen. Einen ersten Schritt in diese Richtung ging IBM bereits mit der Version 12.5 und der parallel erschienen Server-Variante CPLEX Enterprise Server; letztlich aber auch nur ein logischer Schritt, der nicht weiter verwunderte. Damit war es schon möglich, sich einen Hochleistungsserver einzurichten, dort CPLEX zu installieren und die Optimierung somit auszulagern.
Jetzt geht die IBM aber noch einen Schritt weiter. Warum sollte man nur einen Server nutzen, wenn einem mehrere Server zur Verfügung stehen? Was einen Optimierungslauf mit gemischt-ganzzahligen Problemstellungen so zeitaufwändig macht, sind die durch das Branch & Bound-Verfahren entstehenden verschiedenen Knoten, die jeweils einzeln gelöst werden müssen.
Branch & Bound am Beispiel erläutert
Nehmen wir an, Sie optimieren ihre LKW-Flotte für eine Lieferung. Rein rechnerisch benötigen Sie dabei vielleicht, laut erstem Optimierungsergebnis, 3,2 LKW. Dies ist natürlich nicht möglich, Sie können Ihre LKW schlecht zerteilen. Daher geben Sie Ihrem Modell als Information mit, dass die LKW-Anzahl eine ganze Zahl sein muss: Das Optimierungsproblem wird also zu einem MIP (Mixed Integer Programming)-Problem. Einfaches Auf- oder Abrunden führt dabei nicht zwangsläufig zu einer optimalen Lösung, daher sieht das Branch & Bound-Verfahren nun folgendes vor: Es werden zwei neue, voneinander unabhängige, Problemstellungen erstellt, die das Ursprungsmodell erweitern: Bei einem wird die maximale Anzahl der LKW auf drei gesetzt, im zweiten Modell wird die Mindestanzahl auf vier gesetzt. Beide Modelle werden erneut gelöst, daraufhin wieder auf Ganzzahligkeit überprüft usw., bis letztendlich eine gültige Lösung herauskommt.
Da diese neuen Modelle (Knoten) aber, wie schon erwähnt, voneinander unabhängig sind, müssen sie ja nicht zwangsläufig auf dem gleichen Rechner nacheinander abgearbeitet werden. Hier setzt nun der Distributed MIP-Algorithmus an, der für mich neben den ganzen kleineren Neuerungen sozusagen die eigentliche Überraschung unter dem Weihnachtsbaum darstellt: Er schickt die einzelnen Modelle an weitere Server, die ihm zur Verfügung stehen, und koordiniert somit den weiteren Verlauf. Wenn die neue Lösung wieder aufgeteilt werden muss, können die neuen Knoten entsprechend wieder auf gerade freie Server aufgeteilt werden. Die Rechenleistung von mehreren unabhängigen Systemen wird damit optimal genutzt. Somit muss der eigentliche Server weniger Knoten berechnen, da ihm die anderen Server Arbeit abnehmen: Die Zeit, die das Modell braucht, um gelöst zu werden, sinkt dementsprechend, abhängig von der Anzahl und Rechenleistung der weiteren Server.
Fazit
Natürlich ist dieses Prinzip immer abhängig von den einzelnen Systemen und den jeweiligen Verbindungen zwischen den Systemen, aber bei einer guten Konfiguration kann dies einen enormen Zeitvorteil einbringen. Meiner Meinung nach ist das also ein sehr interessanter Ansatz, der den Cloud-Gedanken nicht nur auf die Optimierung überträgt, sondern konsequent weiterdenkt!
Autor
Marc Arnoldussen
X-INTEGRATE Software & Consulting GmbHKontakt