Key Visual - Manage Your Business Integration
 

Jul

26

Laufzeit von CPLEX-Modellen verbessern

By Marc Arnoldussen on Th, Jul/26/2012

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.


Margin
Blog-Autor
Marc Arnoldussen
Marc Arnoldussen
Optimization & SCM Engineer
+49 221 97343-0
Margin
Informationen
7.0.1  7.0.2  8.0  Absatzmarkt  Active MQ  Active  Administration  Agile Lösungen  Agility  AMS  Analyst  Analytics  Anbindung  Anforderungen  Anwenderkonfernz  Apache  Application Server  API Management  API  AS2  ASP  Automatisierung  b2b  B2B Integration  Basic  Big Data  Blogreihe  Bluemix  Blueworks  BPM  Broker  BRMS  Bus  Business Process Management  Business Rules  Buzzword  Camel  Cast Iron  Cloud API  Cloud Computing  Cloud Integration  Cloud  Commerce  Compliance  Conference  Connect:Direct  CPLEX  CXF  DataPower  Decision Server Insights  Deployer  Deployment  Development  DFDL  Digitalisierte Prozesse  Digitalisierung  Domino  DSI  e-Fachverfahren  ersteinrichtung  Edi  Edition  Einführung  Einsatz  Entscheidung  Entwicklung  ESB  Excel  Fahrplanoptimierung  Features  Federated Connectivity  File Transfer  Filetransfer  Finance  FTE  gentran  gis  Geschäftsprozesse  Go Live  Google  Governance  Hardware ESB  Hosting  Hybrid-Cloud  Hybrid Cloud  Hybrid  IBM Blueworks  IBM BPM  IBM Integration Bus  IBM InterConnect  IBM  ILOG DOC  ILOG LNP  ILOG Transportation Analyst  ILOG  Impact  Infrastruktur  Installation  Integration as a Service  Integration Bus  Integration  Integrator  Interoperabilität  IT-Business-Alignment  Konfiguration  Linear  LNP  Logistik  monitoring  M2M  Manage File Transfer  Management  Marktplatz  Mathematik  Mediation  Message Broker  Messages  Messagesight  Messaging  MFT  Migration  Modellierung  MQ  MQTT  Multicast  Muster  Nachlese  Neuerungen in V7.0.1  Neuerungen  off-premise  on-premise  ODM  ODME  Öffentliche Verwaltung  Open Source  Operational Decision Management  Optimierung  OPL  OSGi  Outsourcing  PaaS  Pattern Integration  Pattern  Patterns  Performance  Portfolio  Praxis  Private  Process Server  Produktionsplanung  Prozessautomatisierung  Prozessintegration  Prozessmodelierung  Prozessoptimierung  PureSystem  Qualität  Real Time  Regelmanagement  Rollen  Routenplanung  Routing  ROI  SaaS API  SaaS Integration  SaaS  Salesforce  Schwerpunktanalyse  Script  SCM  Security  Service Federation Management  Servicemix  SFM  SI  Slotting  SoapUI  SOA Cloud Symposium  SOA  SPSS  Standard  Standardplattform  Standardtool  Standortoptimierung  Sterling Integrator  Sterling  SugarCRM  Symposium  Template  TIP  TM1  TOSCA  Transportation  Transportoptimierung  Übersicht  Umstieg  Unix  Update  vergleich  Vorteile  worklight  workload  wtc  Wartung  Websphere  Websphere: Rollen  WebService Security  WebSphere Enterprise Service Bus  WebSphere ESB  WebSphere MessageBroker  WebSphere Technical Conference  WebSphere  WESB  Workloads  WODM  XAR