Latente Optimierung

Die latente Optimierung ist ein Optimierungsparadigma, das von Lokad entwickelt wurde und sich auf schwierige, komplexe kombinatorische Probleme konzentriert. Es behandelt auch stochastische Probleme, die immer dann auftreten, wenn Unsicherheit vorhanden ist. Die latente Optimierung stellt einen Durchbruch für Herausforderungen wie die geplante Ressourcenzuweisung dar. Im Gegensatz zu klassischen Solvern, die im Lösungsraum arbeiten, arbeitet die latente Optimierung im Strategie-Raum. Dieser Ansatz ermöglicht eine schnelle Neuausrichtung der Optimierung, wenn sich die Bedingungen ändern.

Technologieüberblick

Die latente Optimierung, eingeführt im Jahr 2024, ist die zweite Generation von allgemeinen Optimierungstechnologien, die von Lokad entwickelt wurden. Sie behandelt schwierigere kombinatorische Probleme als die, die durch stochastischen diskreten Abstieg behandelt werden, obwohl sie mit einem leicht reduzierten Maß an Skalierbarkeit einhergeht.

Konzeptionell entwerfen die Supply Chain Scientists bei Lokad eine Datenverarbeitungspipeline, die die folgenden Schritte umfasst:

1. Bereiten Sie die historischen Daten vor.
2. Generieren Sie probabilistische Prognosen.
3. Erstellen Sie eine robuste Entscheidungsstrategie.
4. Re-optimieren Sie in letzter Minute unter veränderten Bedingungen.

Die historischen Daten werden mithilfe der allgemeinen Datenverarbeitungsfähigkeiten von Envision vorbereitet; Envision ist die domänenspezifische Sprache von Lokad. Probabilistische Prognosen werden dann mithilfe des differenzierbaren Programmierens erstellt, ein Paradigma, das sich ideal für die probabilistische Modellierung eignet und in Envision als Bürger erster Klasse behandelt wird.

Anschließend wird die latente Optimierung eingesetzt, um eine Entscheidungsstrategie zu generieren. Im Wesentlichen ist das Ergebnis der latenten Optimierung ein spezialisierter Solver, der eng auf das spezifische Problem zugeschnitten ist. Schließlich kann diese Strategie unter den endgültigen, sich leicht ändernden Bedingungen ausgeführt werden, um die erforderlichen Entscheidungen zu treffen. Da die Strategie schnell läuft, kann sie interaktiv von Personen im Prozess verwendet werden.

Alle vier Schritte – (1), (2), (3) und (4) – werden innerhalb von Envision durchgeführt.

Grenzen traditioneller Solver

Die mathematische Optimierung ist ein ausgereichtes Segment der Informatik. Eine Vielzahl von Solvern – sowohl proprietäre als auch Open-Source – sind auf dem Markt verfügbar. Leider erfüllen keine dieser bestehenden Technologien unsere Anforderungen, insbesondere bei der Bewältigung von engen Zeitplanungsproblemen.

Branch-and-Bound-Algorithmen (und alle ihre Varianten) beruhen darauf, den zulässigen Bereich in kleinere Teilprobleme zu unterteilen (Verzweigung) und Relaxationen (Begrenzung) zu verwenden, um große Teile des Suchraums zu beschneiden. Dieser Ansatz funktioniert schlecht für Supply-Chain-Probleme, da sie zu offen bleiben. Obwohl der Lösungsraum streng eingeschränkt ist, ist er dennoch enorm. Nur die Einhaltung der Einschränkungen reicht bei weitem nicht aus, um eine gute Lösung zu produzieren, was das Kernprinzip der Partitionierung untergräbt.

Lokale Suchalgorithmen (und alle ihre Varianten) drehen sich darum, über eine oder mehrere aktuelle Lösungen zu iterieren und nahegelegene Varianten zu untersuchen. Leider funktioniert diese Methode auch schlecht, da das Konzept der “Lokalität” in diesen Problemen nicht gut definiert ist. Angesichts der strengen Einschränkungen dieser Szenarien verletzen die meisten lokalen Anpassungen an eine Lösung so viele Einschränkungen, dass der Suchprozess keine verbesserte Lösung wiederherstellen kann.

Bei Lokad haben wir uns ein Skalierbarkeitsziel von einigen Millionen Variablen für schwierige kombinatorische Probleme gesetzt, zusammen mit der Fähigkeit, sich innerhalb von wenigen Sekunden neu zu optimieren, wenn sich die Bedingungen ändern – auch wenn diese Änderungen die ursprüngliche Lösung durch kaskadierende Effekte vollständig ungültig machen.

Unter der Haube

Lokad verwendet einen unkonventionellen Ansatz zur kombinatorischen Optimierung. Anstatt einen Standard-Solver anzubieten, lösen wir das Problem durch ein spezialisiertes Programmierparadigma namens latente Optimierung. Diese Methode ist entscheidend für die Integration der Erkenntnisse und Expertise unserer Supply Chain Scientists.

Die latente Optimierung führt eine alternative Darstellung des ursprünglichen Problems ein. Diese alternative Darstellung ist eine hochdimensionale Parametrisierung eines einfachen Solvers, der für das vorliegende Problem maßgeschneidert ist. Diese Parameter werden dann durch die iterative Anwendung des parametrisierten Solvers über das ursprüngliche Problem gelernt (was auch stochastische Varianten beinhalten kann). Im Kern ist die latente Optimierung ein Lernprozess.

Das Ergebnis der latenten Optimierung ist ein gut parametrisierter, einfacher Solver, der hochwertige Lösungen für das ursprüngliche Problem sowie für seine Varianten liefert.

Beispiel: Planung eines Luftfahrt-Produktionsstandorts

Betrachten Sie einen Luftfahrt-Hersteller und einen seiner Produktionsstandorte. Dieser Standort montiert ein kritisches Flugzeugbauteil. Das übergeordnete Ziel besteht darin, den Durchsatz des Standorts unter Berücksichtigung der verfügbaren Ressourcen (Mitarbeiter und industrielle Anlagen) zu maximieren.

Dieser Montageprozess umfasst etwa 100 verschiedene Operationen. Es gibt auch etwa 20 verfügbare Slots für die Durchführung dieser Operationen, wobei jeder Slot unterschiedliche Eigenschaften hat. Bestimmte Operationen können nur in bestimmten Slots durchgeführt werden. Ein komplexer Abhängigkeitsgraph verbindet die Operationen, aber anders als bei einer Automobilproduktionslinie bildet dieser Graph keine gerade Sequenz; es gibt beträchtliche Flexibilität in der endgültigen Reihenfolge der Aufgaben.

Darüber hinaus erfordern einige Operationen spezifische Ausrüstungsgegenstände, die in begrenzter Anzahl am Standort vorhanden sind. Viele Operationen hängen auch davon ab, dass der erforderliche Bestand vorhanden ist; manchmal werden wichtige Teile verzögert. Die Operationen variieren darin, wie viele Personen gleichzeitig daran arbeiten können, um die Fertigstellung zu beschleunigen, von 1 bis zu 5 Personen.

Ein Team von etwa 100 Technikern betreibt den Standort in Schichten von 20 bis 30 Personen. Jeder Techniker hat eine von drei Qualifikationsstufen für jede Operation. Die höchste Stufe ermöglicht es dem Techniker, eine Operation durchzuführen und die Arbeit anderer zu überprüfen. Die mittlere Stufe ermöglicht es einem Techniker, seine eigene Arbeit durchzuführen und zu überprüfen. Die niedrigste Stufe ermöglicht einem Techniker, eine Operation durchzuführen, erfordert jedoch die Überprüfung durch einen Kollegen mit der höchsten Qualifikation.

Die Geschäftsleitung des Produktionsstandorts möchte einen minutengenauen Arbeitsplan für die nächsten Wochen, der genau angibt, welcher Techniker an jeder Operation für jedes Bauteil arbeiten wird (wobei jedes Bauteil individuell durch die Seriennummer identifiziert wird). Diese Detailgenauigkeit ist entscheidend, um das Vertrauen in die Solidität des Zeitplans zu gewährleisten.

Die Bedingungen können sich jedoch zu Beginn jeder Schicht ändern. Ein Mitarbeiter kann aufgrund von Krankheit abwesend sein oder ein Teil kann verzögert und somit nicht verfügbar sein. Wenn diese Probleme nicht umgehend gelöst werden, führen sie schnell zu einer Reihe von Ineffizienzen, wodurch Techniker und Anlagen untätig bleiben, während Probleme gelöst werden.

Mit latenter Optimierung kann das Standmanagement einen detaillierten Arbeitsplan für Zehntausende von Aufgaben in den kommenden Wochen erstellen. Sie können das Tool auch in letzter Minute erneut ausführen, um unerwartete Änderungen zu berücksichtigen. Darüber hinaus ist die neu generierte Lösung nicht eine massive zufällige Neuanordnung des ursprünglichen Plans, sondern ein Zeitplan, der dem ursprünglichen Plan sehr ähnlich ist und nur geringfügige Anpassungen erfordert, um die neuesten Bedingungen zu berücksichtigen.