00:18 Introduction
02:18 Contexte
12:08 Pourquoi optimiser ? 1/2 Prévision avec Holt-Winters
17:32 Pourquoi optimiser ? 2/2 - Problème de routage des véhicules
20:49 L’histoire jusqu’à présent
22:21 Sciences auxiliaires (récapitulatif)
23:45 Problèmes et solutions (récapitulatif)
27:12 Optimisation mathématique
28:09 Convexité
34:42 Stochastique
42:10 Multi-objectif
46:01 Conception du solveur
50:46 Leçons de Deep (Learning)
01:10:35 Optimisation mathématique
01:10:58 “Vrai” programmation
01:12:40 Recherche locale
01:19:10 Descente de gradient stochastique
01:26:09 Différenciation automatique
01:31:54 Programmation différentielle (circa 2018)
01:35:36 Conclusion
01:37:44 Prochain cours et questions du public
Description
L’optimisation mathématique est le processus de minimisation d’une fonction mathématique. Presque toutes les techniques modernes d’apprentissage statistique - c’est-à-dire la prévision si l’on adopte une perspective de supply chain - reposent sur l’optimisation mathématique au cœur de leur fonctionnement. De plus, une fois les prévisions établies, l’identification des décisions les plus rentables repose également, au cœur de leur fonctionnement, sur l’optimisation mathématique. Les problèmes de supply chain impliquent fréquemment de nombreuses variables. Ils sont également généralement stochastiques par nature. L’optimisation mathématique est un pilier de la pratique moderne de la supply chain.
Transcription complète
Bienvenue dans cette série de cours sur la supply chain. Je suis Joannes Vermorel et aujourd’hui je vais présenter “L’optimisation mathématique pour la supply chain”. L’optimisation mathématique est la manière bien définie, formalisée et calculable de trouver la meilleure solution à un problème donné. Tous les problèmes de prévision peuvent être considérés comme des problèmes d’optimisation mathématique. Toutes les situations de prise de décision dans la supply chain et en dehors peuvent également être considérées comme des problèmes d’optimisation mathématique. En fait, la perspective de l’optimisation mathématique est tellement ancrée dans notre vision moderne du monde qu’il est devenu très difficile de définir le verbe “optimiser” en dehors du tout petit cadre que nous offre le paradigme de l’optimisation mathématique.
Maintenant, la littérature scientifique sur l’optimisation mathématique est vaste, tout comme l’écosystème logiciel qui propose des outils d’optimisation mathématique. Malheureusement, la plupart d’entre eux sont peu utiles et pertinents en ce qui concerne la supply chain. L’objectif de ce cours sera double : premièrement, nous voulons comprendre comment aborder l’optimisation mathématique pour obtenir quelque chose de précieux et d’utilisable dans une perspective de supply chain. Le deuxième élément consistera à identifier, dans ce vaste paysage, certains des éléments les plus précieux qui peuvent être trouvés.
La définition formelle de l’optimisation mathématique est simple : vous pensez à une fonction qui est généralement appelée la fonction de perte, et cette fonction est réelle, elle ne produit que des nombres. Ce que vous voulez, c’est identifier l’entrée (X0) qui représente la meilleure valeur qui minimise la fonction de perte. C’est généralement le paradigme de l’optimisation mathématique, et il est trompeusement simple. Nous verrons qu’il y a beaucoup de choses à dire sur cette perspective générale.
Ce domaine, je crois, lorsque nous pensons en termes d’optimisation mathématique appliquée, a été principalement développé sous le nom de recherche opérationnelle, que nous définissons plus spécifiquement comme la recherche opérationnelle classique qui s’est déroulée des années 1940 à la fin des années 1970 au XXe siècle. L’idée est que la recherche opérationnelle classique, par rapport à l’optimisation mathématique, se souciait vraiment des problèmes commerciaux. L’optimisation mathématique se soucie de la forme générale du problème d’optimisation, beaucoup moins de savoir si le problème a une quelconque signification commerciale. Au contraire, la recherche opérationnelle classique faisait essentiellement de l’optimisation, mais pas sur n’importe quel type de problèmes - sur des problèmes qui étaient identifiés comme étant importants pour les entreprises.
Intéressant, nous sommes passés de la recherche opérationnelle à l’optimisation mathématique de la même manière que nous sommes passés des prévisions, qui ont émergé au début du XXe siècle en tant que domaine concerné par les prévisions générales des niveaux d’activité économique future, généralement associées aux prévisions de séries temporelles. Ce domaine a été essentiellement remplacé par l’apprentissage automatique, qui se souciait plus largement de faire des prédictions sur un champ d’application beaucoup plus large de problèmes. Nous pourrions dire que nous avons eu à peu près la même sorte de transition de la recherche opérationnelle à l’optimisation mathématique que celle qui a eu lieu entre les prévisions et l’apprentissage automatique. Maintenant, lorsque j’ai dit que l’ère classique de la recherche opérationnelle s’est terminée à la fin des années 70, j’avais une date très précise en tête. En février 1979, Russell Ackoff a publié un article stupéfiant intitulé “L’avenir de la recherche opérationnelle est passé”. Pour comprendre cet article, que je considère comme un véritable jalon dans l’histoire de la science de l’optimisation, il faut comprendre que Russell Ackoff est essentiellement l’un des pères fondateurs de la recherche opérationnelle.
Lorsqu’il a publié cet article, il n’était plus un jeune homme ; il avait 60 ans. Ackoff est né en 1919 et avait passé pratiquement toute sa carrière à travailler sur la recherche opérationnelle. Lorsqu’il a publié son article, il a essentiellement déclaré que la recherche opérationnelle avait échoué. Non seulement elle n’a pas donné de résultats, mais l’intérêt de l’industrie pour ce domaine diminuait, de sorte qu’il y avait moins d’intérêt à la fin des années 90 qu’il y en avait il y a 20 ans.
Ce qui est très intéressant à comprendre, c’est que la cause n’est absolument pas le fait que les ordinateurs de l’époque étaient beaucoup plus faibles que ceux que nous avons aujourd’hui. Le problème n’a rien à voir avec la limitation en termes de puissance de traitement. Nous sommes à la fin des années 70 ; les ordinateurs sont très modestes par rapport à ce que nous avons de nos jours, mais ils peuvent quand même effectuer des millions d’opérations arithmétiques dans un délai raisonnable. Le problème n’est pas lié à la limitation de la puissance de traitement, surtout à une époque où la puissance de traitement progresse incroyablement rapidement.
Au fait, cet article est une lecture fantastique. Je suggère vraiment au public d’y jeter un coup d’œil ; vous pouvez facilement le trouver avec votre moteur de recherche préféré. Cet article est très accessible et bien écrit. Bien que les problèmes que Ackoff soulève dans cet article résonnent encore très fortement quatre décennies plus tard, à bien des égards, l’article est très précurseur de nombreux problèmes qui continuent de tourmenter les chaînes d’approvisionnement actuelles.
Alors, quel est le problème alors ? Le problème est que ce paradigme, où vous prenez une fonction et l’optimisez, vous pouvez prouver que votre processus d’optimisation identifie une bonne solution, voire une solution optimale. Cependant, comment prouver que la fonction de perte que vous optimisez présente un intérêt pour l’entreprise ? Le problème est que lorsque je dis que nous pouvons optimiser un problème donné ou une fonction donnée, que se passe-t-il si ce que vous optimisez est en réalité une illusion ? Et si cette chose n’a rien à voir avec la réalité de l’entreprise que vous essayez d’optimiser ?
Ici réside l’essence du problème, et c’est la raison pour laquelle ces premières tentatives ont essentiellement toutes échoué. C’est parce qu’il s’est avéré que lorsque vous inventez une sorte d’expression mathématique censée représenter l’intérêt de l’entreprise, ce que vous obtenez est une illusion mathématique. C’est littéralement ce que Russell Ackoff souligne dans cet article, et il est à un stade de sa carrière où il joue à ce jeu depuis très longtemps et reconnaît que cela ne mène essentiellement nulle part. Dans son article, il partage l’avis selon lequel le domaine a échoué, et il propose son diagnostic, mais il n’a pas grand-chose à offrir comme solution. C’est très intéressant car l’un des pères fondateurs, un chercheur très respecté et reconnu, affirme que ce domaine de recherche est une impasse. Il passera le reste de sa vie, qui est encore assez longue, à passer entièrement d’une perspective quantitative sur l’optimisation des entreprises à une perspective qualitative. Il passera les trois dernières décennies de sa vie à adopter des méthodes qualitatives et produira encore un travail très intéressant dans la deuxième partie de sa vie après ce tournant.
Maintenant, en ce qui concerne cette série de conférences, que faisons-nous car les points soulevés par Russell Ackoff concernant la recherche opérationnelle restent très valables de nos jours ? En réalité, j’ai déjà commencé à aborder les plus grands problèmes que Ackoff soulignait, et à l’époque, lui et ses pairs n’avaient pas de solutions à offrir. Ils pouvaient diagnostiquer le problème, mais ils n’avaient pas de solution. Dans cette série de conférences, les solutions que je propose sont de nature méthodologique, tout comme le fait qu’Ackoff souligne qu’il y a un problème méthodologique profond avec cette perspective de recherche opérationnelle.
Les méthodes que je propose sont essentiellement de deux types : d’un côté, le personnel de la chaîne d’approvisionnement, et de l’autre côté, la méthode intitulée “optimisation expérimentale” qui s’avère être vraiment complémentaire à l’optimisation mathématique. De plus, contrairement à la recherche opérationnelle qui prétend être d’intérêt ou de pertinence commerciale, la façon dont j’aborde le problème aujourd’hui ne passe pas par l’angle ou les lunettes de la recherche opérationnelle. J’aborde le problème à travers les lunettes de l’optimisation mathématique, que je positionne comme une science auxiliaire pure pour la chaîne d’approvisionnement. Je dis qu’il n’y a rien d’intrinsèquement fondamental dans l’optimisation mathématique pour la chaîne d’approvisionnement ; c’est simplement d’un intérêt fondamental. C’est juste un moyen, pas une fin. C’est là que ça diffère. Le point peut être très simple, mais il est très important quand il s’agit d’obtenir des résultats de qualité prédictive avec tout cela.
Maintenant, pourquoi voulons-nous même optimiser en premier lieu ? La plupart des algorithmes de prévision ont un problème d’optimisation mathématique au cœur. Sur cet écran, ce que vous pouvez voir, c’est l’algorithme de prévision de séries temporelles Holt-Winters multiplicatif très classique. Cet algorithme est principalement d’intérêt historique ; je ne recommanderais à aucune chaîne d’approvisionnement actuelle d’utiliser cet algorithme spécifique. Mais pour des raisons de simplicité, il s’agit d’une méthode paramétrique très simple, et elle est si concise que vous pouvez la mettre entièrement sur un seul écran. Ce n’est même pas très verbeux.
Toutes les variables que vous pouvez voir à l’écran ne sont que des nombres simples ; il n’y a pas de vecteurs impliqués. Essentiellement, Y(t) est votre estimation ; c’est votre prévision de séries temporelles. Ici, à l’écran, cela va prévoir H périodes à l’avance, donc H est comme l’horizon. Et vous pouvez penser que vous travaillez réellement sur Y(t), qui est essentiellement votre série temporelle. Vous pouvez penser à des données de ventes agrégées hebdomadaires ou mensuelles. Ce modèle a essentiellement trois composantes : il a Lt, qui est le niveau (vous avez un niveau par période), Bt, qui est la tendance, et St, qui est une composante saisonnière. Lorsque vous dites que vous voulez apprendre le modèle Holt-Winters, vous avez trois paramètres : alpha, beta et gamma. Ces trois paramètres ne sont essentiellement que des nombres entre zéro et un. Donc, vous avez trois paramètres, tous des nombres entre zéro et un, et lorsque vous dites que vous voulez appliquer l’algorithme Holt-Winters, cela signifie simplement que vous allez identifier les valeurs appropriées pour ces trois paramètres, et c’est tout. L’idée est que ces paramètres, alpha, beta et gamma, seront les meilleurs s’ils minimisent le type d’erreur que vous avez spécifié pour votre prévision. Sur cet écran, vous pouvez voir une erreur quadratique moyenne, qui est très classique.
Le point concernant l’optimisation mathématique est de trouver une méthode pour identifier les bonnes valeurs de paramètres pour alpha, beta et gamma. Que pouvons-nous faire ? Eh bien, la méthode la plus simple et la plus simpliste est quelque chose comme la recherche en grille. La recherche en grille dirait que nous allons simplement explorer toutes les valeurs. Comme ce sont des nombres fractionnaires, il y a un nombre infini de valeurs, donc nous allons en fait choisir une résolution, disons des pas de 0,1, et nous irons par incréments de 0,1. Comme nous avons trois variables entre 0 et 1, nous allons par incréments de 0,1 ; cela fait environ 1 000 itérations pour passer en revue et identifier la meilleure valeur, compte tenu de cette résolution.
Cependant, cette résolution est assez faible. 0,1 vous donne une résolution d’environ 10 % sur l’échelle de vos paramètres. Donc peut-être que vous voulez opter pour 0,01, ce qui est beaucoup mieux ; c’est une résolution de 1 %. Cependant, si vous faites cela, le nombre de combinaisons explose vraiment. Vous passez de 1 000 combinaisons à un million de combinaisons, et vous voyez que c’est le problème de la recherche en grille : très rapidement, vous atteignez un mur combinatoire, et vous avez un nombre énorme d’options.
L’optimisation mathématique consiste à concevoir des algorithmes qui vous donnent plus de résultats pour votre argent pour une quantité donnée de ressources informatiques que vous voulez consacrer au problème. Pouvez-vous obtenir une solution bien meilleure qu’une simple recherche brute ? La réponse est oui, absolument.
Alors que pouvons-nous faire dans ce cas pour obtenir une meilleure solution en investissant moins de ressources informatiques ? Tout d’abord, nous pourrions utiliser une sorte de gradient. L’ensemble de l’expression pour Holt-Winters est complètement différentiable, à l’exception d’une seule division qui est un cas limite minuscule et relativement facile à gérer. Donc, cette expression entière, y compris la fonction de perte, est entièrement différentiable. Nous pourrions utiliser un gradient pour guider notre recherche ; ce serait une approche.
Une autre approche consisterait à dire que, dans la pratique, dans la supply chain, vous avez peut-être des tonnes de séries temporelles. Donc, au lieu de traiter chaque série temporelle indépendamment, ce que vous voulez faire, c’est une recherche en grille pour les 1 000 premières séries temporelles, et vous allez investir, puis vous allez identifier les combinaisons pour alpha, beta et gamma qui sont bonnes. Ensuite, pour toutes les autres séries temporelles, vous allez simplement choisir parmi cette liste restreinte de candidats pour identifier la meilleure solution.
Vous voyez, il y a plein d’idées simples sur la façon dont vous pouvez faire beaucoup mieux qu’une simple approche de recherche en grille, et l’essence de l’optimisation mathématique, et ensuite toutes sortes de problèmes de prise de décision peuvent également être vus typiquement comme des problèmes d’optimisation mathématique.
Par exemple, le problème de routage des véhicules que vous pouvez voir à l’écran peut être considéré comme un problème d’optimisation mathématique. Il s’agit de choisir la liste des points. Je n’ai pas écrit la version formelle du problème car elle est relativement variable et n’apporte pas beaucoup d’informations. Mais si vous voulez y réfléchir, vous pouvez simplement penser : “J’ai des points, je peux attribuer une sorte de pseudo-rang qui est juste un score à chaque point, puis j’ai un algorithme qui trie tous les points par pseudo-rangs dans l’ordre croissant, et c’est ma route.” L’objectif de l’algorithme sera d’identifier les valeurs de ces pseudo-rangs qui vous donnent les meilleures routes.
Maintenant, avec ce problème, nous voyons que nous avons un problème où soudainement la recherche en grille n’est même pas une option. Nous avons des dizaines de points, et si nous devions essayer toutes les combinaisons, cela serait beaucoup trop grand. De plus, le gradient ne va pas nous aider, du moins il n’est pas évident comment il va nous aider, car le problème est très discret de nature, et il n’y a pas quelque chose qui ressemble à une descente de gradient évidente pour ce genre de problème.
Cependant, il s’avère que si nous voulons aborder ce genre de problème, il existe des heuristiques très puissantes qui ont été identifiées dans la littérature. Par exemple, l’heuristique du two-opt, publiée par Croes en 1958, vous donne une heuristique très simple. Vous commencez par une route aléatoire, et dans cette route, chaque fois que la route se croise, vous appliquez une permutation pour supprimer la croisement. Donc, vous commencez par une route aléatoire, et le premier croisement que vous observez, vous faites la permutation pour supprimer le croisement, et ensuite vous répétez le processus avec l’heuristique jusqu’à ce qu’il ne reste plus de croisements. Ce que vous obtiendrez de cette heuristique très simple est en fait une très bonne solution. Ce n’est peut-être pas optimal au sens mathématique strict, donc ce n’est pas nécessairement la solution parfaite ; cependant, c’est une très bonne solution, et vous pouvez l’obtenir avec une quantité relativement minimale de ressources informatiques.
Le problème avec l’heuristique du two-opt, c’est que c’est une heuristique très fine, mais elle est incroyablement spécifique à ce seul problème. Ce qui est vraiment intéressant pour l’optimisation mathématique, c’est d’identifier des méthodes qui fonctionnent sur de grandes classes de problèmes au lieu d’avoir une heuristique qui ne fonctionne que pour une version spécifique d’un problème. Donc, nous voulons avoir des méthodes très générales.
Jusqu’à présent dans cette série de conférences : cette conférence fait partie d’une série de conférences, et ce chapitre présent est consacré aux sciences auxiliaires de la supply chain. Dans le premier chapitre, j’ai présenté mes points de vue sur la supply chain à la fois en tant que domaine d’étude et en tant que pratique. Le deuxième chapitre était consacré à la méthodologie, et en particulier, nous avons introduit une méthodologie qui est d’une importance capitale pour la présente conférence, qui est l’optimisation expérimentale. C’est la clé pour résoudre le problème très valide identifié par Russell Ackoff il y a des décennies. Le troisième chapitre est entièrement consacré au personnel de la supply chain. Dans cette conférence, nous nous concentrons sur l’identification du problème que nous sommes sur le point de résoudre, plutôt que de mélanger la solution et le problème. Dans ce quatrième chapitre, nous étudions toutes les sciences auxiliaires de la supply chain. Il y a une progression depuis le niveau le plus bas en termes de matériel, en passant par le niveau des algorithmes, puis à l’optimisation mathématique. Nous progressons en termes de niveaux d’abstraction tout au long de cette série.
Juste un bref rappel sur les sciences auxiliaires : elles offrent une perspective sur la supply chain elle-même. La présente conférence ne concerne pas la supply chain en soi, mais plutôt l’une des sciences auxiliaires de la supply chain. Cette perspective fait une différence significative par rapport à la perspective classique de la recherche opérationnelle, qui était censée être une fin en soi, par opposition à l’optimisation mathématique, qui est un moyen pour atteindre une fin mais pas une fin en soi, du moins en ce qui concerne la supply chain. L’optimisation mathématique ne se soucie pas des spécificités commerciales, et la relation entre l’optimisation mathématique et la supply chain est similaire à la relation entre la chimie et la médecine. D’un point de vue moderne, vous n’avez pas besoin d’être un chimiste brillant pour être un médecin brillant ; cependant, un médecin qui prétend ne rien savoir en chimie semblerait suspect.
L’optimisation mathématique suppose que le problème est connu. Elle ne se soucie pas de la validité du problème, mais se concentre plutôt sur la maximisation de ce que vous pouvez faire pour un problème donné en termes d’optimisation. En quelque sorte, c’est comme un microscope - très puissant mais avec un champ de vision incroyablement étroit. Le danger, lorsque nous revenons à la discussion sur l’avenir de la recherche opérationnelle, c’est que si vous pointez votre microscope au mauvais endroit, vous pourriez être distrait par des défis intellectuels intéressants mais finalement sans importance.
C’est pourquoi l’optimisation mathématique doit être utilisée en conjonction avec l’optimisation expérimentale. L’optimisation expérimentale, que nous avons abordée dans la conférence précédente, est le processus par lequel vous pouvez itérer avec les retours du monde réel vers de meilleures versions du problème lui-même. L’optimisation expérimentale est un processus de mutation non pas de la solution mais du problème, de sorte que de manière itérative, vous pouvez converger vers un bon problème. C’est là que réside l’essentiel de la question, et là où Russell Ackoff et ses pairs de l’époque n’avaient pas de solution. Ils avaient les outils pour optimiser un problème donné, mais pas les outils pour faire muter le problème jusqu’à ce que le problème soit bon. Si vous prenez un problème mathématique tel que vous pouvez l’écrire dans votre tour d’ivoire, sans retour du monde réel, ce que vous obtenez est une fantaisie. Votre point de départ, lorsque vous commencez un processus d’optimisation expérimentale, est juste une fantaisie. Il faut le retour du monde réel pour que cela fonctionne. L’idée est d’aller et venir entre l’optimisation mathématique et l’optimisation expérimentale. À chaque étape de votre processus d’optimisation expérimentale, vous utiliserez des outils d’optimisation mathématique. L’objectif est de minimiser à la fois les ressources informatiques et les efforts d’ingénierie, permettant au processus de converger vers la prochaine version du problème.
Dans cette conférence, nous affinerons d’abord notre compréhension de la perspective de l’optimisation mathématique. La définition formelle est trompeusement simple, mais il y a des complexités dont nous devons être conscients pour atteindre une pertinence pratique dans le cadre de la supply chain. Nous explorerons ensuite deux grandes classes de solveurs qui représentent l’état de l’art en matière d’optimisation mathématique du point de vue de la supply chain.
Tout d’abord, discutons de la convexité et des premiers travaux en optimisation mathématique. La recherche opérationnelle s’est initialement concentrée sur les fonctions de perte convexes. Une fonction est dite convexe si elle respecte certaines propriétés. Intuitivement, une fonction est convexe si, pour deux points quelconques sur la variété définie par la fonction, la ligne droite reliant ces points sera toujours au-dessus des valeurs prises par la fonction entre ces points.
La convexité est essentielle pour permettre une véritable optimisation mathématique, où vous pouvez prouver des résultats. Intuitivement, lorsque vous avez une fonction convexe, cela signifie que pour n’importe quel point de la fonction (n’importe quelle solution candidate), vous pouvez toujours regarder autour de vous et trouver une direction dans laquelle vous pouvez descendre. Peu importe où vous commencez, vous pouvez toujours descendre, et descendre est toujours un bon mouvement. Le seul point où vous ne pouvez pas descendre plus bas est essentiellement le point optimal. Je simplifie ici ; il y a des cas particuliers où vous avez des solutions non uniques ou pas de solutions du tout. Mais en mettant de côté quelques cas particuliers, le seul point où vous ne pouvez pas optimiser davantage avec une fonction convexe est le point optimal. Sinon, vous pouvez toujours descendre, et descendre est un bon mouvement.
Il y a eu énormément de recherches sur les fonctions convexes, et divers paradigmes de programmation ont émergé au fil des ans. LP signifie programmation linéaire, et d’autres paradigmes incluent la programmation conique d’ordre deux, la programmation géométrique (traitant des polynômes), la programmation semi-définie (impliquant des matrices avec des valeurs propres positives) et la programmation conique géométrique. Ces cadres ont tous en commun qu’ils traitent de problèmes convexes structurés. Ils sont convexes à la fois dans leur fonction de perte et dans les contraintes qui restreignent les solutions éligibles.
Ces cadres ont suscité un très grand intérêt, avec une intense production de littérature scientifique. Cependant, malgré leurs noms impressionnants, ces paradigmes ont très peu d’expressivité. Même les problèmes simples dépassent les capacités de ces cadres. Par exemple, l’optimisation des paramètres de Holt-Winters, un modèle de prévision de base des années 1960, dépasse déjà ce que l’un de ces cadres peut faire. De même, le problème de routage des véhicules et le problème du voyageur de commerce, qui sont tous deux des problèmes simples, dépassent les capacités de ces cadres.
C’est pourquoi je disais dès le début qu’il y a eu une énorme quantité de littérature, mais qu’il y a très peu d’utilisation. Le seul point où vous ne pouvez pas descendre plus bas est essentiellement le point optimal. Je simplifie ici ; il y a des cas particuliers où vous avez des solutions non uniques ou pas de solutions du tout. Mais en mettant de côté quelques cas particuliers, le seul point où vous ne pouvez pas optimiser davantage avec une fonction convexe est le point optimal. Sinon, vous pouvez toujours descendre, et descendre est un bon mouvement.
Il y a eu énormément de recherches sur les fonctions convexes, et divers paradigmes de programmation ont émergé au fil des ans. LP signifie programmation linéaire, et d’autres paradigmes incluent la programmation conique d’ordre deux, la programmation géométrique (traitant des polynômes), la programmation semi-définie (impliquant des matrices avec des valeurs propres positives) et la programmation conique géométrique. Ces cadres ont tous en commun qu’ils traitent de problèmes convexes structurés. Ils sont convexes à la fois dans leur fonction de perte et dans les contraintes qui restreignent les solutions éligibles.
Ces cadres ont suscité un très grand intérêt, avec une intense production de littérature scientifique. Cependant, malgré leurs noms impressionnants, ces paradigmes ont très peu d’expressivité. Même les problèmes simples dépassent les capacités de ces cadres. Par exemple, l’optimisation des paramètres de Holt-Winters, un modèle de prévision de base des années 1960, dépasse déjà ce que l’un de ces cadres peut faire. De même, le problème de routage des véhicules et le problème du voyageur de commerce, qui sont tous deux des problèmes simples, dépassent les capacités de ces cadres.
C’est pourquoi je disais dès le début qu’il y a eu un énorme corpus de littérature, mais qu’il y a très peu d’utilisation. Une partie du problème était une focalisation erronée sur les solveurs d’optimisation mathématique pure. Ces solveurs sont très intéressants d’un point de vue mathématique car ils permettent de produire des preuves mathématiques, mais ils ne peuvent être utilisés qu’avec des problèmes littéralement jouets ou complètement inventés. Une fois dans le monde réel, ils échouent, et il y a eu très peu de progrès dans ces domaines au cours des dernières décennies. En ce qui concerne la supply chain, presque rien, à l’exception de quelques niches, n’a de pertinence pour ces solveurs.
Un autre aspect, qui a été complètement négligé et ignoré pendant l’ère classique de la recherche opérationnelle, est la randomité. La randomité ou la stochasticité est d’une importance capitale de deux manières radicalement différentes. La première façon dont nous devons aborder la randomité est dans le solveur lui-même. De nos jours, tous les solveurs de pointe exploitent largement les processus stochastiques en interne. C’est très intéressant par opposition à un processus entièrement déterministe. Je parle du fonctionnement interne du solveur, de la pièce de logiciel qui met en œuvre les techniques d’optimisation mathématique.
La raison pour laquelle tous les solveurs de pointe exploitent largement les processus stochastiques a à voir avec la manière dont le matériel informatique moderne existe. L’alternative à la randomité lors de l’exploration des solutions est de se souvenir de ce que vous avez fait dans le passé, afin de ne pas rester bloqué dans la même boucle. Si vous devez vous souvenir, vous consommerez de la mémoire. Le problème réside dans le fait que nous devons effectuer de nombreuses lectures en mémoire. Une façon d’introduire de la randomité est généralement un moyen de soulager largement le besoin d’accès aléatoire à la mémoire.
En rendant votre processus stochastique, vous pouvez éviter de sonder votre propre base de données de ce que vous avez testé ou non parmi les solutions possibles pour le problème que vous souhaitez optimiser. Vous le faites un peu au hasard, mais pas complètement. Cela a une importance clé dans pratiquement tous les solveurs modernes. L’un des aspects quelque peu contre-intuitifs d’un processus stochastique est que bien que vous puissiez avoir un solveur stochastique, la sortie peut encore être assez déterministe. Pour comprendre cela, considérez l’analogie d’une série de tamis. Un tamis est fondamentalement un processus stochastique physique, où vous appliquez des mouvements aléatoires et le processus de tamisage a lieu. Bien que le processus soit complètement aléatoire, le résultat est complètement déterministe. À la fin, vous obtenez un résultat complètement prévisible à partir du processus de tamisage, même si votre processus était fondamentalement aléatoire. C’est exactement le genre de chose qui se produit avec les solveurs stochastiques bien conçus. C’est l’un des ingrédients clés des solveurs modernes.
Un autre aspect, qui est orthogonal en ce qui concerne l’aléatoire, est la nature stochastique des problèmes eux-mêmes. Cela était principalement absent de l’ère classique de la recherche opérationnelle - l’idée que votre fonction de perte est bruitée et que toute mesure que vous en obtiendrez aura un certain degré de bruit. C’est presque toujours le cas dans la supply chain. Pourquoi ? La réalité est que dans la supply chain, chaque fois que vous prenez une décision, c’est parce que vous anticipez certains événements futurs. Si vous décidez d’acheter quelque chose, c’est parce que vous anticipez qu’il y aura un besoin pour cela plus tard dans le futur. Le futur n’est pas écrit, donc vous pouvez avoir des aperçus sur le futur, mais l’aperçu n’est jamais parfait. Si vous décidez de produire un produit maintenant, c’est parce que vous vous attendez à ce qu’il y ait une demande pour ce produit plus tard dans le futur. La qualité de votre décision, qui est de produire aujourd’hui, dépend de conditions futures incertaines, et donc toute décision que vous prenez dans la supply chain aura une fonction de perte qui varie en fonction de ces conditions futures qui ne peuvent pas être contrôlées. Le genre d’aléatoire dû à la gestion des événements futurs est irréductible, et cela est d’un intérêt clé car cela signifie que nous traitons fondamentalement des problèmes stochastiques.
Cependant, si nous revenons aux solveurs mathématiques classiques, nous constatons que cet aspect est complètement absent, ce qui pose un gros problème. Cela signifie que nous avons des classes de solveurs qui ne peuvent même pas comprendre le genre de problèmes auxquels nous serons confrontés, car les problèmes qui seront d’intérêt, où nous voulons appliquer l’optimisation mathématique, seront de nature stochastique. Je parle du bruit dans la fonction de perte.
Il y a une objection selon laquelle si vous avez un problème stochastique, vous pouvez toujours le transformer en un problème déterministe grâce à l’échantillonnage. Si vous évaluez votre fonction de perte bruitée 10 000 fois, vous pouvez obtenir une fonction de perte approximativement déterministe. Cependant, cette approche est incroyablement inefficace car elle introduit une surcharge de 10 000 fois sur votre processus d’optimisation. La perspective de l’optimisation mathématique consiste à obtenir les meilleurs résultats pour vos ressources informatiques limitées. Il ne s’agit pas d’investir une quantité infiniment grande de ressources informatiques pour résoudre le problème. Nous devons faire face à une quantité finie de ressources informatiques, même si cette quantité est assez grande. Ainsi, lorsque nous examinons les solveurs plus tard, nous devons garder à l’esprit qu’il est primordial d’avoir des solveurs qui peuvent appréhender nativement les problèmes stochastiques au lieu d’adopter l’approche déterministe.
Un autre angle, qui est également d’un intérêt primordial, est l’optimisation multi-objectif. Dans l’expression naïve du problème d’optimisation mathématique, j’ai dit que la fonction de perte était essentiellement à valeur unique, donc nous avions une valeur que nous voulions minimiser. Mais que se passe-t-il si nous avons un vecteur de valeurs, et ce que nous voulons faire est de trouver la solution qui donne le point le plus bas selon l’ordre lexicographique de tous les vecteurs, comme f1, f2, f3, etc.?
Pourquoi cela intéresse-t-il même d’un point de vue de la supply chain ? La réalité est que si vous adoptez cette perspective multi-objectif, vous pouvez exprimer toutes vos contraintes comme une seule fonction de perte dédiée. Vous pouvez d’abord avoir une fonction qui compte les violations de vos contraintes. Pourquoi avez-vous des contraintes dans la supply chain ? Eh bien, vous avez des contraintes partout. Par exemple, si vous passez une commande d’achat, vous devez vous assurer d’avoir suffisamment d’espace dans votre entrepôt pour stocker les marchandises à leur arrivée. Donc, vous avez des contraintes sur l’espace de stockage, la capacité de production, et plus encore. L’idée est qu’au lieu d’avoir un solveur où vous devez spécifier les contraintes de manière spéciale, il est plus intéressant d’avoir un solveur qui peut traiter l’optimisation multi-objectif et où vous pouvez exprimer les contraintes comme l’un des objectifs. Vous comptez simplement le nombre de violations de contraintes et vous voulez minimiser cela, en ramenant ce nombre de violations à zéro.
La raison pour laquelle cette mentalité est très pertinente pour la supply chain est que les problèmes d’optimisation auxquels les supply chains sont confrontées ne sont pas des énigmes cryptographiques. Ce ne sont pas des problèmes combinatoires très serrés où soit vous avez une solution et c’est bon, soit vous êtes juste à un bit de la solution et vous n’avez rien. Dans la supply chain, obtenir ce qui est généralement appelé une solution réalisable - une solution qui satisfait toutes les contraintes - est généralement complètement trivial. Identifier une solution qui satisfait les contraintes n’est pas une tâche difficile. Ce qui est très difficile, c’est, parmi toutes les solutions qui satisfont les contraintes, identifier celle qui est la plus rentable pour l’entreprise. C’est là que cela devient très difficile. Trouver une solution qui ne viole pas les contraintes est très simple. Ce n’est pas le cas dans d’autres domaines, par exemple, dans l’optimisation mathématique pour la conception industrielle, où vous voulez placer des composants à l’intérieur d’un téléphone portable. Il s’agit d’un problème incroyablement contraint et combinatoire, et où vous devez vraiment traiter les contraintes comme des citoyens de première classe. Ce n’est pas nécessaire, je crois, pour la grande majorité des problèmes de supply chain. Il est donc à nouveau très intéressant d’avoir des techniques qui peuvent traiter nativement l’optimisation multi-objectif.
Maintenant, parlons un peu plus en détail de la conception du solveur. D’un point de vue très général sur la manière dont nous voulons concevoir un logiciel qui produira des solutions pour une classe très large de problèmes, il y a deux aspects de conception très remarquables que j’aimerais mettre en avant. Le premier aspect à considérer est de savoir si nous allons opérer selon une perspective de boîte blanche ou de boîte noire. L’idée d’une perspective de boîte noire est que nous pouvons traiter n’importe quel programme arbitraire, donc la fonction de perte peut être n’importe quel programme arbitraire. Nous nous en fichons ; nous traitons cela comme une boîte noire complète. La seule chose que nous voulons, c’est un programme où nous pouvons évaluer le programme et obtenir la valeur d’une solution provisoire. Au contraire, une approche de boîte blanche met l’accent sur le fait que la fonction de perte elle-même a une structure que nous pouvons inspecter et exploiter. Nous pouvons voir à l’intérieur de la fonction de perte. En passant, lorsque je discutais de la convexité quelques diapositives auparavant, tous ces modèles et solveurs mathématiques purs étaient vraiment des approches de boîte blanche. Ce sont des cas extrêmes d’approches de boîte blanche, où non seulement vous pouvez voir à l’intérieur du problème, mais le problème a une structure très rigide, comme la programmation semi-définie, où la forme est très étroite. Cependant, sans opter pour quelque chose d’aussi rigide qu’un cadre mathématique, vous pouvez, par exemple, dire que dans le cadre de la boîte blanche, vous disposez de quelque chose comme le gradient qui vous aidera. Un gradient de la fonction de perte est d’un intérêt crucial car soudainement vous pouvez savoir dans quelle direction vous voulez aller pour descendre, même si vous n’avez pas un problème convexe où la simple descente de gradient garantit un bon résultat. En règle générale, si vous pouvez concevoir votre solveur en boîte blanche, vous aurez un solveur qui est des ordres de grandeur plus performant par rapport à un solveur en boîte noire.
Maintenant, en tant que deuxième aspect, nous avons les solveurs hors ligne par rapport aux solveurs en ligne. Le solveur hors ligne fonctionne généralement en mode batch, donc un solveur hors ligne va simplement prendre le problème, l’exécuter et vous devrez attendre jusqu’à ce qu’il soit terminé. À ce moment-là, lorsque le solveur est terminé, il vous donne la meilleure solution ou quelque chose qui est la meilleure solution identifiée. Au contraire, un solveur en ligne fonctionne beaucoup plus avec une approche de meilleur effort. Il va identifier une solution qui est acceptable, puis investir des ressources informatiques pour itérer vers des solutions de plus en plus meilleures au fur et à mesure que le temps passe et que vous investissez plus de ressources informatiques. Ce qui est vraiment d’un intérêt crucial, c’est que lorsque vous abordez un problème avec un solveur en ligne, cela signifie que vous pouvez pratiquement mettre en pause le processus à n’importe quel moment et obtenir une solution candidate précoce. Vous pouvez même reprendre le processus. Si nous revenons aux solveurs mathématiques, ils sont généralement des solveurs en mode batch où vous devez attendre jusqu’à la fin du processus.
Malheureusement, travailler dans le monde de la supply chain peut être une expérience très mouvementée, comme cela a été abordé dans l’une des conférences précédentes de cette série. Il y aura des situations où vous pouvez généralement vous permettre de passer, disons, trois heures pour exécuter ce processus d’optimisation mathématique. Mais parfois, vous pouvez rencontrer des problèmes informatiques, des problèmes du monde réel ou une urgence dans votre supply chain. Dans de tels cas, ce sera une bouée de sauvetage si ce qui prenait habituellement trois heures peut être interrompu après cinq minutes et fournir une réponse, même mauvaise, plutôt que pas de réponse du tout. Il y a un dicton dans l’armée selon lequel le pire plan est l’absence de plan, il vaut donc mieux avoir un plan très approximatif que rien du tout. C’est exactement ce qu’un solveur en ligne vous offre. Ce sont les éléments de conception clés que nous garderons à l’esprit dans la discussion suivante.
Maintenant, pour conclure cette première partie de la conférence sur l’approche de l’optimisation mathématique, jetons un coup d’œil aux leçons sur l’apprentissage profond. L’apprentissage profond a été une révolution complète pour le domaine de l’apprentissage automatique. Cependant, au cœur de l’apprentissage profond, il y a aussi un problème d’optimisation mathématique. Je crois que l’apprentissage profond a généré une révolution au sein même de l’optimisation mathématique et a complètement changé notre façon de voir les problèmes d’optimisation. L’apprentissage profond a redéfini ce que nous considérons comme l’état de l’art de l’optimisation mathématique.
De nos jours, les plus grands modèles d’apprentissage profond traitent plus d’un billion de paramètres, ce qui équivaut à mille milliards. Juste pour mettre les choses en perspective, la plupart des solveurs mathématiques ont du mal à gérer ne serait-ce que 1 000 variables et s’effondrent généralement avec seulement quelques dizaines de milliers de variables, peu importe la puissance de calcul que vous leur fournissez. En revanche, l’apprentissage profond réussit, en utilisant sans doute une grande quantité de ressources informatiques, mais néanmoins, c’est faisable. Il existe des modèles d’apprentissage profond en production qui ont plus d’un billion de paramètres, et tous ces paramètres sont optimisés, ce qui signifie que nous disposons de processus d’optimisation mathématique qui peuvent s’adapter à un billion de paramètres. C’est absolument stupéfiant et radicalement différent des performances que nous avons observées avec les perspectives d’optimisation classiques.
Ce qui est intéressant, c’est que même les problèmes qui sont complètement déterministes, comme jouer au Go ou aux échecs, qui sont non statistiques, discrets et combinatoires, ont été résolus avec le plus de succès grâce à des méthodes qui sont complètement stochastiques et statistiques. Cela est déconcertant car jouer au Go ou aux échecs peut être considéré comme des problèmes d’optimisation discrets, mais ils sont résolus de manière plus efficace de nos jours avec des méthodes qui sont complètement stochastiques et statistiques. Cela va à l’encontre de l’intuition que la communauté scientifique avait de ces problèmes il y a deux décennies.
Revenons sur la compréhension qui a été débloquée par l’apprentissage profond concernant l’optimisation mathématique. La première chose est de revoir complètement la malédiction de la dimensionnalité. Je crois que ce concept est en grande partie erroné, et l’apprentissage profond prouve que ce concept n’est pas la façon dont vous devriez même penser à la difficulté d’un problème d’optimisation. Il s’avère que lorsque vous regardez des classes de problèmes mathématiques, vous pouvez prouver mathématiquement que certains problèmes sont extrêmement difficiles à résoudre parfaitement. Par exemple, si vous avez déjà entendu parler de problèmes NP-difficiles, vous savez que plus vous ajoutez de dimensions au problème, plus il devient exponentiellement plus difficile à résoudre. Chaque dimension supplémentaire rend le problème plus difficile, et il y a une barrière cumulative. Vous pouvez prouver qu’aucun algorithme ne pourra jamais espérer résoudre le problème parfaitement avec une quantité limitée de ressources informatiques. Cependant, l’apprentissage profond a montré que cette perspective était en grande partie erronée.
Tout d’abord, nous devons différencier la complexité de représentation du problème et la complexité intrinsèque du problème. Permettez-moi de clarifier ces deux termes avec un exemple. Prenons l’exemple de la prévision des séries temporelles donné initialement. Disons que nous avons un historique des ventes, agrégé quotidiennement sur trois ans, nous avons donc un vecteur temporel agrégé quotidiennement d’environ 1 000 jours. C’est la représentation du problème.
Maintenant, que se passe-t-il si je passe à une représentation des séries temporelles par seconde ? Il s’agit du même historique des ventes, mais au lieu de représenter mes données de ventes en agrégats quotidiens, je vais représenter cette série temporelle, exactement la même série temporelle, en agrégats par seconde. Cela signifie qu’il y a 86 400 secondes dans chaque jour, donc je vais gonfler la taille et la dimension de ma représentation du problème de 86 000.
Mais si nous commençons à réfléchir à la dimension intrinsèque, ce n’est pas parce que j’ai un historique des ventes, et ce n’est pas parce que je passe d’un agrégat par jour à un agrégat par seconde, que j’augmente la complexité ou la complexité dimensionnelle du problème de 1 000. Il est fort probable que si je passe à des ventes agrégées par seconde, la série temporelle sera incroyablement clairsemée, donc elle sera principalement composée de zéros pour pratiquement tous les compartiments. Je n’augmente pas la dimensionnalité intéressante du problème d’un facteur de 100 000. Le deep learning clarifie que ce n’est pas parce que vous avez une représentation du problème avec de nombreuses dimensions que le problème est fondamentalement difficile.
Un autre aspect associé à la dimensionnalité est que même si vous pouvez prouver que certains problèmes sont NP-complets, par exemple, le problème du voyageur de commerce (une version simplifiée du problème de routage des véhicules présenté au début de cette conférence), le voyageur de commerce est techniquement ce qu’on appelle un problème NP-difficile. Donc, c’est un problème où si vous voulez trouver la meilleure solution dans le cas général, cela va être exponentiellement coûteux à mesure que vous ajoutez des points à votre carte. Mais la réalité est que ces problèmes sont très faciles à résoudre, comme le montre l’heuristique du two-opt ; vous pouvez obtenir d’excellentes solutions avec une quantité minimale de ressources informatiques. Donc, méfiez-vous des preuves mathématiques, démontrant que certains problèmes sont très difficiles, elles peuvent être trompeuses. Elles ne vous disent pas que si vous acceptez d’avoir une solution approximative, l’approximation peut être excellente, et parfois ce n’est même pas une approximation ; vous allez obtenir la solution optimale. C’est juste que vous ne pouvez pas prouver qu’elle est optimale. Cela ne dit rien sur la possibilité d’approximer le problème, et très fréquemment, ces problèmes soi-disant affectés par la malédiction de la dimensionnalité sont faciles à résoudre car leurs dimensions intéressantes ne sont pas si élevées. Le deep learning a démontré avec succès que de nombreux problèmes considérés comme incroyablement difficiles ne l’étaient pas tant que ça en premier lieu.
La deuxième idée clé était les minima locaux. La majorité des chercheurs travaillant sur l’optimisation mathématique et la recherche opérationnelle se sont tournés vers les fonctions convexes car il n’y avait pas de minima locaux. Pendant longtemps, les personnes qui ne travaillaient pas sur les fonctions convexes réfléchissaient à la façon d’éviter de rester coincées dans un minimum local. La plupart des efforts étaient consacrés à des choses comme les méta-heuristiques. Le deep learning a apporté une compréhension renouvelée : nous ne nous soucions pas des minima locaux. Cette compréhension provient de travaux récents issus de la communauté du deep learning.
Si vous avez une très grande dimension, vous pouvez montrer que les minima locaux disparaissent à mesure que la dimension du problème augmente. Les minima locaux sont très fréquents dans les problèmes de faible dimension, mais si vous augmentez la dimension des problèmes à des centaines ou des milliers, statistiquement parlant, les minima locaux deviennent incroyablement improbables. Au point où, en regardant des dimensions très grandes comme des millions, ils disparaissent complètement.
Au lieu de penser qu’une dimension plus élevée est votre ennemi, comme cela était associé à la malédiction de la dimensionnalité, que se passerait-il si vous pouviez faire exactement le contraire et gonfler la dimension du problème jusqu’à ce qu’elle devienne si grande qu’il soit trivial d’avoir une descente propre sans aucun minimum local ? Il s’avère que c’est exactement ce qui est fait dans la communauté du deep learning et avec des modèles qui ont un trillion de paramètres. Cette approche vous donne un moyen très clair de progresser par gradient.
Essentiellement, la communauté du deep learning a montré qu’il était sans importance d’avoir une preuve de la qualité de la descente ou de la convergence ultime. Ce qui importe, c’est la vitesse de descente. Vous voulez itérer et descendre très rapidement vers une très bonne solution. Si vous pouvez avoir un processus qui descend plus rapidement, vous irez finalement plus loin en termes d’optimisation. Ces idées vont à l’encontre de la compréhension générale de l’optimisation mathématique, ou de ce qui était la compréhension dominante il y a deux décennies.
Il y a d’autres leçons à tirer du deep learning, car c’est un domaine très riche. L’une d’entre elles est la sympathie matérielle. Le problème avec les solveurs mathématiques, tels que la programmation conique ou la programmation géométrique, est qu’ils se concentrent d’abord sur l’intuition mathématique et non sur le matériel informatique. Si vous concevez un solveur qui antagonise fondamentalement votre matériel informatique, peu importe à quel point vos mathématiques sont intelligentes, il y a de fortes chances que vous soyez désespérément inefficace en raison d’une mauvaise utilisation du matériel informatique.
L’une des principales idées de la communauté du deep learning est qu’il faut bien s’entendre avec le matériel informatique et concevoir un solveur qui l’embrasse. C’est pourquoi j’ai commencé cette série de conférences sur les sciences auxiliaires pour la supply chain avec les ordinateurs modernes pour la supply chain. Il est important de comprendre le matériel que vous avez et comment en tirer le meilleur parti. Cette sympathie matérielle est ce qui vous permet d’obtenir des modèles avec un trillion de paramètres, à condition d’avoir un grand cluster d’ordinateurs ou un superordinateur.
Une autre leçon du deep learning est l’utilisation de fonctions de substitution. Traditionnellement, les solveurs mathématiques visaient à optimiser le problème tel qu’il était, sans s’en écarter. Cependant, le deep learning a montré qu’il était parfois préférable d’utiliser des fonctions de substitution. Par exemple, très fréquemment pour les prédictions, les modèles de deep learning utilisent l’entropie croisée comme métrique d’erreur au lieu de la moyenne quadratique. Pratiquement personne dans le monde réel ne s’intéresse à l’entropie croisée en tant que métrique, car elle est assez bizarre.
Alors pourquoi les gens utilisent-ils l’entropie croisée ? Elle fournit des gradients incroyablement raides et, comme l’a montré le deep learning, tout est une question de vitesse de descente. Si vous avez des gradients très raides, vous pouvez descendre très rapidement. Les gens pourraient objecter et dire : “Si je veux optimiser la moyenne quadratique, pourquoi devrais-je utiliser l’entropie croisée ? Ce n’est même pas la même cible.” La réalité est que si vous optimisez l’entropie croisée, vous aurez des gradients très raides et, à la fin, si vous évaluez votre solution par rapport à la moyenne quadratique, vous obtiendrez également une meilleure solution selon le critère de la moyenne quadratique, très fréquemment, sinon toujours. Je simplifie juste pour les besoins de cette explication. L’idée des fonctions de substitution est que le vrai problème n’est pas absolu ; c’est juste quelque chose que vous utiliserez pour contrôler la validité finale de votre solution. Ce n’est pas nécessairement quelque chose que vous utiliserez pendant que le solveur est en cours. Cela va complètement à l’encontre des idées impliquées dans les solveurs mathématiques qui étaient populaires au cours des deux dernières décennies.
Enfin, il y a l’importance de travailler selon des paradigmes. Avec l’optimisation mathématique, il y a implicitement une division du travail impliquée dans l’organisation de votre équipe d’ingénieurs. La division du travail implicite liée aux solveurs mathématiques est que vous aurez d’un côté des ingénieurs mathématiques, responsables de l’ingénierie du solveur, et de l’autre côté des ingénieurs de problèmes, dont la responsabilité est d’exprimer le problème sous une forme adaptée au traitement par les solveurs mathématiques. Cette division du travail était prédominante et l’idée était de la rendre aussi simple que possible pour l’ingénieur de problèmes, de sorte qu’il n’ait qu’à exprimer le problème de la manière la plus minimaliste et la plus pure possible, laissant le solveur faire le travail.
Le deep learning a montré que cette perspective était profondément inefficace. Cette division arbitraire du travail n’était pas du tout la meilleure façon d’aborder le problème. Si vous faites cela, vous vous retrouvez avec des situations impossibles, c’est-à-dire largement supérieures à l’état de l’art pour les ingénieurs mathématiques travaillant sur le problème d’optimisation. Une bien meilleure façon est de demander aux ingénieurs de problèmes de faire un effort supplémentaire pour reformuler les problèmes de manière à les rendre beaucoup plus adaptés à l’optimisation par l’optimiseur mathématique.
Le deep learning consiste en un ensemble de recettes qui vous permettent de formuler le problème au-dessus de votre solveur, afin d’obtenir le meilleur rendement de votre optimiseur. La plupart des développements dans la communauté du deep learning se sont concentrés sur l’élaboration de ces recettes qui sont très efficaces pour apprendre tout en s’adaptant parfaitement au paradigme des solveurs qu’ils utilisent (par exemple, TensorFlow, PyTorch, MXNet). La conclusion est que vous voulez vraiment collaborer avec l’ingénieur de problèmes, ou dans le langage de la supply chain, le Supply Chain Scientist.
Passons maintenant à la deuxième et dernière partie de cette conférence sur les éléments les plus précieux de la littérature. Nous examinerons deux grandes classes de solveurs : la recherche locale et la programmation différentiable.
Tout d’abord, permettez-moi de m’arrêter à nouveau sur le terme “programmation”. Ce mot revêt une importance capitale car, d’un point de vue de la supply chain, nous voulons vraiment être en mesure d’exprimer le problème que nous rencontrons, ou le problème que nous pensons rencontrer. Nous ne voulons pas d’une sorte de version super basse résolution du problème qui correspond simplement à une hypothèse mathématique semi-absurde, comme avoir besoin d’exprimer votre problème dans un cône ou quelque chose du genre. Ce qui nous intéresse vraiment, c’est d’avoir accès à un véritable paradigme de programmation.
Rappelez-vous, ces solveurs mathématiques tels que la programmation linéaire, la programmation conique de second ordre et la programmation géométrique sont tous venus avec un mot-clé de programmation. Cependant, au cours des dernières décennies, ce que nous attendons d’un paradigme de programmation a évolué de manière spectaculaire. De nos jours, nous voulons quelque chose qui vous permette de traiter presque n’importe quel programme, des programmes dans lesquels vous avez des boucles, des branches et éventuellement des allocations de mémoire, etc. Vous voulez vraiment quelque chose qui soit aussi proche que possible d’un programme arbitraire, pas une sorte de version jouet super limitée qui a certaines propriétés mathématiques intéressantes. En supply chain, il vaut mieux être approximativement correct que totalement faux.
Pour traiter l’optimisation générique, commençons par la recherche locale. La recherche locale est une technique d’optimisation mathématique trompeusement simple. Le pseudocode consiste à commencer par une solution aléatoire, que vous représentez sous la forme d’un ensemble de bits. Vous initialisez ensuite votre solution de manière aléatoire et commencez à inverser aléatoirement les bits pour explorer le voisinage de la solution. Si, grâce à cette exploration aléatoire, vous trouvez une solution qui s’avère meilleure, cela devient votre nouvelle solution de référence.
Cette approche étonnamment puissante peut fonctionner avec littéralement n’importe quel programme, en le traitant comme une boîte noire, et peut également redémarrer à partir de n’importe quelle solution connue. Il existe de nombreuses façons d’améliorer cette approche. Une façon est le calcul différentiel, à ne pas confondre avec le calcul différentiable. Le calcul différentiel est l’idée que si vous exécutez votre programme sur une solution donnée, puis inversez un bit, vous pouvez réexécuter le même programme avec une exécution différentielle, sans avoir à réexécuter l’ensemble du programme. Évidemment, les résultats peuvent varier, et cela dépend beaucoup de la structure du problème. Une façon d’accélérer le processus est de ne pas exploiter une sorte d’information supplémentaire sur le programme boîte noire que nous utilisons, mais simplement d’être capable d’accélérer le programme lui-même, en le traitant toujours principalement comme une boîte noire, car vous ne réexécutez pas l’ensemble du programme à chaque fois.
Il existe d’autres approches pour améliorer la recherche locale. Vous pouvez améliorer le type de mouvements que vous effectuez. La stratégie la plus basique s’appelle les k-inversions, où vous inversez un nombre k de bits avec k étant un nombre très petit, quelque chose comme une paire à une douzaine. Au lieu de simplement inverser les bits, vous pouvez laisser l’ingénieur du problème définir le type de mutations à appliquer à la solution. Par exemple, vous pouvez exprimer que vous souhaitez appliquer une sorte de permutation dans votre problème. L’idée est que ces mouvements intelligents préservent souvent la satisfaction de certaines contraintes de votre problème, ce qui peut aider le processus de recherche locale à converger plus rapidement.
Une autre façon d’améliorer la recherche locale est de ne pas explorer complètement l’espace de manière aléatoire. Au lieu d’inverser les bits de manière aléatoire, vous pouvez essayer d’apprendre les bonnes directions, en identifiant les zones les plus prometteuses pour les inversions. Certains articles récents ont montré que vous pouvez brancher un petit module d’apprentissage en profondeur sur la recherche locale, agissant comme un générateur. Cependant, cette approche peut être délicate en termes d’ingénierie, car vous devez vous assurer que les ressources de calcul supplémentaires introduites par le processus d’apprentissage automatique donnent un retour positif en termes de ressources de calcul.
Il existe d’autres heuristiques bien connues, et si vous souhaitez avoir une très bonne vue synthétique de ce qu’il faut pour mettre en œuvre un moteur de recherche locale moderne, vous pouvez lire l’article “LocalSolver: A Black-Box Local-Search Solver for 0-1 Programs”. La société qui exploite LocalSolver a également un produit du même nom. Dans cet article, ils donnent un aperçu technique de ce qui se passe sous le capot de leur solveur de qualité industrielle. Ils utilisent le multi-démarrage et le recuit simulé pour de meilleurs résultats.
Un inconvénient que j’ajouterais à la recherche locale est qu’elle ne traite pas très bien ou nativement les problèmes stochastiques. Avec les problèmes stochastiques, ce n’est pas aussi simple que de dire simplement “j’ai une meilleure solution” et de décider immédiatement que cela devient la meilleure solution. C’est plus compliqué que cela, et vous devez fournir des efforts supplémentaires avant de passer à la solution évaluée comme la nouvelle meilleure.
Maintenant, passons à la deuxième classe de solveurs que nous allons discuter aujourd’hui, qui est la programmation différentiable. Mais d’abord, pour comprendre la programmation différentiable, nous devons comprendre la descente de gradient stochastique. La descente de gradient stochastique est une technique d’optimisation itérative basée sur le gradient. Elle est apparue comme une série de techniques pionnières au début des années 1950, ce qui la rend presque vieille de 70 ans. Elle est restée assez confidentielle pendant près de six décennies, et nous avons dû attendre l’avènement de l’apprentissage en profondeur pour réaliser le véritable potentiel et la puissance de la descente de gradient stochastique.
La descente de gradient stochastique suppose que la fonction de perte peut être décomposée de manière additive en une série de composantes. Dans l’équation, Q(W) représente la fonction de perte, qui est décomposée en une série de fonctions partielles, Qi. Cela est pertinent car la plupart des problèmes d’apprentissage peuvent être considérés comme devant apprendre une prédiction basée sur une série d’exemples. L’idée est que vous pouvez décomposer votre fonction de perte en tant qu’erreur moyenne commise sur l’ensemble des données, avec une erreur locale pour chaque point de données. De nombreux problèmes de supply chain peuvent également être décomposés de manière additive de cette manière. Par exemple, vous pouvez décomposer votre réseau de supply chain en une série de performances pour chaque SKU individuel, avec une fonction de perte attachée à chaque SKU. La véritable fonction de perte que vous souhaitez optimiser est la somme totale.
Lorsque vous avez cette décomposition en place, qui est très naturelle pour les problèmes d’apprentissage, vous pouvez itérer avec le processus de descente de gradient stochastique (SGD). Le vecteur de paramètres W peut être une très grande série, car les plus grands modèles d’apprentissage en profondeur ont un trillion de paramètres. L’idée est qu’à chaque étape du processus, vous mettez à jour vos paramètres en appliquant une petite quantité de gradient. Eta est le taux d’apprentissage, un petit nombre généralement compris entre 0 et 1, souvent autour de 0,01. Nabla de Q est le gradient pour une fonction de perte partielle Qi. Étonnamment, ce processus fonctionne bien.
On dit que SGD est stochastique car vous choisissez aléatoirement votre prochain élément i, en sautant à travers votre ensemble de données et en appliquant un tout petit peu de gradient à vos paramètres à chaque étape. C’est l’essence de la descente de gradient stochastique.
Elle est restée relativement confidentielle et largement ignorée par la communauté pendant près de six décennies, car il est assez surprenant que la descente de gradient stochastique fonctionne du tout. Elle fonctionne car elle offre un excellent compromis entre le bruit dans la fonction de perte et le coût computationnel d’accéder à la fonction de perte elle-même. Au lieu d’avoir une fonction de perte qui doit être évaluée sur l’ensemble des données, avec la descente de gradient stochastique, nous pouvons prendre un point de données à la fois et appliquer quand même un peu de gradient. Cette mesure va être très fragmentaire et bruitée, mais ce bruit est en réalité acceptable car il est très rapide. Vous pouvez effectuer des optimisations minuscules et bruitées de plusieurs ordres de grandeur par rapport au traitement de l’ensemble des données.
Étonnamment, le bruit introduit aide à la descente du gradient. L’un des problèmes dans les espaces de grande dimension est que les minima locaux deviennent relativement inexistants. Cependant, vous pouvez encore rencontrer de vastes plateaux où le gradient est très faible, et la descente du gradient n’a pas de direction à choisir pour la descente. Le bruit vous donne des gradients plus raides et plus bruités qui aident à la descente.
Ce qui est également intéressant avec la descente de gradient, c’est qu’il s’agit d’un processus stochastique, mais il peut traiter gratuitement des problèmes stochastiques. Si Qi est une fonction stochastique avec du bruit et donne un résultat aléatoire qui varie à chaque évaluation, vous n’avez même pas besoin de changer une seule ligne de l’algorithme. La descente de gradient stochastique est d’un intérêt primordial car elle vous donne quelque chose qui est complètement aligné avec le paradigme qui est pertinent pour les besoins de la supply chain.
La deuxième question est : d’où vient le gradient ? Nous avons un programme, et nous prenons simplement le gradient de la fonction de perte partielle, mais d’où vient ce gradient ? Comment obtenez-vous un gradient pour un programme arbitraire ? Il s’avère qu’il existe une technique très élégante et minimaliste découverte il y a longtemps, appelée différentiation automatique.
La différentiation automatique est apparue dans les années 1960 et a été affinée au fil du temps. Il existe deux types : le mode avant, découvert en 1964, et le mode arrière, découvert en 1980. La différentiation automatique peut être considérée comme une astuce de compilation. L’idée est que vous avez un programme à compiler, et avec la différentiation automatique, vous avez votre programme qui représente la fonction de perte. Vous pouvez recompiler ce programme pour obtenir un deuxième programme, et la sortie du deuxième programme n’est pas la fonction de perte mais les gradients de tous les paramètres impliqués dans le calcul de la fonction de perte.
De plus, la différentiation automatique vous donne un deuxième programme dont la complexité de calcul est essentiellement identique à celle de votre programme initial. Cela signifie que non seulement vous avez un moyen de créer un deuxième programme qui calcule les gradients, mais aussi que le deuxième programme a les mêmes caractéristiques de calcul en termes de performances que le premier programme. Il s’agit d’un facteur constant d’inflation en termes de coût de calcul. La réalité, cependant, est que le deuxième programme obtenu n’a pas exactement les mêmes caractéristiques de mémoire que le programme initial. Bien que les détails techniques dépassent le cadre de cette présentation, nous pouvons en discuter lors des questions. Essentiellement, le deuxième programme, appelé le programme inverse, va nécessiter plus de mémoire, et dans certaines situations pathologiques, il peut nécessiter beaucoup plus de mémoire que le programme initial. N’oubliez pas que plus de mémoire crée des problèmes de performances de calcul, car vous ne pouvez pas supposer un accès uniforme à la mémoire.
Pour illustrer un peu à quoi ressemble la différentiation automatique, comme je l’ai mentionné, il existe deux modes : avant et arrière. Du point de vue de l’apprentissage ou de l’optimisation de la supply chain, le seul mode qui nous intéresse est le mode arrière. Ce que vous pouvez voir à l’écran, c’est une fonction de perte F, complètement inventée. Vous pouvez voir la trace avant, une séquence d’opérations arithmétiques ou élémentaires qui ont lieu pour calculer votre fonction pour deux valeurs d’entrée données, X1 et X2. Cela vous donne toutes les étapes élémentaires effectuées pour calculer la valeur finale.
L’idée est que pour chaque étape élémentaire, et la plupart d’entre elles sont simplement des opérations arithmétiques de base comme la multiplication ou l’addition, le mode arrière est un programme qui exécute les mêmes étapes mais dans l’ordre inverse. Au lieu d’avoir les valeurs avant, vous aurez les adjoints. Pour chaque opération arithmétique, vous aurez leur contrepartie inverse. La transition de l’opération avant à la contrepartie inverse est très simple.
Même si cela semble compliqué, vous avez une exécution avant et une exécution arrière, où votre exécution arrière n’est rien d’autre qu’une transformation élémentaire appliquée à chaque opération. À la fin de l’exécution arrière, vous obtenez les gradients. La différentiation automatique peut sembler compliquée, mais ce n’est pas le cas. Le premier prototype que nous avons mis en place faisait moins de 100 lignes de code, donc c’est très simple et essentiellement une astuce de transpilation bon marché.
Maintenant, c’est intéressant car nous avons la descente de gradient stochastique, qui est un mécanisme d’optimisation incroyablement puissant. Il est incroyablement évolutif, en ligne, sur tableau blanc et fonctionne nativement avec des problèmes stochastiques. Le seul problème qui restait était de savoir comment obtenir le gradient, et avec la différentiation automatique, nous avons le gradient pour un surcoût fixe ou un facteur constant, pour à peu près n’importe quel programme arbitraire. Ce que nous obtenons à la fin, c’est la programmation différentiable.
Fait intéressant, la programmation différentiable est une combinaison de la descente de gradient stochastique et de la différentiation automatique. Bien que ces deux techniques, la descente de gradient stochastique et la différentiation automatique, aient des décennies, la programmation différentiable n’a connu une notoriété qu’au début de 2018 lorsque Yann LeCun, le responsable de l’IA chez Facebook, a commencé à communiquer sur ce concept. LeCun n’a pas inventé ce concept, mais il a contribué à le rendre populaire.
Par exemple, la communauté de l’apprentissage profond utilisait initialement la rétropropagation plutôt que la différentiation automatique. Pour ceux qui sont familiers avec les réseaux neuronaux, la rétropropagation est un processus complexe qui est des ordres de grandeur plus compliqué à mettre en œuvre que la différentiation automatique. La différentiation automatique est supérieure à tous égards. Avec cette compréhension, la communauté de l’apprentissage profond a affiné sa vision de ce qui constitue l’apprentissage dans l’apprentissage profond. L’apprentissage profond combine l’optimisation mathématique avec diverses techniques d’apprentissage, et la programmation différentiable est apparue comme un concept clair qui isole les parties non-apprentissage de l’apprentissage profond.
Les techniques modernes d’apprentissage profond, telles que le modèle transformer, supposent un environnement de programmation différentiable en dessous. Cela permet aux chercheurs de se concentrer sur les aspects d’apprentissage qui sont construits par-dessus. La programmation différentiable, bien que fondamentale pour l’apprentissage profond, est également très pertinente pour l’optimisation de la chaîne d’approvisionnement et pour soutenir les processus d’apprentissage de la chaîne d’approvisionnement, tels que la prévision statistique.
Tout comme avec l’apprentissage profond, il y a deux parties au problème : la programmation différentiable comme couche de base et les techniques d’optimisation ou d’apprentissage par-dessus. La communauté de l’apprentissage profond vise à identifier les architectures qui fonctionnent bien avec la programmation différentiable, telles que les transformers. De même, il faut identifier les architectures qui fonctionnent bien à des fins d’optimisation. C’est ce qui a été fait pour apprendre à jouer au Go ou aux échecs dans des environnements hautement combinatoires. Nous discuterons des techniques qui fonctionnent bien pour l’optimisation spécifique à la chaîne d’approvisionnement dans les prochaines conférences.
Mais maintenant, il est temps de conclure. Une part importante de la littérature sur la chaîne d’approvisionnement et même la plupart de ses implémentations logicielles sont assez confuses en ce qui concerne l’optimisation mathématique. Cet aspect n’est généralement même pas correctement identifié en tant que tel, et par conséquent, les praticiens, les chercheurs et même les ingénieurs logiciels travaillant pour des entreprises de logiciels de gestion souvent se mélangent dans leurs recettes numériques de manière assez désordonnée en ce qui concerne l’optimisation mathématique. Ils ont un gros problème, car une composante n’a pas été identifiée comme étant de nature d’optimisation mathématique, et parce que les gens ne sont même pas conscients de ce qui est disponible dans la littérature, ils ont souvent recours à des recherches en grille grossières ou à des heuristiques hâtives qui donnent des performances erratiques et incohérentes. En conclusion de cette conférence, à partir de maintenant, chaque fois que vous rencontrez une méthode numérique de chaîne d’approvisionnement ou un logiciel de chaîne d’approvisionnement qui prétend offrir une fonctionnalité analytique quelconque, vous devez vous demander ce qui se passe en termes d’optimisation mathématique et ce qui est fait. Si vous réalisez que les fournisseurs n’offrent pas une vue claire de cette perspective, il y a de fortes chances que vous soyez du côté gauche de l’illustration, et ce n’est pas l’endroit où vous voulez être.
Maintenant, jetons un coup d’œil aux questions.
Question : La transition vers les méthodes computationnelles est-elle une compétence préalable dans les opérations, et les rôles opérationnels deviendront-ils obsolètes, ou vice versa ?
Tout d’abord, permettez-moi de clarifier quelques points. Je pense que c’est une erreur de pousser ce genre de préoccupations vers le DSI. Les gens attendent beaucoup trop de leurs DSI. En tant que directeur des systèmes d’information, vous devez déjà gérer la couche de base de votre infrastructure logicielle, tels que les ressources informatiques, les systèmes transactionnels de bas niveau, l’intégrité du réseau et la cybersécurité. On ne devrait pas attendre du DSI qu’il comprenne ce qu’il faut faire réellement pour apporter une valeur ajoutée à votre chaîne d’approvisionnement.
Le problème est que dans de nombreuses entreprises, les gens sont tellement désespérément ignorants de tout ce qui concerne l’informatique que le DSI devient la personne à qui l’on s’adresse pour tout. La réalité est que le DSI devrait s’occuper de la couche de base de l’infrastructure, et ensuite, il revient à chaque spécialiste de répondre à ses besoins spécifiques avec les ressources informatiques et les outils logiciels à leur disposition.
En ce qui concerne les rôles opérationnels devenant obsolètes, si votre rôle consiste à passer toute la journée à parcourir manuellement des feuilles de calcul Excel, alors oui, votre rôle est très susceptible de devenir obsolète. C’est un problème connu depuis 1979, lorsque Russell Ackoff a publié son article. Le problème est que les gens savaient que cette méthode de prise de décision n’était pas l’avenir, mais elle est restée la norme pendant très longtemps. Le cœur du problème est que les entreprises doivent comprendre le processus expérimental. Je crois qu’il y aura une transition où les entreprises commenceront à réacquérir ces compétences. De nombreuses grandes entreprises nord-américaines, après la Seconde Guerre mondiale, avaient une certaine connaissance de la recherche opérationnelle parmi leurs cadres. C’était un sujet très en vogue, et les conseils d’administration des grandes entreprises connaissaient des choses sur la recherche opérationnelle. Comme le souligne Russell Ackoff, en raison du manque de résultats, ces idées ont été reléguées au bas de l’échelle de l’entreprise jusqu’à ce qu’elles soient même externalisées complètement, car elles étaient principalement sans pertinence et ne produisaient pas de résultats tangibles. Je crois que la recherche opérationnelle ne reviendra que si les gens tirent les leçons de la raison pour laquelle l’ère classique de la recherche opérationnelle n’a pas donné de résultats. Le DSI n’aura qu’une contribution modeste dans cette entreprise ; il s’agit principalement de repenser la valeur ajoutée des personnes au sein de l’entreprise.
Vous voulez apporter une contribution capitaliste, et cela renvoie à l’une de mes conférences précédentes sur la livraison orientée produit dans le sens de produits logiciels pour les chaînes d’approvisionnement. Le cœur du problème est le suivant : quelle sorte de valeur ajoutée capitaliste apportez-vous à votre entreprise ? Si la réponse est aucune, alors vous pourriez ne pas faire partie de ce que votre entreprise devrait devenir et deviendra à l’avenir.
Question : Que pensez-vous de l’utilisation du solveur Excel pour minimiser la valeur MRMSC et trouver la valeur optimale pour alpha, beta et gamma ?
Je pense que cette question est pertinente pour le cas de Holt-Winters, où vous pouvez réellement trouver une solution avec une recherche en grille. Cependant, que se passe-t-il dans ce solveur Excel ? S’agit-il d’une descente de gradient ou autre chose ? Si vous faites référence au solveur linéaire d’Excel, ce n’est pas un problème linéaire, donc Excel ne peut rien faire pour vous dans ce cas. Si vous avez d’autres solveurs dans Excel ou des modules complémentaires, oui, ils peuvent fonctionner, mais c’est une perspective très datée. Elle n’embrasse pas une vision plus stochastique ; le type de prévision que vous obtenez est une prévision non probabiliste, ce qui est une approche dépassée.
Je ne dis pas qu’Excel ne peut pas être utilisé, mais la question est de savoir quelles capacités de programmation sont débloquées dans Excel ? Pouvez-vous faire de la descente de gradient stochastique dans Excel ? Probablement, si vous ajoutez un module complémentaire dédié. Excel vous permet de brancher n’importe quel programme arbitraire dessus. Pourriez-vous potentiellement faire de la programmation différentiable dans Excel ? Oui. Est-ce une bonne idée de le faire dans Excel ? Non. Pour comprendre pourquoi, il faut revenir au concept de livraison de logiciels orientée produit, qui explique ce qui ne va pas avec Excel. Cela se résume au modèle de programmation et à la possibilité de maintenir réellement votre travail dans le temps avec un effort d’équipe.
Question : Les problèmes d’optimisation sont généralement orientés vers la planification des véhicules ou les prévisions. Pourquoi ne pas envisager d’optimiser l’ensemble de la supply chain également ? Cela ne réduirait-il pas les coûts par rapport à l’examen de zones isolées ?
Je suis tout à fait d’accord. Le problème de l’optimisation de la supply chain est que lorsque vous effectuez une optimisation locale sur un sous-problème, vous allez très probablement déplacer le problème, sans le résoudre pour l’ensemble de la supply chain. Je suis tout à fait d’accord, et dès que vous commencez à examiner un problème plus complexe, vous vous retrouvez avec un problème hybride - par exemple, un problème de routage de véhicules combiné à une stratégie de réapprovisionnement. Le problème est que vous avez besoin d’un solveur très générique pour aborder cela, car vous ne voulez pas être limité. Si vous avez un solveur très générique, vous devez avoir des mécanismes très génériques au lieu de vous fier à des heuristiques intelligentes comme le two-opt, qui fonctionne bien uniquement pour le routage des véhicules et non pour quelque chose qui est un hybride à la fois de réapprovisionnement et de routage de véhicules.
Pour passer à cette perspective holistique, il faut ne pas avoir peur de la malédiction de la dimensionnalité. Il y a vingt ans, les gens disaient que ces problèmes étaient déjà extrêmement difficiles et NP-complets, comme le problème du voyageur de commerce, et vous voulez résoudre un problème encore plus difficile en l’entrelaçant avec un autre problème. La réponse est oui ; vous voulez être capable de le faire, et c’est pourquoi il est essentiel d’avoir un solveur qui vous permet de traiter des programmes arbitraires car votre résolution peut être la consolidation de nombreux problèmes entrelacés et entrelacés.
En effet, l’idée de résoudre ces problèmes de manière isolée est beaucoup plus faible par rapport à la résolution de tout. Il vaut mieux être approximativement correct que complètement faux. Il est beaucoup mieux d’avoir un solveur très faible qui aborde l’ensemble de la supply chain comme un système, comme un bloc, plutôt que d’avoir des optimisations locales avancées qui ne font que créer des problèmes ailleurs lorsque vous micro-optimisez localement. L’optimisation réelle du système n’est pas nécessairement la meilleure optimisation pour chaque partie, il est donc naturel que si vous optimisez pour l’intérêt de l’ensemble de l’entreprise et de sa supply chain, cela ne sera pas localement optimal car vous tenez compte des autres aspects de l’entreprise et de sa supply chain.
Question : Après avoir effectué un exercice d’optimisation, quand devrions-nous revoir le scénario en tenant compte du fait que de nouvelles contraintes peuvent apparaître à tout moment ? La réponse est que vous devriez revoir l’optimisation fréquemment. C’est le rôle du Supply Chain Scientist que j’ai présenté lors de la deuxième conférence de cette série. Le Supply Chain Scientist revisitera l’optimisation aussi souvent que nécessaire. Si une nouvelle contrainte émerge, comme un navire gigantesque bloquant le canal de Suez, cela était inattendu, mais vous devez faire face à cette perturbation dans votre supply chain. Vous n’avez pas d’autre choix que de résoudre ces problèmes ; sinon, le système que vous avez mis en place générera des résultats non sensés car il fonctionnera dans de fausses conditions. Même si vous n’avez pas d’urgence à gérer, vous voulez quand même investir votre temps pour réfléchir à l’angle le plus susceptible de générer le plus grand retour pour l’entreprise. C’est fondamentalement de la recherche et développement. Vous avez le système en place, il fonctionne, et vous essayez simplement d’identifier les domaines où vous pouvez améliorer le système. Cela devient un processus de recherche appliquée qui est très capitaliste et erratique. En tant que Supply Chain Scientist, il y a des jours où vous passez toute votre journée à tester des méthodes numériques, aucune d’entre elles ne donnant de meilleurs résultats que ce que vous avez déjà. Certains jours, vous apportez une petite modification et vous avez beaucoup de chance, ce qui permet d’économiser des millions à l’entreprise. C’est un processus erratique, mais en moyenne, le résultat peut être énorme.
Question : Quels seraient les cas d’utilisation pour les problèmes d’optimisation autres que la programmation linéaire, la programmation entière, la programmation mixte et dans le cas de Weber et du coût des marchandises ?
Je renverserais la question : où voyez-vous que la programmation linéaire a une quelconque pertinence pour un problème de supply chain ? Il n’y a pratiquement aucun problème de supply chain qui soit linéaire. Mon objection est que ces cadres sont très simplistes et ne peuvent même pas aborder des problèmes basiques. Comme je l’ai dit, ces cadres mathématiques, comme la programmation linéaire, ne peuvent même pas aborder un problème basique comme l’optimisation en hiver pour un ancien modèle de prévision paramétrique de basse dimension. Ils ne peuvent même pas traiter le problème du voyageur de commerce ou à peu près n’importe quoi d’autre.
La programmation entière ou la programmation mixte-entière est simplement un terme générique pour indiquer que certaines des variables seront des entiers, mais cela ne change pas le fait que ces cadres de programmation ne sont que des cadres mathématiques basiques qui sont loin d’avoir l’expressivité nécessaire pour aborder les problèmes de supply chain.
Lorsque vous parlez des cas d’utilisation des problèmes d’optimisation, je vous invite à consulter toutes mes conférences sur les personas de la supply chain. Nous avons déjà une série de personas de la supply chain, et je liste littéralement des tonnes de problèmes qui peuvent être abordés grâce à l’optimisation mathématique. Dans les conférences sur les personas de la supply chain, nous avons Paris, Miami, Amsterdam et une série mondiale, avec d’autres à venir. Nous avons de nombreux problèmes qui doivent être abordés et mériteraient d’être abordés avec une perspective d’optimisation mathématique appropriée. Cependant, vous verrez que pour chacun de ces problèmes, vous ne pourrez pas les formuler dans les contraintes très strictes et souvent bizarres qui émergent de ces cadres mathématiques. Encore une fois, ces cadres mathématiques sont principalement axés sur la convexité, et ce n’est pas la bonne perspective pour la supply chain. La plupart des points que nous traitons ne sont pas convexes. Mais ce n’est pas grave ; ce n’est pas parce qu’ils ne sont pas convexes qu’ils sont impossibles à résoudre. Vous voyez, c’est juste que vous ne pourrez pas avoir une preuve mathématique à la fin de la journée. Mais votre patron ou votre entreprise se soucie du profit, pas de savoir si vous avez une preuve mathématique pour étayer la décision. Ils se soucient du fait que vous puissiez prendre la bonne décision en termes de production, de réapprovisionnement, de prix, d’assortiments, et autres, pas que vous ayez une preuve mathématique attachée à ces décisions.
Question : Combien de temps les données d’apprentissage de l’algorithme doivent-elles être stockées pour aider à l’apprentissage ?
Eh bien, je dirais, étant donné que le stockage des données est incroyablement bon marché de nos jours, pourquoi ne pas les conserver indéfiniment ? Le stockage des données est tellement bon marché ; par exemple, il suffit d’aller dans un supermarché et vous pouvez voir que le prix d’un disque dur d’un téraoctet est d’environ 60 euros ou quelque chose comme ça. Donc, c’est incroyablement bon marché.
Maintenant, évidemment, il y a une préoccupation distincte selon laquelle si vous avez des données personnelles dans vos données, alors les données que vous conservez deviennent une responsabilité. Mais d’un point de vue de la supply chain, si nous supposons que vous avez d’abord éliminé toutes les données personnelles, car vous n’avez généralement pas besoin d’avoir des données personnelles en premier lieu. Vous n’avez pas besoin de conserver les numéros de carte de crédit ou les noms de vos clients. Vous avez seulement besoin d’avoir des identifiants de clients, et ainsi de suite. Si vous éliminez simplement toutes les données personnelles de vos données, je dirais, combien de temps ? Eh bien, conservez-les indéfiniment.
L’un des points clés de la supply chain est que vous disposez de données limitées. Ce n’est pas comme les problèmes d’apprentissage profond tels que la reconnaissance d’images, où vous pouvez traiter toutes les images sur le web et avoir accès à des bases de données presque infinies pour les analyser. En supply chain, vos données sont toujours limitées. En effet, si vous souhaitez prévoir la demande future, il y a très peu d’industries où regarder plus de dix ans en arrière est vraiment pertinent, statistiquement parlant, pour prévoir la demande du prochain trimestre. Mais néanmoins, je dirais que c’est toujours plus facile de tronquer les données si vous en avez besoin plutôt que de réaliser que vous avez jeté des données et qu’elles manquent maintenant. Ma suggestion est donc de tout conserver, d’éliminer les données personnelles et, à la toute fin de votre pipeline de données, vous verrez s’il est préférable de filtrer les données très anciennes. Cela peut être le cas, ou cela peut ne pas l’être ; cela dépend de l’industrie dans laquelle vous opérez. Par exemple, dans l’aérospatiale, lorsque vous avez des pièces et des avions ayant une durée de vie opérationnelle de quatre décennies, avoir des données dans votre système pour les quatre dernières décennies est pertinent.
Question : La programmation multi-objectifs est-elle une fonction de deux objectifs ou plus, tels que la somme ou la minimisation de plusieurs fonctions en un seul objectif ?
Il existe plusieurs variantes de la façon dont vous pouvez aborder les objectifs multiples. Il ne s’agit pas d’avoir une fonction qui est une somme, car si vous avez la somme, alors il s’agit simplement d’une question de décomposition et de structure de la fonction de perte. Non, il s’agit vraiment d’avoir un vecteur. Et en effet, il existe essentiellement plusieurs variantes de la programmation multi-objectifs. La variante la plus intéressante est celle où vous voulez opter pour un ordre lexicographique. En ce qui concerne la supply chain, la minimisation, lorsque vous voulez dire que vous prenez la moyenne ou le maximum des nombreuses fonctions, peut être intéressante, mais je n’en suis pas sûr. Je pense que l’approche multi-objectifs, où vous pouvez réellement injecter des contraintes et traiter les contraintes comme faisant partie intégrante de votre optimisation régulière, est très intéressante pour les besoins de la supply chain. Les autres variantes pourraient également être intéressantes, mais je n’en suis pas si sûr. Je ne dis pas qu’elles ne le sont pas ; je dis simplement que je ne suis pas sûr.
Question : Comment décider quand utiliser une solution approximative par rapport à une solution optimisée ?
Je veux dire, je ne suis pas sûr de comprendre la question. L’idée est que, s’il y a une leçon à tirer de l’apprentissage profond, c’est qu’il n’y a pas de solution optimale unique. Tout est une approximation à un certain degré. Même lorsque vous dites que vous avez des chiffres, dans les ordinateurs, les chiffres ne sont pas infiniment précis ; ils sont finis. Et cette précision finie peut en réalité, dans certaines circonstances, vous revenir et vous mordre. Donc la réponse est que c’est toujours approximatif. Je dirais que la plus grande leçon est qu’il est illusoire de penser qu’il existe une solution parfaite. Il n’y a pas de solution parfaite et optimale. Toutes les solutions que vous avez sont des approximations, et certaines sont, je dirais, légèrement plus ou moins approximatives. Donc, je ne suis pas sûr de comprendre le sens de votre question, mais du point de vue de l’optimisation mathématique, cela signifie que vous avez une fonction de perte pour évaluer la qualité, et à la fin de la journée, si vous avez deux solutions concurrentes, vous avez votre fonction de perte pour déterminer laquelle est la meilleure. C’est ainsi que ça fonctionne.
Question : Pourquoi la série temporelle, en termes de données historiques, a-t-elle été divisée par 86 400 en premier lieu ?
Ce n’était pas le cas. C’était un exemple. Je voulais simplement souligner et pousser la situation à un état absurde où vous voyez, lorsque vous utilisez une série temporelle, un algorithme classique de prévision de séries temporelles, vous adoptez ce qu’on appelle une série temporelle à espacement égal. Il existe de nombreuses façons de représenter une série temporelle, et la façon la plus courante de représenter une série temporelle est la série temporelle à espacement égal, où vous effectuez une agrégation par intervalles de longueur égale. C’est généralement ce que vous obtenez avec une agrégation quotidienne ou hebdomadaire. Vous avez des intervalles de même longueur, et votre série a une structure similaire à un vecteur.
Mais ce que je souligne, c’est que cela est arbitraire dans une large mesure. Vous pouvez décider de représenter les données comme des données quotidiennes, mais vous pourriez décider de représenter les données à la seconde. Est-ce que cela aurait un sens de représenter les données à la seconde ? La réponse est oui ; cela dépend du type de problèmes. Par exemple, si vous êtes un fournisseur d’électricité et que vous voulez gérer un réseau, alors vous devez gérer la puissance à chaque seconde afin d’avoir exactement l’équilibre entre l’offre d’électricité dans votre réseau et la consommation d’énergie. Et cet équilibre est réglé à la seconde près. Il peut donc y avoir des situations où il est pertinent de représenter les données à la seconde. Pour les ventes dans votre magasin local, cela peut ne pas avoir de sens. Ce que je voulais souligner avec ce chiffre 86 400, d’ailleurs, c’est simplement 24 heures multipliées par 60 minutes multipliées par 60 secondes, et je voulais clarifier le fait que vous avez toujours une représentation de vos données, et vous ne devez pas confondre la représentation de vos données qui est associée à une certaine dimensionalité avec la dimension intrinsèque de vos données, qui peut avoir une dimension complètement différente. La représentation est, dans une large mesure, complètement arbitraire et inventée. Elle vous donne un indicateur numérique, comme avoir trois ans de données, de sorte que vous avez un vecteur de dimension mille. Mais ce mille est quelque chose qui est en grande partie inventé car il est basé sur la décision d’agréger les données sur une base quotidienne. Si vous choisissiez une autre période alternative, vous obtiendriez une dimension différente. C’est le point que je voulais souligner, et c’est ce que l’apprentissage profond a vraiment bien compris : avoir d’autres choses où vous n’êtes pas trompé en étant confus par des choix arbitraires de représentation des données. Vous voulez être un peu indifférent à la représentation.
Question : En introduisant la prévision probabiliste, nous passons à une fonction de coût et à des contraintes qui sont probabilistes par nature. Quelles implications cela a-t-il sur le processus de recherche d’une solution ?
Eh bien, cela a une contrainte très basique et fondamentale. Si vous avez un solveur qui ne peut pas traiter les problèmes, et encore une fois, rappelez-vous que vous pouvez toujours revenir d’un problème stochastique à un problème déterministe en moyennant simplement votre résultat sur un très grand nombre d’échantillons, alors vous êtes un peu en difficulté en termes de coûts de calcul. Cela signifie que vous devrez dépenser environ 10 000 fois plus de puissance de traitement pour arriver à une solution satisfaisante par rapport à une solution alternative. L’implication est que vous voulez vraiment vous assurer que votre outil d’optimisation mathématique, l’infrastructure que vous avez, est nativement capable de traiter les problèmes stochastiques. C’est exactement ce que vous obtenez avec la programmation différentiable, pas tellement avec la recherche locale, mais vous pouvez améliorer ou réviser la recherche locale pour qu’elle fonctionne plus facilement dans ce genre de situations également.
Fondamentalement, lorsque vous optez pour la prévision probabiliste, cela remet en question non seulement votre vision de l’avenir, mais aussi le type d’outils et d’instruments avec lesquels vous devez travailler ces prévisions. C’est exactement le type d’outils que Lokad développe depuis la dernière décennie. La raison en est que nous avons besoin d’outils qui peuvent bien fonctionner avec le type de problèmes stochastiques qui émergent invariablement dans la supply chain, car pratiquement tous les problèmes de la supply chain comportent une part d’incertitude, et donc ils traitent tous d’un problème stochastique dans une certaine mesure.
Excellent. Donc, la prochaine conférence aura lieu le même jour de la semaine, un mercredi. Il y aura des vacances entre maintenant et cette date. La prochaine conférence aura lieu le 22 septembre et j’espère vous y voir tous. Cette fois-ci, nous parlerons d’apprentissage automatique pour la supply chain. À bientôt.
Références
- The Future of Operational Research Is Past, Russell L. Ackoff, février 1979
- LocalSolver 1.x: A black-box local-search solver for 0-1 programming, Thierry Benoist, Bertrand Estellon, Frédéric Gardi, Romain Megel, Karim Nouioua, septembre 2011
- Automatic differentiation in machine learning: a survey, Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, Jeffrey Mark Siskind, dernière révision en février 2018
