L'approche de l'IA offre des solutions à des problèmes d'optimisation délicats, du routage global des packages à l'exploitation du réseau électrique.

Alors que le Père Noël dispose d'un traîneau magique et de neuf rennes courageux pour l'aider à livrer les cadeaux, pour des entreprises comme FedEx, le problème d'optimisation de l'acheminement efficace des colis de vacances est si complexe qu'elles utilisent souvent un logiciel spécialisé pour trouver une solution.

Ce logiciel, appelé solveur de programmation linéaire en nombres entiers mixtes (MILP), divise un problème d'optimisation massif 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 parvenir à une solution.

Le processus est si onéreux 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 puisse être générée dans un laps de temps défini.

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

Ils ont identifié une étape intermédiaire clé dans les solveurs MILP qui comporte tellement de solutions potentielles qu'elle prend énormément de temps à démêler, 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 à 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 à usage général au problème en question.

Cette nouvelle technique a accéléré les solveurs MILP entre 30 et 70 pour cent, sans aucune perte 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 raisonnable.

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

« Parfois, dans un domaine comme l'optimisation, il est très courant que les gens pensent aux solutions comme étant purement du machine learning ou purement classiques. Je suis fermement convaincu que nous voulons tirer le meilleur parti des deux mondes, et c'est un très fort instanciation de cette approche hybride », déclare l'auteur principal Cathy Wu, professeur adjoint de 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 du Institut des données, des systèmes et de la société (IDSS).

Wu a écrit l'article avec les co-auteurs principaux Siriu Li, étudiant diplômé de l'IDSS, et Wenbin Ouyang, étudiant diplômé du CEE ; ainsi que Max Paulus, étudiant diplômé à l'ETH Zurich. La recherche sera présentée à la Conférence sur les systèmes de traitement de l'information neuronale.

Difficile à résoudre

Les problèmes MILP ont un nombre exponentiel de solutions potentielles. Par exemple, supposons qu'un vendeur itinérant souhaite trouver le chemin le plus court pour visiter plusieurs villes, puis retourner dans sa ville d'origine. S’il existe 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 dans l’univers.

“Ces problèmes sont appelés 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 suffisamment important, nous ne pouvons qu'espérer obtenir des performances sous-optimales”, explique Wu.

Un solveur MILP utilise un éventail de techniques et d'astuces pratiques qui permettent d'obtenir des solutions raisonnables dans un laps de temps raisonnable.

Un solveur typique utilise une approche diviser pour régner, en divisant d’abord l’espace des solutions potentielles en morceaux plus petits grâce à une technique appelée branchement. Ensuite, le solveur utilise une technique appelée découpe pour resserrer ces petits morceaux afin qu'ils puissent être recherchés plus rapidement.

Cutting 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 dizaines d’algorithmes, appelés séparateurs, 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éparation à utiliser est, en soi, un problème avec un nombre exponentiel de solutions.

“La gestion des séparateurs est un élément essentiel de tout solveur, mais il s'agit d'un aspect sous-estimé de l'espace des problèmes. L'une des contributions de ce travail consiste à identifier le problème de la gestion des séparateurs comme une tâche d'apprentissage automatique”, dit-elle.

Réduire l'espace de solution

Elle et ses collaborateurs ont conçu un mécanisme de filtrage qui réduit cet espace de recherche de séparateur 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, selon lequel le plus grand bénéfice viendrait d'un petit ensemble d'algorithmes, et l'ajout d'algorithmes supplémentaires n'apporterait pas beaucoup d'amélioration supplémentaire.

Ils utilisent ensuite un modèle d’apprentissage automatique pour sélectionner la meilleure combinaison d’algorithmes parmi les 20 options restantes.

Ce modèle est formé avec un ensemble de données spécifique au problème d'optimisation de l'utilisateur, il apprend donc à choisir les algorithmes les mieux adaptés à la tâche particulière de l'utilisateur. Étant donné qu’une entreprise comme FedEx a résolu des problèmes de routage à plusieurs reprises auparavant, l’utilisation de données réelles tirées de l’expérience passée devrait conduire à de meilleures solutions que de repartir 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, consiste à choisir une solution potentielle, à obtenir des commentaires sur sa qualité, puis à réessayer pour trouver une meilleure solution.

Cette approche basée sur les données a accéléré les solveurs MILP entre 30 et 70 % sans aucune perte de précision. De plus, l’accélération était similaire lorsqu’ils l’appliquaient à un solveur open source plus simple et à un solveur commercial plus puissant.

À l’avenir, Wu et ses collaborateurs souhaitent appliquer cette approche à des problèmes MILP encore plus complexes, où la collecte de données étiquetées pour entraîner le modèle pourrait s’avérer particulièrement difficile. Peut-être pourraient-ils entraîner le modèle sur un ensemble de données plus petit, puis le modifier pour résoudre un problème d'optimisation beaucoup plus vaste, dit-elle. Les chercheurs souhaitent également interpréter le modèle appris pour mieux comprendre l’efficacité des différents algorithmes de séparation.

L'ouvrage est publié sur le arXiv serveur de préimpression.

Cette histoire est republiée avec l'aimable autorisation de MIT News (web.mit.edu/newsoffice/), un site populaire qui couvre l'actualité de la recherche, de l'innovation et de l'enseignement du MIT.