Laufzeit von CPLEX-Modellen verbessern

Abhängig davon, wie viele Iterationen dafür nötig sind, dauert es natürlich entsprechend lange, das Optimum des Modells zu finden. Die Laufzeit lässt sich allerdings verkürzen, wenn man eine geringere Lösungsqualität akzeptiert. Ist Beispielweise der optimale Zielfunktionswert (ohne Berücksichtigung der Ganzzahligkeitsbedingung) 10, die beste bisher gefundene Lösung mit ganzen Zahlen 9, so ergibt sich eine Differenz von 10%.

CPLEX bietet für diesen Fall die Möglichkeit, diesen Parameter vorher einzustellen, dass die Suche bei einer bestimmten prozentualen Differenz beendet wird und die beste bisher gefundene Lösung angezeigt wird. Außerdem lässt sich einstellen, dass die Suche nach einer festgelegten Zeit beendet wird, unabhängig von der Lösungsqualität. Weitere Parameter ermöglichen es, den genutzten Arbeitsspeicher und die Anzahl der verwendeten CPU-Kerne festzulegen, um CPLEX perfekt an die Arbeitsumgebung anzupassen.

Eine andere Möglichkeit besteht darin, das Modell in kleinere Teilmodelle zu unterteilen und diese einzeln zu lösen. Die dadurch berechnete Lösung ist im Allgemeinen kein globales Optimum (es unterscheidet sich also von dem Wert, den man herausbekommen hätte, wenn man das komplette Modell gelöst hätte), kann aber die Berechnung erheblich beschleunigen. Wenn die dadurch erreichte Lösungsqualität ausreicht, ist dies also ein ernstzunehmender Ansatz.

Im vorliegenden Fall wurden wir von einem Unternehmen beauftragt, diesen Ansatz mit ILOG CPLEX zu realisieren. Eine Produktionsplanung stützte sich auf zwölf aufeinanderfolgende Zeitabschnitte. Da es zu unperformant war, dieses Modell komplett zu optimieren, wurden die Zeitabschnitte aufgeteilt. Zunächst wurden die Zeitabschnitte 1-4 optimiert. Von dieser Lösung wurden dann die Abschnitte 1-2 als „optimal“ angesehen und als konstant gesetzt. Danach wurden die Abschnitte 3-6 optimiert. Wieder wurden die ersten beiden Abschnitte als „optimal“ angenommen, sodass nun die Zeitabschnitte 1-4 fix waren. Es folgte die Optimierung über die Abschnitte 5-8, und wurde entsprechend fortgesetzt, bis schließlich das komplette Modell optimiert war.

Umsetzen lässt sich dies über eine scriptbasierte Modellierung. Zunächst wird in gewohnter Weise ein Modell entwickelt, das die komplette Fragestellung optimieren könnte. Als nächstes wird ein main-Modell entwickelt, in dem dann das Scripting genutzt wird. Dieses ruft das Optimierungsmodell auf und befüllt es mit Daten. Außerdem lässt sich dort auch festlegen, wie obere und untere Schranken für Variablen lauten sollen.

Wenn also schon ein Modell gelöst wurde, lassen sich innerhalb des Scriptings diese Lösungen auslesen, und einige davon als gleichzeitige obere und untere Schranken für einige Variablen festlegen; somit wird die Variable festgesetzt und die Anzahl der weiteren zu berechnenden Variablen wird reduziert. Ein interner Counter kann dabei die Iterationen mitzählen und abhängig davon immer weitere Variablen festlegen, bis am Ende das komplette Zeitfenster optimiert wurde.