Des chercheurs de l'ETH développent l'algorithme de flux le plus rapide possible

Cette avancée fait presque penser à 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. En fait, 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 pour transporter le plus de marchandises possible de Copenhague à Milan. Pour de tels 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 qu'un réseau est grand

Personne n'y était parvenu avant Rasmus Kyng. Bien que des recherches soient menées sur ce problème 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 m^1,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 du temps. m de temps. A partir de 2004, on est parvenu à réduire le temps de calcul nécessaire à la résolution des problèmes à m^1,33 de réduire les co?ts. 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 les voitures à cheval

Les chercheurs de l'ETH 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 en tout cas été agréablement surprise et a réagi avec enthousiasme à 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. Son travail a été récompensé en 2022 par le prix du meilleur article lors du symposium annuel de l'IEEE sur les fondements de l'informatique, par le journal informatique Communications of the ACM, et par le magazine de vulgarisation Quanta Magazine, qui a classé l'algorithme de Kyng parmi les "meilleurs". c?té externedix plus grandes découvertes de l'année 2022 en informatique..

Depuis, les chercheurs de l'ETH ont affiné leur approche et développé d'autres algorithmes de temps presque linéaire. Par exemple, le premier algorithme se référait encore à des réseaux statiques immuables dont les connexions sont orientées, 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 constitue une étape importante.

Des algorithmes rapides comme l'éclair 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 de temps presque linéaire. Celui-ci résout le problème du Minimum Cost Maximum Flow également pour les réseaux qui se modifient progressivement par l'ajout de nouvelles connexions. Dans un deuxième document, accepté par le "IEEE Symposium on Foundations of Computer Science (FOCS)" d'octobre prochain, les chercheurs de l'ETH ont en outre développé un autre algorithme qui tient également compte de la suppression de connexions.

Ces algorithmes déterminent les itinéraires les plus courts, notamment dans les réseaux où des connexions sont ajoutées ou supprimées. Dans les réseaux de transport réels, de tels changements se produisent par exemple lorsque, comme depuis l'été 2023, le tunnel de base du Saint-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 Saint-Gothard.

Dans de tels cas, comment un ordinateur, un service de cartographie en ligne ou un calculateur d'itinéraire de transport calcule-t-il la liaison la plus rapide et la plus économique 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 nouvelle construction - 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 de 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 un tron?on entier 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.

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, enseignant 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

Depuis cette époque, on sait que les problèmes de flux de réseau importants 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 représentent en principe des cas spéciaux 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 prix Turing, 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, ont réussi à é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 par laquelle circule déjà un autre courant. Contrairement aux trains, le courant peut donc être mathématiquement "partiellement" transféré sur une nouvelle connexion.

Cette redirection partielle a permis à Spielman et à ses collègues de calculer beaucoup plus rapidement de telles modifications de parcours et, en même temps, de calculer également l'ensemble du réseau à chaque modification. "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 les progrès des chercheurs de l'ETH, c'est qu'ils ne se limitent pas au développement de nouveaux algorithmes. Au contraire, ils utilisent et con?oivent également de nouveaux outils mathématiques qui accélèrent encore 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 toute 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 qu'auparavant.

En tout cas, les algorithmes de flux nettement plus rapides ne posent 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", c?té externeécrit à ce sujet un groupe international par des chercheurs de l'Université de Berkeley, dont font également partie Rasmus Kyng et Deeksha Adil, chercheuse à l'Institut d'études théoriques de l'ETH Zurich.