Cette percée ressemble presque à Lucky Luke, l’homme qui tire plus vite que son ombre. Rasmus Kyng et son équipe ont développé un algorithme ultra-rapide qui devrait changer tout un domaine de recherche. Plus précisément, l’équipe de Kyng a écrit ce qu’on appelle un algorithme de flux de réseau qui répond à la question suivante : "Comment obtenir un flux de trafic maximal dans un réseau tout en minimisant les coûts de transport ?"
Imaginez que vous utilisiez le réseau de transport européen et que vous souhaitiez trouver le moyen le plus rapide et le moins cher d’acheminer le plus de marchandises possible de Copenhague à Milan. Pour ce genre de cas, l’algorithme de Kyng calcule le flux de trafic optimal et le plus économique, et ce pour tout type de réseau, qu’il s’agisse du rail, de la route, de l’eau ou d’Internet. Son algorithme calcule si rapidement qu’il présente la solution au moment même où un ordinateur lit les données décrivant le réseau.
Il calcule aussi vite que la taille du réseau.
Personne n’y était parvenu avant Rasmus Kyng. Bien que ce problème fasse l’objet de recherches depuis environ 90 ans. Jusqu’à présent, le calcul du flux de trafic optimal prenait toujours beaucoup plus de temps que le traitement des données du réseau. En fait, plus la taille et la complexité d’un réseau augmentaient, plus le temps de calcul nécessaire était important, bien plus que la taille réelle du problème de calcul. C’est pourquoi il existe des problèmes de flux dans les réseaux qui sont trop importants pour qu’un ordinateur puisse les calculer.Ce n’est pas le cas de Rasmus Kyng : dans son algorithme, le temps de calcul augmente au même rythme que la taille du réseau - c’est un peu comme si vous vous lanciez dans une randonnée en montagne et que votre rythme de marche ne faiblissait pas une minute, même si le chemin de randonnée devenait de plus en plus raide ! Cette performance se reflète dans les chiffres bruts : Jusqu’au tournant du millénaire, aucun algorithme ne parvenait à calculer plus vite que m1,5, où m représente le nombre de connexions dans un réseau que l’ordinateur doit calculer - et le simple fait de lire une fois les données du réseau prend m de temps. A partir de 2004, il a été possible de réduire le temps de calcul nécessaire à la résolution du problème à m1,33. Avec l’algorithme de Kyng, le temps de calcul "supplémentaire" nécessaire pour obtenir une solution après la lecture des données du réseau est désormais tout simplement négligeable.
Comme une Porsche contre des voitures à cheval
Les chercheurs ont ainsi développé l’algorithme de flux réseau théoriquement le plus rapide possible. Rasmus Kyng et son équipe en ont apporté la preuve mathématique il y a deux ans dans un article révolutionnaire. Dans le jargon technique, ces nouveaux algorithmes d’une rapidité quasi optimale sont également appelés "algorithmes à temps presque linéaire". La communauté des informaticiens théoriques a été agréablement surprise et enthousiasmée par la percée de Kyng.Le directeur de thèse de Kyng, Daniel A. Spielman, professeur de mathématiques et d’informatique à Yale et lui-même pionnier et doyen dans ce domaine, a comparé l’algorithme "absurdement rapide" à une Porsche qui dépasse les voitures à cheval. Leur travail a été récompensé par le prix du meilleur article lors du symposium annuel de l’IEEE sur les fondements de l’informatique en 2022, par le journal informatique Communications of the ACM, et l’algorithme de Kyng a été classé parmi les dix plus grandes découvertes informatiques de 2022 par le magazine de vulgarisation Quanta Magazine.
Depuis, les chercheurs ont affiné leur approche et développé d’autres algorithmes de temps presque linéaire. Par exemple, le premier algorithme concernait encore des réseaux statiques immuables dont les connexions sont directionnelles, c’est-à-dire qu’elles fonctionnent comme des rues à sens unique dans les réseaux routiers urbains. Les algorithmes publiés cette année peuvent désormais calculer des flux optimaux pour des réseaux qui changent progressivement au fil du temps. Pour les réseaux très complexes et très riches en données, qui évoluent dynamiquement et très rapidement - comme les molécules ou le cerveau en biologie, ou comme les relations amicales humaines - un calcul ultrarapide devient une étape importante.
Des algorithmes ultra-rapides pour des réseaux changeants
Jeudi, Simon Meierhans, de l’équipe de Kyng, a présenté à Vancouver, lors du "Annual ACM Symposium on Theory of Computing (STOC)", un nouvel algorithme à temps presque linéaire. Celui-ci résout le problème du coût minimum et du flux maximum, même pour les réseaux qui se modifient progressivement par l’ajout de nouvelles connexions. Dans un deuxième document, adopté par le "IEEE Symposium on Foundations of Computer Science (FOCS)" d’octobre prochain, les chercheurs ont en outre développé un autre algorithme qui prend également en compte la suppression de connexions.Ces algorithmes déterminent les itinéraires les plus courts, notamment dans les réseaux où des liaisons sont ajoutées ou supprimées. Dans les réseaux de transport réels, de telles modifications se produisent par exemple lorsque, comme depuis l’été 2023, le tunnel de base du Gothard est d’abord entièrement puis partiellement fermé ou lorsqu’un glissement de terrain détruit actuellement une partie de la route nationale A13, qui est la principale route alternative au tunnel routier du Gothard.
Dans de tels cas, comment un ordinateur, un service de cartographie en ligne ou un calculateur d’itinéraire routier calcule-t-il la liaison la plus rapide et la moins chère entre Milan et Copenhague ? Les nouveaux algorithmes de Kyng calculent également l’itinéraire optimal pour ces réseaux qui changent progressivement en un temps presque linéaire, c’est-à-dire si rapide que le temps de calcul pour chaque nouvelle liaison - par déviation ou construction nouvelle - est à nouveau négligeable.
Qu’est-ce qui rend la méthode de calcul de Kyng si rapide par rapport à tous les autres algorithmes de flux réseau ? En principe, toutes les méthodes de calcul connaissent le défi de devoir calculer le réseau en plusieurs itérations afin de trouver le flux optimal et l’itinéraire le plus avantageux. Ce faisant, ils calculent à chaque fois les différentes variantes de connexions ouvertes, bloquées ou bouchées lorsqu’elles ont atteint leur limite de capacité.
Calculer quoi ? Le tout ou ses parties ?
Avant Rasmus Kyng, il existait principalement deux stratégies de solution : l’une s’inspirait du réseau ferroviaire et calculait à chaque itération une partie entière du trajet avec un flux de trafic modifié. L’autre s’inspirait du flux électrique dans le réseau électrique. Elle calculait l’ensemble du réseau à chaque itération, mais utilisait des valeurs moyennes statistiques pour le flux modifié d’une partie du trajet afin de calculer plus rapidement."Notre approche repose sur de très nombreuses petites étapes de calcul efficaces et peu coûteuses, qui sont globalement beaucoup plus rapides que quelques grandes étapes".
L’équipe de Rasmus Kyng prend désormais en compte les avantages respectifs des deux approches et les combine en une approche radicalement nouvelle. "Notre approche repose sur de très nombreuses petites étapes de calcul efficaces et peu coûteuses, qui sont globalement beaucoup plus rapides que quelques grandes étapes", explique Maximilian Probst Gutenberg, maître de conférences et collaborateur du groupe de Kyng, qui a largement contribué au développement des algorithmes de temps presque linéaire.
Un regard sur l’histoire de la discipline révèle des dimensions supplémentaires de la portée de la percée de Rasmus Kyng : après tout, les problèmes de flux dans les réseaux ont été parmi les premiers à être résolus systématiquement à l’aide d’algorithmes dans les années 1950, et les algorithmes de flux ont joué un rôle important dans l’établissement de l’informatique théorique comme domaine de recherche à part entière. C’est de cette époque que date le célèbre algorithme des mathématiciens Lester R. Ford Jr. et Delbert R. Fulkerson, qui résout efficacement le problème du flux maximal, c’est-à-dire comment transporter le plus de marchandises possible à travers un réseau sans dépasser les limites de capacité des différentes routes.
Pas seulement rapide, mais aussi complet
On sait depuis cette époque que les principaux problèmes de flux de réseau, tels que le problème du flux maximal, le problème du coût minimal (dit problème de transbordement ou de transport) et d’autres encore, sont en principe des cas particuliers du problème global du flux minimal-cost. Avant Rasmus Kyng, la plupart des algorithmes ne parvenaient à résoudre efficacement qu’un seul de ces sous-problèmes. Ils n’étaient toutefois pas particulièrement rapides et ne pouvaient pas être étendus au problème plus vaste du min-cost-flow. Cela vaut également pour les algorithmes de flux novateurs des années 1970, pour lesquels les informaticiens théoriques John Edward Hopcroft, Richard Manning Karp et Robert Endre Tarjan ont remporté en 1985 et 1986 le Turing Award, considéré comme le prix Nobel de l’informatique.Changement de perspective du rail au courant
Ce n’est qu’en 2004 que les mathématiciens et informaticiens Daniel Spielman et Shang-Hua Teng, et plus tard Samuel Daitch, sont parvenus à écrire de tels algorithmes qui résolvaient également le problème du Minimum-Cost Flow de manière rapide et efficace. Ce sont également eux qui se sont inspirés du flux électrique dans le réseau électrique. Leur changement de perspective, du rail à l’électricité, a entraîné une différence considérable sur le plan mathématique : dans le réseau ferroviaire, si un train est détourné parce qu’une ligne est supprimée, il peut arriver que la prochaine meilleure ligne selon l’horaire soit déjà occupée par un autre train. Dans le réseau électrique, en revanche, il est possible que les électrons qui forment le flux de courant soient partiellement déviés vers une liaison du réseau où circule déjà un autre courant. Contrairement aux trains, le courant peut donc être mathématiquement "partiellement" transféré sur une nouvelle connexion."Nous avons rejeté l’approche consistant à concevoir des algorithmes aussi puissants que possible pour l’ensemble du réseau".
Cette redirection partielle a permis à Spielman et à ses collègues de calculer ces changements d’itinéraire beaucoup plus rapidement, tout en calculant l’ensemble du réseau à chaque changement. "Nous avons rejeté l’approche de Spielman qui consistait à concevoir des algorithmes aussi puissants que possible pour l’ensemble du réseau", explique Rasmus Kyng, "nous avons plutôt transposé son idée de calcul de parcours partiel aux approches antérieures de Hopcroft et Karp". Ce calcul de parcours partiel par itération a largement contribué à accélérer le calcul du flux global.
Au tournant des bases théoriques
Ce qui est décisif pour le progrès des chercheurs, c’est qu’il ne se limite pas au développement de nouveaux algorithmes. Au contraire, ils utilisent et conçoivent également de nouveaux outils mathématiques qui accélèrent leurs algorithmes. Ils ont notamment développé une nouvelle structure de données qui organise les données du réseau de manière à ce que chaque modification d’une connexion dans le réseau puisse être trouvée extrêmement rapidement et contribue ainsi à la solution algorithmique ultrarapide. Comme il existe de nombreuses applications pour les algorithmes en temps quasi linéaire et pour des outils tels que la nouvelle structure de données, la spirale de l’innovation devrait bientôt tourner beaucoup plus vite que jusqu’à présent.Les algorithmes de flux nettement plus rapides ne posent en tout cas pas seulement les bases pour résoudre de très grands problèmes, souvent impossibles à calculer efficacement jusqu’à présent, mais ils modifient aussi la manière dont les ordinateurs calculent des tâches complexes en général. "Ces dix dernières années, on a assisté à une révolution dans les fondements théoriques d’algorithmes avérés rapides pour des problèmes fondamentaux de l’informatique théorique", écrit à ce sujet un groupe international de chercheurs de l’université de Berkeley, dont font également partie Rasmus Kyng et Deeksha Adil, chercheuse à l’Institut d’études théoriques de l’EPF de Zurich.
Références bibliographiques
van den Brand, J, Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M, Sachdeva, S. Almost-Linear Time Algorithms for Decremental Graphs : Min-Cost Flow and More via Duality. 65e symposium IEEE sur les fondements de l’informatique (FOCS) 2024. https://focs.computer.org/2024/accepted-papers-for-focs-2024/Chen, L, Kyng, R, Liu, YP, Meierhans, S, Probst Gutenberg, M. Algorithmes de temps quasi-linéaires pour les graphes incrémentaux : détection de cycle, SCCs, s-t Shortest Path, et Minimum-Cost Flow. Actes du 56e symposium annuel de l’ACM sur la théorie de l’informatique, juin 2024 (STOC 2024). doi : https://doi.org/10.1145/3618260.3649745 .
Chen, L, Kyng, R, Liu, YP, Peng, R, Probst Gutenberg, M, Sachdeva, S, Kyng, R. Maximum flow and minimum-cost flow in almost-linear time. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA, 2022. doi : 10.1109/FOCS54457.2022.00064 .
