Key Visual - Manage Your Business Integration
 

Jan

10

Geschäftsoptimierung braucht praktikable mathematische Berechnungen

By Marc Arnoldussen on Th, Jan/10/2013

Geschäftsprobleme können häufig über lineare Modelle optimiert werden. Doch lassen sich reale Probleme wirklich "schnell" berechnen? In mathematischen Optimierungsmodellen hängt die Performance oft davon ab, ob das zugrunde gelegte Modell linear ist - oft lassen sich Modelle erst dann lösen. Doch wie erreicht man dies, wenn man eigentlich ein Produkt von booleschen Variablen benötigt, um eine Problemstellung zu modellieren? Mit diesem Thema befasst sich unser heutiger Beitrag.

Boolesche Produkte in einem mathematischen Modell

IBM ILOG CPLEX ist der Marktführer im Bereich der linearen Optimierung und schneidet in Benchmarks immer hervorragend ab. Voraussetzung für diese hohe Performance ist aber ein gut durchdachtes mathematisches Modell, welches CPLEX dann lösen kann. Oft liegt genau in dieser Erstellung aber ein Hindernis, da es oftmals schwierig erscheint, spezielle Fragestellungen als lineare Bedingungen auszudrücken. Häufig hängen bestimmte Werte von zwei unterschiedlichen Ja-Nein-Bedingungen ab, die man generell zunächst als (boolesches) Produkt modellieren würde.

Ein Beispiel aus der Logistik

Ein Beispiel aus der Logistik soll dies verdeutlichen: Wenn Lokation A und Lokation B geöffnet sind, ist ein LKW in der Lage, bis zu 36 Paletten von A nach B zu transportieren. Wenn nur eine der beiden Lokationen geschlossen ist, ist dies nicht möglich. Für den Weg von A nach B gilt also (in OPL-Schreibweise):
float maximaleKapazitaet = 36;
dvar boolean a; // Gibt an, ob Lokation A geöffnet ist.
dvar boolean b; // Gibt an, ob Lokation B geöffnet ist.
dexpr float transportKapazitaet = a*b*maximaleKapazitaet;

Für solche Fälle, also für quadratische Ausdrücke, hat CPLEX Algorithmen implementiert, die diese Bedingungen auflösen können, aber sobald weitere Bedingungen hinzukommen (Zwischenstation C muss ebenfalls geöffnet sein:

dexpr float transportKapazitaet = a*b*c*maximaleKapazitaet; ),

wird die Durchführung problematisch.

Umformulierung durch eine Hilfsvariable

Durch geschickte Modellierung ist es jedoch möglich, diese Bedingungen in das Modell einzubauen. Dazu werden lediglich eine Hilfsvariable, die sich zunächst über den kompletten (reellen) Zahlenraum erstrecken kann, und drei weitere Bedingungen benötigt. Dabei spielt es keine Rolle, wie viele dieser binären Faktoren berücksichtigt werden müssen.



Das Verfahren erläutere ich zunächst für den oben genannten Fall von zwei Bedingungen, erweitere das Modell aber später auf eine beliebige Anzahl.

Beispiel mit zwei binären Variablen

Wir erweitern das Modell um eine Hilfsvariable t und ergänzen folgende Bedingungen im Modell:

dvar float t;
t <= a;
t <= b;
a + b – 1 <= t;
0 <= t;

Durch eine Wertetabelle, die in diesem Fall nur aus 4 Kombinationen besteht, lässt sich dies leicht nachweisen. Nun lässt sich jedes im Modell vorkommende Produkt a*b durch t ersetzen, und das Modell ist wieder linear.

Erweiterung auf eine beliebige Anzahl an binären Variablen

Interessanter wird es nun bei einer beliebigen Anzahl an Faktoren. Wir nehmen an, unser LKW muss durch ein Set von Städten fahren, welches am Anfang eingelesen wird. Dann lauten unsere Bedingungen wie folgt:

/*Die Städte sind vorher nicht bekannt, sondern werden aus einer Datenquelle eingelesen */
{string} staedte = …;

/* Für jede Stadt wird eine Entscheidungsvariable definiert*/
dvar boolean x[staedte];
dvar float t; // unsere Hilfsvariable

/* Die neu formulierte Transportkapazitaet */
dexpr float transportKapazitaet = t * maximaleKapazitaet;

subject to {
forall (s in staedte) t <= x[s];
sum(s in staedte) x[s] – card(staedte) + 1 <= t;
0 <= t; }

Durchführung der Optimierung doch performant möglich!

Wie man sieht, ist es mit dieser Methode möglich, ein Produkt von n binären Variablen durch nur eine zusätzliche Variable und insgesamt n+2 weitere Gleichungen (zusammengefasst in 3 Bedingungen) zu einen Bedingungen umzuformen, was die Performance bei linearen Solvern deutlich erhöhen kann und in einigen Fällen überhaupt erst die Durchführung der Optimierung gestattet.




Haben Sie derartige Fragen zur Durchführbarkeit von Optimierungen? Ich freue mich über Ihre Rückmeldungen.



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