Optimisation latente

L’optimisation latente est un paradigme d’optimisation pionnier par Lokad qui cible les problèmes combinatoires difficiles et complexes. Elle traite également des problèmes stochastiques, qui émergent dès que l’incertitude se présente. L’optimisation latente représente une percée pour des défis tels que l’allocation programmée de ressources. Contrairement aux solveurs classiques, qui opèrent dans l’espace solution, l’optimisation latente opère dans l’espace stratégie. Cette approche permet une ré-optimisation rapide à mesure que les conditions évoluent.

Aperçu de la technologie

L’optimisation latente, introduite en 2024, est la deuxième génération de technologies d’optimisation à usage général développées par Lokad. Elle s’attaque à des problèmes combinatoires plus difficiles que ceux abordés par descente discrète stochastique, bien qu’elle offre un niveau de scalabilité légèrement réduit.

Conceptuellement, les Supply Chain Scientists chez Lokad conçoivent un pipeline de traitement de données qui comprend les étapes suivantes:

1. Préparer les données historiques.
2. Générer des prévisions probabilistes.
3. Produire une stratégie robuste de prise de décision.
4. Ré-optimiser à la dernière minute, dans des conditions modifiées.

Les données historiques sont préparées en utilisant les capacités générales d’ingénierie des données d’Envision ; Envision est le langage spécifique à un domaine de Lokad. Les prévisions probabilistes sont ensuite produites en utilisant differentiable programming, un paradigme idéalement adapté à la modélisation probabiliste et traité comme un citoyen de première classe dans Envision.

Ensuite, l’optimisation latente est utilisée pour générer une stratégie de prise de décision. En essence, le résultat de l’optimisation latente est un solveur spécialisé étroitement adapté au problème spécifique. Enfin, cette stratégie peut être exécutée — et éventuellement réexécutée — dans les conditions finales, légèrement modifiées, afin de produire les décisions requises. Parce que la stratégie s’exécute rapidement, elle peut être utilisée de manière interactive par les personnes impliquées.

Les quatre étapes — (1), (2), (3) et (4) — sont réalisées au sein d’Envision.

Limites des solveurs traditionnels

L’optimisation mathématique est un secteur mature de l’informatique. Une large gamme de solveurs — à la fois propriétaires et open source — est disponible sur le marché. Malheureusement, aucune de ces technologies existantes ne répond à nos exigences, en particulier lorsqu’il s’agit de problèmes de planification serrés.

Les algorithmes de branch-and-bound (et toutes leurs variantes) reposent sur le découpage de la région réalisable en sous-problèmes plus petits (branching) et sur l’utilisation de relaxations (bounding) pour élaguer de larges sections de l’espace de recherche. Cette approche fonctionne mal pour les problèmes de supply chain car ils restent trop ouverts. Bien que l’espace solution soit strictement contraint, il demeure néanmoins énorme. Se contenter de satisfaire les contraintes est loin d’être suffisant pour produire une bonne solution, ce qui compromet le principe même du partitionnement.

Les algorithmes de recherche locale (et toutes leurs variantes) consistent à itérer sur une ou plusieurs solutions actuelles, en examinant des variantes proches. Malheureusement, cette méthode fonctionne également mal car le concept de “localité” n’est pas bien défini dans ces problèmes. Étant donné à quel point ces scénarios sont strictement contraints, la plupart des ajustements locaux à une solution enfreignent tant de contraintes que le processus de recherche ne peut pas aboutir à une solution améliorée.

Chez Lokad, nous nous sommes fixés pour objectif une scalabilité de quelques millions de variables pour des problèmes combinatoires difficiles, tout en ayant la capacité de ré-optimiser en quelques secondes lorsque les conditions évoluent — même si ces changements invalident complètement la solution initiale par des effets de cascade.

Sous le capot

Lokad utilise une approche peu orthodoxe de l’optimisation combinatoire. Plutôt que de proposer un solveur standard, nous abordons le problème à travers un paradigme de programmation spécialisé appelé optimisation latente. Cette méthode est essentielle pour intégrer les connaissances et l’expertise de nos Supply Chain Scientists.

L’optimisation latente introduit une représentation alternative du problème initial. Cette représentation alternative est une paramétrisation haute dimension d’un solveur simple adapté au problème en question. Ces paramètres sont ensuite appris en appliquant de manière itérative le solveur paramétré sur le problème initial (dont beaucoup incluent des variantes stochastiques). Au cœur, l’optimisation latente est un processus d’apprentissage.

Le résultat de l’optimisation latente est un solveur simple et bien paramétré qui produit des solutions de haute qualité pour le problème initial ainsi que pour ses variantes.

Exemple : Planification d’un site de production aéronautique

Considérez un fabricant aéronautique et l’un de ses sites de production. Ce site assemble un composant d’avion critique. L’objectif global est de maximiser le débit du site compte tenu des ressources disponibles (personnel et actifs industriels).

Ce processus d’assemblage implique environ 100 opérations distinctes. Il existe également environ 20 créneaux disponibles pour réaliser ces opérations, chaque créneau ayant des attributs différents. Certaines opérations ne peuvent être effectuées que dans des créneaux spécifiques. Un graphe de dépendances complexe relie les opérations, mais contrairement à une chaîne de production automobile, ce graphe ne constitue pas une séquence linéaire ; il existe une flexibilité considérable dans l’ordre final des tâches.

De plus, certaines opérations nécessitent des équipements spécifiques, qui existent en quantités limitées sur le site. De nombreuses opérations dépendent également de la disponibilité des stocks nécessaires ; parfois, des pièces essentielles sont retardées. Les opérations varient quant au nombre de personnes pouvant y travailler simultanément pour accélérer leur réalisation, allant de 1 à 5 individus au maximum.

Une équipe d’environ 100 techniciens exploite le site par équipes de 20 à 30 personnes. Chaque technicien dispose de l’un des trois niveaux de qualification pour chaque opération. Le niveau le plus élevé permet au technicien d’effectuer une opération et de vérifier le travail effectué par d’autres. Le niveau intermédiaire permet à un technicien d’effectuer une opération et d’auto-vérifier son propre travail. Le niveau le plus bas permet à un technicien d’effectuer une opération, mais nécessite une vérification par un pair possédant la qualification la plus élevée.

La direction du site de production souhaite un planning des tâches à la minute près pour les prochaines semaines, précisant exactement quel technicien travaillera sur chaque opération pour chaque composant (chaque composant étant identifié individuellement par un numéro de série). Ce niveau de détail est essentiel pour garantir la fiabilité du planning.

Cependant, les conditions peuvent évoluer au début de chaque quart de travail. Un employé peut être absent pour cause de maladie, ou une pièce peut être retardée et donc indisponible. Si ces problèmes ne sont pas rapidement traités, ils se transforment rapidement en une série d’inefficacités, laissant les techniciens et les actifs inactifs pendant que les problèmes sont résolus.

Avec l’optimisation latente, la direction du site peut produire un planning détaillé couvrant des dizaines de milliers de tâches pour les semaines à venir. Elle peut également relancer l’outil à la dernière minute pour tenir compte des changements inattendus. De plus, la solution nouvellement générée n’est pas un réaménagement aléatoire massif du plan initial, mais un planning qui ressemble étroitement à la version initiale, nécessitant seulement des ajustements mineurs pour s’adapter aux conditions les plus récentes.