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.
Autor
Marc Arnoldussen
X-INTEGRATE Software & Consulting GmbHKontakt