La révolution de l’IA dans la résolution de problèmes complexes logistiques et au-delà

Patrick Lesggie

Des chercheurs du MIT et de l’ETH Zurich ont développé une technique basée sur l’apprentissage automatique pour accélérer le processus d’optimisation utilisé par des entreprises comme FedEx pour le routage des colis. Cette approche, qui simplifie une étape clé dans les solveurs de programmation linéaire à variables mixtes (MILP) et adapte le processus à l’aide des données propres à une entreprise, a entraîné une augmentation de la vitesse de 30 à 70 pour cent sans sacrifier la précision. Elle présente des applications potentielles dans diverses industries confrontées à des problèmes complexes d’allocation de ressources.

Une nouvelle approche basée sur les données pourrait conduire à de meilleures solutions pour des problèmes d’optimisation difficiles tels que le routage mondial des colis ou le fonctionnement du réseau électrique.

Des chercheurs du MIT et de l’ETH Zurich ont développé une nouvelle technique basée sur l’apprentissage machine qui pourrait être appliquée à de nombreux défis logistiques complexes, tels que le routage des colis, la distribution de vaccins et la gestion du réseau électrique.

Alors que le Père Noël possède un traîneau magique et neuf rennes intrépides pour l’aider à distribuer des cadeaux, pour des entreprises comme FedEx, le problème d’optimisation du routage efficace de colis pendant les fêtes est si complexe qu’elles utilisent souvent un logiciel spécialisé pour trouver une solution.

Ce logiciel, appelé solveur de programmation linéaire à variables mixtes (MILP), divise un énorme problème d’optimisation en morceaux plus petits et utilise des algorithmes génériques pour essayer de trouver la meilleure solution. Cependant, le solveur peut prendre des heures, voire des jours, pour arriver à une solution.

Le processus est si fastidieux qu’une entreprise doit souvent arrêter le logiciel en cours de route, acceptant une solution qui n’est pas idéale mais la meilleure qui a pu être générée dans un laps de temps donné.

Des chercheurs du MIT et de l’ETH Zurich ont utilisé l’apprentissage automatique pour accélérer le processus.

Ils ont identifié une étape intermédiaire clé dans les solveurs MILP qui comporte tellement de solutions potentielles qu’il faut énormément de temps pour les résoudre, ce qui ralentit l’ensemble du processus. Les chercheurs ont utilisé une technique de filtrage pour simplifier cette étape, puis ont utilisé l’apprentissage automatique pour trouver la solution optimale pour un type spécifique de problème.

Leur approche basée sur les données permet à une entreprise d’utiliser ses propres données pour adapter un solveur MILP générique au problème en cours.

Cette nouvelle technique a accéléré les solveurs MILP de 30 à 70 pour cent, sans aucune baisse de précision. On pourrait utiliser cette méthode pour obtenir une solution optimale plus rapidement ou, pour des problèmes particulièrement complexes, une meilleure solution dans un laps de temps réalisable.

Cette approche pourrait être utilisée partout où des solveurs MILP sont employés, comme par les services de covoiturage, les opérateurs de réseau électrique, les distributeurs de vaccins ou toute entité confrontée à un problème complexe d’allocation de ressources.

« Parfois, dans un domaine comme l’optimisation, il est très courant pour les gens de considérer les solutions comme étant soit purement basées sur l’apprentissage automatique, soit purement classiques. Je suis convaincue que nous voulons tirer le meilleur parti des deux mondes, et c’est une très forte instantiation de cette approche hybride », explique l’auteur principal Cathy Wu, professeure adjointe en développement de carrière Gilbert W. Winslow en génie civil et environnemental (CEE), et membre du Laboratoire des Systèmes d’information et de décision (LIDS) et de l’Institut des données, des systèmes et de la société (IDSS)

Wu a rédigé l’article avec les co-auteurs principaux Sirui Li, étudiant diplômé de l’IDSS, et Wenbin Ouyang, étudiant diplômé de CEE; ainsi que Max Paulus, un étudiant diplômé de l’ETH Zurich. La recherche sera présentée lors de la Conférence sur le traitement de l’information neuronale.

Dur à résoudre

Les problèmes MILP ont un nombre exponentiel de solutions potentielles. Par exemple, un voyageur veut trouver le chemin le plus court pour visiter plusieurs villes et revenir à sa ville d’origine. S’il y a de nombreuses villes qui pourraient être visitées dans n’importe quel ordre, le nombre de solutions potentielles pourrait être supérieur au nombre d’atomes de l’univers.

« Ces problèmes sont qualifiés de NP-difficiles, ce qui signifie qu’il est très peu probable qu’il existe un algorithme efficace pour les résoudre. Lorsque le problème est assez grand, nous ne pouvons espérer qu’obtenir une performance suboptimale », explique Wu.

Un solveur MILP utilise une série de techniques et de trucs pratiques qui peuvent parvenir à des solutions raisonnables dans un laps de temps réalisable.

Un solveur typique utilise une approche de division et de conquête, divisant d’abord l’espace des solutions potentielles en morceaux plus petits avec une technique appelée branchements. Ensuite, le solveur utilise une technique appelée coupe pour resserrer ces morceaux plus petits afin qu’ils puissent être recherchés plus rapidement.

La technique de coupe utilise un ensemble de règles qui resserrent l’espace de recherche sans supprimer aucune solution réalisable. Ces règles sont générées par quelques douzaines d’algorithmes, connus sous le nom de séparateurs, qui ont été créés pour différents types de problèmes MILP.

Wu et son équipe ont découvert que le processus d’identification de la combinaison idéale d’algorithmes de séparateurs à utiliser est, en soi, un problème avec un nombre exponentiel de solutions.

« La gestion des séparateurs est une partie essentielle de chaque solveur, mais c’est un aspect sous-estimé de l’espace des problèmes. Une des contributions de ce travail est d’identifier la gestion des séparateurs comme une tâche d’apprentissage automatique pour commencer », dit-elle.

Réduction de l’espace des solutions

Elle et ses collaborateurs ont élaboré un mécanisme de filtrage qui réduit cet espace de recherche des séparateurs de plus de 130 000 combinaisons potentielles à environ 20 options. Ce mécanisme de filtrage s’appuie sur le principe des rendements marginaux décroissants, qui dit que le plus grand bénéfice proviendrait d’un petit ensemble d’algorithmes, et l’ajout d’algorithmes supplémentaires ne apporterait pas grand-chose d’autre.

Ensuite, ils utilisent un modèle d’apprentissage automatique pour choisir la meilleure combinaison d’algorithmes parmi les 20 options restantes.

Ce modèle est entraîné avec un ensemble de données spécifique au problème d’optimisation de l’utilisateur, de sorte qu’il apprend à choisir les algorithmes qui conviennent le mieux à la tâche particulière de l’utilisateur. Comme une entreprise comme FedEx a résolu des problèmes de routage de nombreuses fois auparavant, l’utilisation de données réelles obtenues à partir de l’expérience passée devrait conduire à de meilleures solutions que de commencer à partir de zéro à chaque fois.

Le processus d’apprentissage itératif du modèle, connu sous le nom de bandits contextuels, une forme d’apprentissage par renforcement, implique le choix d’une solution potentielle, de recevoir des commentaires sur sa qualité, puis d’essayer à nouveau de trouver une meilleure solution.

Cette approche basée sur les données a accéléré les solveurs MILP de 30 à 70 pour cent sans aucune baisse de précision. De plus, le gain de vitesse a été similaire lorsqu’ils l’ont appliqué à un solveur plus simple, en open source, et un solveur plus puissant, commercial.

Dans le futur, Wu et ses collaborateurs veulent appliquer cette approche à des problèmes MILP encore plus complexes, où il pourrait être particulièrement difficile de collecter des données étiquetées pour entraîner le modèle. Peut-être peuvent-ils entraîner le modèle sur un ensemble de données plus petit, puis l’adapter pour aborder un problème d’optimisation beaucoup plus grand, dit-elle. Les chercheurs sont également intéressés par l’interprétation du modèle appris pour mieux comprendre l’efficacité des différents algorithmes de séparateurs.

Référence: « Learning to Configure Separators in Branch-and-Cut » par Sirui Li, Wenbin Ouyang, Max B. Paulus et Cathy Wu, 8 novembre 2023, Mathématiques > Optimisation et Contrôle.
arXiv:2311.05650

Cette recherche est soutenue, en partie, par Mathworks, la National Science Foundation (NSF), le MIT Amazon Science Hub, et le comité de soutien à la recherche du MIT.