Geschäftsoptimierung braucht praktikable mathematische Berechnungen

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.

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.

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.

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; }

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.