L'optimisation Latente

L’optimisation latente est un paradigme d’optimisation initié par Lokad qui cible des problèmes combinatoires difficiles et complexes. Elle gère également des problèmes stochastiques, qui surgissent dès qu’une incertitude est présente. L’optimisation latente représente une percée pour des défis tels que l’allocation planifiée des 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 re-optimisation rapide à mesure que les conditions évoluent.

Vue d’ensemble de la technologie

L’optimisation latente, introduite en 2024, représente 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 traités par stochastic discrete descent, bien qu’elle présente un niveau de scalabilité légèrement réduit.

Conceptuellement, les Supply Chain Scientists chez Lokad conçoivent une chaîne 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 de prise de décision robuste.
4. Re-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éal pour la modélisation probabiliste et considéré 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 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 des personnes impliquées.

Les quatre étapes—(1), (2), (3) et (4)—sont réalisées dans Envision.

Limites des solveurs traditionnels

L’optimisation mathématique est un segment mûr de l’informatique. Une large gamme de solveurs—tant propriétaires qu’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 le partitionnement de la région faisable en sous-problèmes plus petits (branching) et 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 les 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 d’une solution violent tellement de contraintes que le processus de recherche ne peut pas aboutir à une solution améliorée.

Chez Lokad, nous nous sommes fixé comme objectif de scalabilité de quelques millions de variables pour des problèmes combinatoires difficiles, avec la capacité de re-optimiser en quelques secondes lorsque les conditions changent—même si ces changements invalident complètement la solution initiale par effet cascade.

Dans les coulisses

Lokad utilise une approche non conventionnelle de l’optimisation combinatoire. Plutôt que de proposer un solveur standard, nous traitons le problème à l’aide d’un paradigme de programmation spécialisé appelé l’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 original. Cette représentation alternative est une paramétrisation en 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é au problème original (dont beaucoup incluent des variantes stochastiques). Au cœur de cette approche, l’optimisation latente est 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érez un fabricant aéronautique et l’un de ses sites de production. Ce site assemble un composant d’avion critique. L’objectif général 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 forme 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 subissent des retards. Les opérations varient quant au nombre de personnes pouvant y travailler simultanément pour accélérer leur achèvement, allant de 1 à 5 individus.

Une main-d’œuvre d’environ 100 techniciens exploite le site par équipes de 20 à 30 personnes. Chaque technicien possè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 réalisé par les autres. Le niveau intermédiaire permet à un technicien d’exécuter 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 de travail détaillé à la minute près pour les prochaines semaines, précisant exactement quel technicien travaillera sur quelle opération pour chaque composant (chaque composant étant individuellement identifié par son 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 poste. Un employé peut être absent en raison d’une maladie, ou une pièce peut être retardée et donc indisponible. Si ces problèmes ne sont pas traités rapidement, ils se transforment rapidement en une série d’inefficacités, laissant techniciens et actifs inactifs pendant la résolution des problèmes.

Grâce à l’optimisation latente, la direction du site peut produire un planning de travail détaillé englobant des dizaines de milliers de tâches pour les semaines à venir. Elle peut également relancer l’outil à la dernière minute pour tenir compte de changements inattendus. De plus, la solution nouvellement générée n’est pas une réorganisation aléatoire massive 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.