Laufzeit von CPLEX-Modellen verbessern

Wissensbeitrag

IBM ILOG CPLEX bietet einem die Möglichkeit, mit individuellen mathematischen Modellen viele Arten von Problemstellungen zu simulieren und zu optimieren. Der Marktführer in diesem Bereich zeichnet sich durch eine besonders hohe Performanz aus und ist in der Lage, auch Modelle mit Millionen von Variablen und Bedingungen zu lösen.

Grenzen der linearen Optimierung

Die Laufzeit wird allerdings durch die Anzahl von Variablen negativ beeinflusst, die ganzzahlig sein müssen. Für diese MIP-Modelle (Mixed Integer Programming) müssen spezielle Algorithmen wie z.B. Branch & Bound bzw. Branch & Cut verwendet werden. Dazu wird die Ganzzahligkeitsbedingung zunächst ignoriert, wodurch das Modell sehr schnell gelöst werden kann. Allerdings können dabei natürlich auch rationale Zahlen als Ergebnis herauskommen. Für diese Variablen werden schrittweise weitere Bedingungen hinzugefügt und das Modell wird erneut gelöst. Dies wiederholt sich so lange, bis alle Variablen schließlich ganzzahlig sind.

Zeitersparnis durch CPLEX-Standardfunktionen

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.

Zeitersparnis durch eigene Algorithmen

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.

Strategische Produktionsplanung

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.

Die Realisierung mit ILOG OPL und ILOG Script

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.

Fazit

Selbstverständlich kann dieser Ansatz auch mit den Parametern für Lösungsqualität und Rechenzeit kombiniert werden. Somit bietet CPLEX trotz der hohen Performanz die Möglichkeit, mit eigenen Algorithmen die Optimierung noch weiter zu beschleunigen, bis die gewünschte Laufzeit erreicht wird.

Boston Consulting Group Logo
Referenz

IBM ILOG CPLEX als Ergänzung zu MATLAB

Die X-INTEGRATE besitzt tiefgehendes Wissen in der individuellen Modellerstellung für IBM ILOG CPLEX sowie in der Integration mit anderen Applikationen und Lösungen. Die BCG hat auf diese Expertise zurückgegriffen und in kurzer Zeit MATLAB durch IBM ILOG CPLEX erweitert.

ILOG Optimization
Technologie

ILOG Optimization

ILOG CPLEX und ILOG CP Optimizer bieten Ihnen die Möglichkeit, in kürzester Zeit verschiedene Simulationen für mögliche Entscheidungen durchzuführen. Dabei ist CPLEX vor allem für lineare Modelle geeignet, während CP Optimizer generelle Constraint-Programming-Modelle löst.

Geschäftsoptimierung
Wissen

Geschäftsoptimierung mit mathematische Berechnungen

In mathematischen Optimierungsmodellen für Geschäftsprobleme hängt die Performance oft davon ab, ob das zugrunde gelegte Modell linear ist. Der heutige Blogartikel erklärt das Vorgehen.

Wissen

CPLEX 12.6 ist da

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.

Blog 17.08.23

PIM für den E-Commerce – die Booster aktivieren

Kunden erwarten heute im E-Commerce mehr als nur einen Webshop zum Kaufen - sie verlangen eine nahtlose Integration von Recherche, Produktvorauswahl, Kaufvorbereitung, -durchführung und After-Sales-Services über verschiedene analoge und digitale Touchpoints hinweg. In diesem Blogbeitrag wird dir anhand eines Beispiels erklärt, wie das KANO-Modell zur Steigerung der Kundenzufriedenheit beiträgt. Du erfährst, wie du die richtigen Informationen in der passenden Form bereitstellst und gezielt die Vorteile für deine Kunden zum optimalen Zeitpunkt hervorhebst.

Event Archive 31.01.23

Process Mining: Geschäftsprozesse verstehen und verbessern

Die Schwächen des Ist-Zustands aufdecken: Ineffizienzen beim Zusammenspiel von Mitarbeitenden und IT-Systemen durch datengetriebene Einsichten in effiziente Automation verwandeln. - Jetzt anmelden!

Wissen

Bessere Laufzeiten und schnellere Reaktionen dank BPM

In unserer schnelllebigen Zeit ist es gerade im Geschäftsumfeld wichtig, dass alle Prozesse möglichst schnell und vollständig abgeschlossen werden. Hier kann kann BPM helfen, durch die Optimierung Prozessen Zeit und Geld zu sparen.

Gleichgewicht zwischen Zeit, Kosten und Qualität
Wissen

Individuelle Fahrplanoptimierung mit IBM ILOG CPLEX

Bei Supply Chain-Fragestellungen kann es vorkommen, dass einem die ILOG Supply Chain-Produkte wie LogicNet Plus XE und Transportation Analyst für die eigenen Bedürfnisse unpassend erscheinen. Für diesen Fall bietet ILOG CPLEX eine Alternative.

Verschiedene Werkzeuge wie Hammer, Schraubenzieher, etc. auf einem Boden
Wissen

ILOG CPLEX, COGNOS TM1 und SPSS - Möglichkeiten aus 3 Welten

Wie bei jeder Softwareentwicklung basieren auch Optimierungsprojekte auf dem EVA-Prinzip, also der Abfolge Eingabe – Verarbeitung – Ausgabe. Drei Tools für drei Aspekte - das sind die Vorteile von ILOG CPLEX, COGNOS TM1 und SPSS.

Event 06.05.20

Webcast: Versicherung und Data Science

Marc Bastian zeigt Ihnen ein Beispiel einer analytischen Infrastruktur für KI Anwendungsfälle, praktische Projekterfahrung und Erfolgsfaktoren.

Event

Webcast: Cloud Transformation & "run your App"

Lernen Sie mit Jochen Schneider die Cloud 1.0 (Cloud 1.0 (Lift&Shift), Cloud 2.0 (Microservices, Big Data) und Cloud 3.0 (Multi Cloud Management, Big Compute) kennen.

Event

Webcast: Das kognitive Versicherungsunternehmen

Lernen Sie von Dr. Jürgen Huschens das Konzept des Kognitive Enterprise kennen, die Adaption auf die Versicherungsindustrie und vieles mehr.

Event

Webcast: Smarte Erkennung von Kostennoten

Unsere Speaker Madeline Jolk und Frank Trila von der TIMETOACT berichten Ihnen alles rund um das Thema Erkennung von Kostennoten.

Event

Webcast: Regresspotenziale nutzbar mit KI

André Ullrich von der Roland Rechtsschutz AG erzählt Ihnen in einem Praxisbericht, wie Regresspotenziale mit KI nutzbar gemacht werden können.

Event

Webcast: VA-IT Anforderungen umsetzen

Unsere Experten Kerstin Gießer und Carsten Hufnagel von der TIMETOACT berichten Ihnen, wie VA-IT-Anforderungen schnell und Modular umgesetzt werden können.

Articifial Intelligence & Data Science
Service

Artificial Intelligence & Data Science

Aus strukturierten und unstrukturierten Daten wertvolle Informationen extrahieren — das verbirgt sich hinter Data Science.

Analytics und Business Intelligence
Service

Analytics & Business Intelligence

Analytics & Business Intelligence hat in den vergangenen Jahren zunehmend an Bedeutung gewonnen.

Icon Atlassian Jira Software
Produkt 09.08.22

Jira Software

Planung, Nachverfolgung und Releases von Software für agile Teams

Bleiben Sie mit dem TIMETOACT GROUP Newsletter auf dem Laufenden!