Optimisation Latente

L’optimisation latente est un paradigme d’optimisation pionnier développé par Lokad qui cible les problèmes combinatoires difficiles et complexes. Il gère également les problèmes stochastiques, qui surviennent chaque fois que l’incertitude est présente. L’optimisation latente représente une avancée pour des défis tels que l’allocation de ressources planifiée. Contrairement aux solveurs classiques, qui opèrent dans l’espace des solutions, l’optimisation latente opère dans l’espace de la 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 polyvalentes développées par Lokad. Elle s’attaque à des problèmes combinatoires plus difficiles que ceux abordés par la descente discrète stochastique, bien qu’elle présente un niveau de scalabilité légèrement réduit.

Conceptuellement, les Scientifiques de la Supply Chain chez Lokad conçoivent un pipeline de traitement des 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, sous des conditions modifiées.

Les données historiques sont préparées en utilisant les capacités d’ingénierie des données générales d’Envision ; Envision est le langage spécifique au domaine de Lokad. Les prévisions probabilistes sont ensuite produites en utilisant la programmation différentiable, 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é spécifiquement adapté au problème spécifique. Enfin, cette stratégie peut être exécutée, et éventuellement réexécutée, sous les conditions finales, légèrement changeantes, pour produire les décisions requises. Comme 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 segment 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ée.

Les algorithmes de branch-and-bound (et toutes leurs variantes) reposent sur la partition de la région réalisable en sous-problèmes plus petits (branchement) et utilisent des relaxations (bornage) 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. Alors que l’espace des solutions est strictement contraint, il reste énorme. Se contenter de satisfaire les contraintes est loin d’être suffisant pour produire une bonne solution, ce qui compromet la prémisse de base de la partition.

Les algorithmes de recherche locale (et toutes leurs variantes) tournent autour de l’itération sur une ou plusieurs solutions actuelles, 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 violent tellement de contraintes que le processus de recherche ne peut pas récupérer une solution améliorée.

À Lokad, nous avons fixé un objectif de scalabilité de quelques millions de variables pour les problèmes combinatoires difficiles, ainsi que la capacité de se réoptimiser en quelques secondes lorsque les conditions changent, même si ces changements invalident complètement la solution initiale à travers des effets en cascade.

Sous le capot

Lokad utilise une approche non conventionnelle pour l’optimisation combinatoire. Plutôt que d’offrir 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 idées et l’expertise de nos Supply Chain Scientists.

L’optimisation latente introduit une représentation alternative du problème original. Cette représentation alternative est une paramétrisation multidimensionnelle 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 original (qui peut inclure des variantes stochastiques). Au cœur de l’optimisation latente se trouve un processus d’apprentissage.

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

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

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

Ce processus d’assemblage implique environ 100 opérations distinctes. Il y a également environ 20 créneaux disponibles pour effectuer 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épendance complexe relie les opérations, mais contrairement à une ligne de production automobile, ce graphe ne forme pas une séquence droite ; il y a une flexibilité considérable dans l’ordonnancement 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 en fonction du nombre de personnes pouvant travailler simultanément pour accélérer la réalisation, allant de 1 à 5 individus.

Une équipe d’environ 100 techniciens opère le site par roulements de 20 à 30 personnes. Chaque technicien a 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 et de vérifier lui-même 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 ayant la qualification la plus élevée.

La direction du site de production souhaite un planning minute par minute pour les prochaines semaines, spécifiant exactement quel technicien travaillera sur chaque opération pour chaque composant (chaque composant étant identifié individuellement par 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 roulement. Un employé peut être absent en raison d’une maladie, ou une pièce peut être retardée et donc non disponible. Si ces problèmes ne sont pas rapidement résolus, 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é englobant des dizaines de milliers de tâches pour les semaines à venir. Ils peuvent également relancer l’outil au dernier moment pour tenir compte des changements inattendus. De plus, la solution nouvellement générée n’est pas un remaniement aléatoire massif du plan original, mais un planning qui ressemble étroitement à la version initiale, ne nécessitant que des ajustements mineurs pour s’adapter aux conditions les plus récentes.