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.

Tafel mit mathematischen Formeln
Wissen

Formeln gewinnbringend anwenden

Mathematik und Formeln haben keineswegs nur theoretischen Wert. Besonders in der Optimierung sind sie unerlässlich. Dieser Blogartikel erläutert die Möglichkeiten von Mathematik, die in Optimierungsmodellen verwendet wird.

Boston Consulting Group Logo
Referenz

IBM ILOG CPLEX als Ergänzung zu MATLAB

Die X-INTEGRATE besitzt tiefgehendes Wissen in der individuellen Modellerstellung für IBM ILOG CPLEX sowie in der Integration mit anderen Applikationen und Lösungen. Die BCG hat auf diese Expertise zurückgegriffen und in kurzer Zeit MATLAB durch IBM ILOG CPLEX erweitert.

ILOG Optimization
Technologie

ILOG Optimization

ILOG CPLEX und ILOG CP Optimizer bieten Ihnen die Möglichkeit, in kürzester Zeit verschiedene Simulationen für mögliche Entscheidungen durchzuführen. Dabei ist CPLEX vor allem für lineare Modelle geeignet, während CP Optimizer generelle Constraint-Programming-Modelle löst.

Gleichgewicht zwischen Zeit, Kosten und Qualität
Wissen

Individuelle Fahrplanoptimierung mit IBM ILOG CPLEX

Bei Supply Chain-Fragestellungen kann es vorkommen, dass einem die ILOG Supply Chain-Produkte wie LogicNet Plus XE und Transportation Analyst für die eigenen Bedürfnisse unpassend erscheinen. Für diesen Fall bietet ILOG CPLEX eine Alternative.

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.

Wissen

Magische Quadrate – gar nicht mehr so magisch

In diesem Blogbeitrag wird beleuchtet, was magische Quadrate mit Constraint Programming zu tun haben und wie diese mit dem CP-Solver des CPLEX Optimization Studios für Anwendungsfälle aus der Praxis gelöst werden können.

Standort 15.01.25

catworkx Ungarn

Als einer der größten Atlassian Platinum und Enterprise Solution Partner freuen wir uns, Sie an unserem Standort in Ungarn zu begrüßen.

Wissen

Standortoptimierung als Teil des Supply Chain Managements

Das Supply Chain Management umfasst viele einzelne Aspekte der strategischen und operativen Arbeitsweise von Unternehmen. Einen möglichen Ansatz stellt die Standortoptimierung dar, die dieser Blogartikel vorstellt.

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.

MAN Logo
Referenz

Dynamische und optimierte Auftragseinplanung

MAN Truck & Bus AG setzt auf einen von X-INTEGRATE mathematisch optimierten Auftragsbestand, um seinen Auftragseinplanungsprozess und die Auftragsoptimierung zu verbessern.

Blog 06.10.22

Die Zukunft des Handels – mit Dr. Kai Hudetz vom IFH KÖLN

Eine geballte Ladung Kompetenz haben wir uns für den heutigen insights!-Podcast ins Studio geholt: Dr. Kai Hudetz ist seit August 2009 Geschäftsführer des Kölner Instituts für Handelsforschung IFH und Gründungsmitglied des E-Commerce-Centers ECC. Der Wirtschaftswissenschaftler und Gastdozent verschiedener Hochschulen beschäftigt sich seit Jahrzehnten mit der Frage, wie Handel und digitales Zeitalter zusammenfinden. Im Gespräch erklärt er unter anderem, warum es für den Handel kein Zurück mehr gibt, woran es in deutschen Unternehmen oft noch mangelt und dass der Faktor Mensch keineswegs an Wert verliert.

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.

Wissen

Deep Learning: Ein Beispiel aus dem öffentlichen Dienst

Automatische Bilderkennung hat das Potenzial, Wasserwirtschaftsverbände spürbar zu entlasten – und so beim Hochwasserschutz zu unterstützen. Ein Fallbeispiel.

Blog

Deep Learning: Ein Beispiel aus dem öffentlichen Dienst

Automatische Bilderkennung hat das Potenzial, Wasserwirtschaftsverbände spürbar zu entlasten – und so beim Hochwasserschutz zu unterstützen. Ein Fallbeispiel.

Wissen

Deep Learning: Ein Beispiel aus dem öffentlichen Dienst

Automatische Bilderkennung hat das Potenzial, Wasserwirtschaftsverbände spürbar zu entlasten – und so beim Hochwasserschutz zu unterstützen. Ein Fallbeispiel.

Blog 06.04.23

Metaverse: B2B und B2C Unternehmen maximieren ihren ROI

Das Metaverse verspricht der Gamechanger für die Zukunft der virtuellen Realität und der digitalen Interaktion zu werden und hat das Potenzial Handel, Arbeitswelt und Freizeit nachhaltig zu verändern. Metaverse-Plattformen können Unternehmen dabei helfen, innovative Geschäftschancen zu schaffen und neue Kundengruppen zu erschließen. In diesem Kontext bieten sie die nächste große Chance für Unternehmen im E-Commerce, um wettbewerbsfähig zu bleiben und dein Geschäft auszubauen. Was es mit Metaverse genau auf sich hat, wie Unternehmen von der Metaverse-Revolution profitieren können und was wir von den Vorreitern lernen können, lernst du in der neuen insights!-Folge mit Christian Gleich.

Wissen 30.07.24

LLM-Benchmarks Juli 2024

Unser LLM Leaderboard aus Juli 2024 hilft dabei, das beste Large Language Model für die digitale Produktentwicklung zu finden.

Bleiben Sie mit dem TIMETOACT GROUP Newsletter auf dem Laufenden!