Geschäftsoptimierung

Geschäftsoptimierung braucht praktikable mathematische Berechnungen

Wissensbeitrag

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

Tafel mit mathematischen Formeln

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.

Wissen

Laufzeit von CPLEX-Modellen verbessern

IBM ILOG CPLEX bietet einem die Möglichkeit, mit individuellen mathematischen Modellen viele Arten von Problemstellungen zu simulieren und zu optimieren. Dieser Artikel erklärt, wie sich die Laufzeit dieser Modelle verlängern lässt.

Mathematische Optimierung
Kompetenz 03.09.20

Mathematische Optimierung

Mathematische Optimierung hilft Unternehmen dabei, über den Einsatz begrenzter Ressourcen komplexe Entscheidungen zu fällen und zielgerichtete Kompromisse zu machen.

Mathematische Optimierung und Supermärkte
Wissen

Mathematische Optimierung und Supermärkte

Mathematische Optimierung findet in vielen Bereichen Anwendung. So auch zur Standortplanung für eine Supermarktkette. Dieser Blogartikel fasst die Eckpunkte des Projektes zusammen.

Tafel mit mathematischen Formeln
Wissen

Wozu dient die mathematische Optimierung?

Der Lösungsansatz „mathematische Optimierung“ ist ein sehr mächtiges Werkzeug, wenn es darum geht, verschiedenste Fragestellungen zu untersuchen und eine bestmögliche Lösung zu finden. Dieser Blogbeitrag untersucht häufige Fragen rund um das Thema.

Zur SCOPE Website
Presse 16.12.19

Fachbeitrag: Auftragsbestand mathematisch optimiert

83.000 Fahrzeuge setzte MAN Truck & Bus 2016 ein. Die hohe Nachfrage nahm der Full-Range-Anbieter zum Anlass, seinen Auftragseinplanungsprozess und die Auftragsoptimierung auf den Prüfstand zu stellen. Die Erfolgsstory im Artikel in der SCOPE.

Wolken zur Visualisierung der Cloud
Wissen

Mathematische Optimierung in der Cloud mit IBM DOcplexcloud

IBM bietet mit DOcplexcloud einen Optimierungsservice in der Cloud an. Dabei werden Opimierungsanfragen an einen Server in der Cloud gesendet. Dieser Service bringt so einige Vorteile mit sich, auf die dieser Blogbeitrag näher eingehen will.

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

Referenz

Expletus nutzt Freshdesk: Automatisierte Ticketoptimierung!

CLOUDPILOTS optimierte die Ticketbearbeitung bei Expletus durch eine maßgeschneiderte App, die automatisierte Kontaktupdates ermöglichte.

Blog 30.05.22

Brand Experience und Strategie

Als Unternehmen und Marke lässt man ungern Margen bei Händler liegen, das gilt für die analoge und digitale Welt gleichermaßen. Als Marke willst du logischerweise direkt zum Endkunden.

Blog 03.11.22

Start-ups und die Suche nach Investoren

Unternehmerin, Buchautorin, Keynote Speakerin, Hochschuldozentin und noch einiges mehr – Ruth Cremer auf ein Profil festzunageln, ist so gut wie unmöglich. Spätestens mit ihrem Buch „Die Höhle des Löwen“ machte sich die Rheinländerin in der hiesigen Gründerszene einen Namen. Wir haben sie heute für unseren insights!-Podcast vor das Mikrofon geladen. Bei dieser Gelegenheit erzählt Ruth Cremer, inwiefern auch Investoren von Start-ups profitieren können, dass es letztlich immer um das Lösen von Problemen geht und dass Frauen in manchen Belangen gegenüber Männern einfach die Nase vorn haben.

Bleiben Sie mit dem TIMETOACT GROUP Newsletter auf dem Laufenden!