Les chercheurs développent l’algorithme de flux le plus rapide possible

Dans une avancée qui rappelle Lucky Luke, l’homme qui tire plus vite que son ombre, Rasmus Kyng et son équipe ont développé un algorithme ultra-rapide qui semble prêt à transformer tout un domaine de recherche.

Le travail révolutionnaire de l’équipe de Kyng implique ce que l’on appelle un algorithme de flux de réseau, qui aborde la question de savoir comment atteindre le flux maximum dans un réseau tout en minimisant simultanément les coûts de transport.

Imaginez que vous utilisez le réseau de transport européen et que vous recherchez l’itinéraire le plus rapide et le moins cher pour transporter autant de marchandises que possible de Copenhague à Milan. L’algorithme de Kyng peut être appliqué dans de tels cas pour calculer le flux de trafic optimal et le moins coûteux pour tout type de réseau, qu’il s’agisse du rail, de la route, de l’eau ou d’Internet.

Son algorithme effectue ces calculs si rapidement qu’il peut fournir la solution au moment même où un ordinateur lit les données qui décrivent le réseau.

Des calculs aussi rapides qu’un réseau est grand

Avant Kyng, personne n’avait jamais réussi à faire cela, même si les chercheurs travaillent sur ce problème depuis près de 90 ans. Auparavant, il fallait beaucoup plus de temps pour calculer le flux optimal que pour traiter les données du réseau.

Et à mesure que le réseau devenait plus grand et plus complexe, le temps de calcul requis augmentait, en comparaison, beaucoup plus rapidement que la taille réelle du problème informatique. C’est pourquoi nous constatons également des problèmes de flux dans des réseaux trop grands pour qu’un ordinateur puisse même les calculer.

L’approche de Kyng élimine ce problème : en utilisant son algorithme, le temps de calcul et la taille du réseau augmentent au même rythme, un peu comme lors d’une randonnée et en gardant constamment le même rythme, quelle que soit la pente du chemin.

Un coup d’œil aux chiffres bruts montre le chemin parcouru : jusqu’au tournant du millénaire, aucun algorithme ne parvenait à calculer plus vite que m.^1,5où m représente le nombre de connexions dans un réseau que l’ordinateur doit calculer, et la simple lecture des données du réseau prend m temps.

En 2004, la vitesse de calcul requise pour résoudre le problème a été réduite avec succès à m^1,33Grâce à l’algorithme de Kyng, le temps de calcul « supplémentaire » nécessaire pour atteindre la solution après la lecture des données du réseau est désormais négligeable.

Comme une Porsche qui fait la course avec une calèche

Les chercheurs de l’ETH Zurich ont ainsi développé ce qui est en théorie l’algorithme de flux de réseau le plus rapide possible. Il y a deux ans, Kyng et son équipe ont présenté une preuve mathématique de leur concept dans un article révolutionnaire. Les scientifiques qualifient ces nouveaux algorithmes d’une rapidité presque optimale d’« algorithmes à temps presque linéaire », et la communauté des informaticiens théoriques a répondu à la percée de Kyng avec un mélange d’étonnement et d’enthousiasme.

Le directeur de thèse de Kyng, Daniel A. Spielman, professeur de mathématiques appliquées et d’informatique à Yale et lui-même pionnier et doyen dans ce domaine, a comparé l’algorithme « absurdement rapide » à une Porsche dépassant des calèches.

En plus d’avoir remporté le prix du meilleur article 2022 au Symposium annuel de l’IEEE sur les fondements de l’informatique (FOCS), leur article a également été mis en avant dans la revue informatique. Communication de l’ACMet les rédacteurs du magazine scientifique populaire Quanta ont désigné l’algorithme de Kyng comme l’une des dix plus grandes découvertes en informatique en 2022.

Les chercheurs de l’ETH Zurich ont depuis affiné leur approche et développé d’autres algorithmes en temps quasi-linéaire. Par exemple, le premier algorithme était encore axé sur des réseaux fixes et statiques dont les connexions sont dirigées, c’est-à-dire qu’ils fonctionnent comme des rues à sens unique dans les réseaux routiers urbains.

Les algorithmes publiés cette année sont désormais également capables de calculer des flux optimaux pour des réseaux qui évoluent progressivement au fil du temps. Des calculs ultra-rapides constituent une étape importante pour traiter des réseaux extrêmement complexes et riches en données qui évoluent de manière dynamique et très rapide, comme les molécules ou le cerveau en biologie, ou les amitiés humaines.

Des algorithmes ultra-rapides pour changer de réseau

Jeudi, Simon Meierhans, membre de l’équipe de Kyng, a présenté un nouvel algorithme à temps quasi linéaire lors du Symposium annuel de l’ACM sur la théorie de l’informatique (STOC 2024) à Vancouver. Cet algorithme résout le problème du débit maximal à coût minimum pour les réseaux qui évoluent progressivement à mesure que de nouvelles connexions sont ajoutées.

De plus, dans un deuxième article accepté par le Symposium IEEE sur les fondements de l’informatique (FOCS) en octobre, les chercheurs de l’ETH Zurich ont développé un autre algorithme qui gère également les connexions supprimées.

Plus précisément, ces algorithmes identifient les itinéraires les plus courts dans les réseaux où des connexions sont ajoutées ou supprimées. Dans les réseaux de circulation réels, la fermeture complète puis la réouverture partielle du tunnel de base du Saint-Gothard au cours des mois qui ont suivi l’été 2023, ou le récent glissement de terrain qui a détruit une partie de l’autoroute A13, qui constitue la principale alternative, sont des exemples de tels changements en Suisse. route vers le tunnel routier du Saint-Gothard.

Face à de tels changements, comment un ordinateur, un service de cartographie en ligne ou un planificateur d’itinéraire calcule-t-il la liaison la moins chère et la plus rapide entre Milan et Copenhague ? Les nouveaux algorithmes de Kyng calculent également l’itinéraire optimal pour ces réseaux changeant de manière incrémentale ou décrémentielle dans un temps presque linéaire, si rapidement que le temps de calcul pour chaque nouvelle connexion, qu’elle soit ajoutée via un réacheminement ou la création de nouveaux itinéraires, est à nouveau négligeable.

Mais qu’est-ce qui rend exactement l’approche de Kyng en matière de calculs beaucoup plus rapide que tout autre algorithme de flux réseau ? En principe, toutes les méthodes de calcul sont confrontées au défi de devoir analyser le réseau en plusieurs itérations afin de trouver le flux optimal et l’itinéraire au coût minimum. Ce faisant, ils parcourent chacune des différentes variantes dont les connexions sont ouvertes, fermées ou encombrées parce qu’elles ont atteint leur limite de capacité.

Calculer le tout ? Ou ses parties ?

Avant Kyng, les informaticiens avaient tendance à choisir entre deux stratégies clés pour résoudre ce problème. L’une d’elles était calquée sur le réseau ferroviaire et impliquait le calcul d’une section entière du réseau avec un flux de trafic modifié à chaque itération. La deuxième stratégie, inspirée des flux d’énergie dans le réseau électrique, calculait l’ensemble du réseau à chaque itération, mais utilisait des valeurs moyennes statistiques pour le flux modifié de chaque section du réseau afin de rendre le calcul plus rapide.

L’équipe de Kyng a désormais combiné les avantages respectifs de ces deux stratégies afin de créer une approche combinée radicalement nouvelle. « Notre approche repose sur de nombreuses petites étapes de calcul efficaces et peu coûteuses, qui, prises ensemble, sont bien plus rapides que quelques grandes étapes », explique Maximilian Probst Gutenberg, professeur et membre du groupe de Kyng, qui a joué un rôle clé dans le développement des algorithmes à temps quasi linéaire.

Un bref aperçu de l’histoire de cette discipline ajoute une dimension supplémentaire à l’importance de la percée de Kyng : 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 un domaine de recherche à part entière.

De cette période est également issu l’algorithme bien connu développé par les mathématiciens Lester R. Ford Jr. et Delbert R. Fulkerson. Leur algorithme résout efficacement le problème du flux maximal, qui cherche à déterminer comment transporter autant de marchandises que possible à travers un réseau sans dépasser la capacité des itinéraires individuels.

Rapide et varié

Ces progrès ont montré aux chercheurs que le problème du flux maximum, le problème du coût minimum (problème de transbordement ou de transport) et de nombreux autres problèmes importants de flux de réseau peuvent tous être considérés comme des cas particuliers du problème général du flux à coût minimum.

Avant les recherches de Kyng, la plupart des algorithmes n’étaient capables de résoudre efficacement qu’un seul de ces problèmes, même s’ils ne pouvaient pas le faire particulièrement rapidement, ni être étendus au problème plus large du flux à coût minimum.

Il en va de même pour les algorithmes de flux pionniers des années 1970, pour lesquels les informaticiens théoriciens John Edward Hopcroft, Richard Manning Karp et Robert Endre Tarjan ont reçu chacun un prix Turing, considéré comme le « prix Nobel » de l’informatique. Karp a reçu le sien en 1985, Hopcroft et Tarjan en 1986.

Changement de perspective du ferroviaire à l’électricité

Ce n’est qu’en 2004 que les mathématiciens et informaticiens Daniel Spielman et Shang-Hua Teng, puis Samuel Daitch, ont réussi à écrire des algorithmes qui ont également fourni une solution rapide et efficace au problème des flux à coût minimum. C’est ce groupe qui a orienté l’attention vers les flux d’énergie dans le réseau électrique.

Leur changement de perspective, du chemin de fer à l’électricité, a conduit à une distinction mathématique essentielle : si un train est dévié sur le réseau ferroviaire parce qu’une ligne est hors service, le meilleur itinéraire suivant selon l’horaire peut déjà être occupé par un autre train.

Dans le réseau électrique, il est possible que les électrons qui composent un flux d’énergie soient partiellement détournés vers une connexion réseau à travers laquelle circule déjà un autre courant. Ainsi, contrairement aux trains, le courant électrique peut, en termes mathématiques, être « partiellement » déplacé vers une nouvelle connexion.

Ce réacheminement partiel a permis à Spielman et à ses collègues de calculer ces changements d’itinéraire beaucoup plus rapidement et, en même temps, de recalculer l’ensemble du réseau après chaque changement. “Nous avons rejeté l’approche de Spielman consistant à créer les algorithmes les plus puissants possibles pour l’ensemble du réseau”, explique Kyng.

« Au lieu de cela, nous avons appliqué son idée de calcul d’itinéraire partiel aux approches antérieures de Hopcroft et Karp. » Ce calcul d’itinéraires partiels à chaque itération a joué un rôle majeur dans l’accélération du calcul global du flux.

Un tournant dans les principes théoriques

Une grande partie des progrès des chercheurs de l’ETH Zurich s’explique par la décision d’étendre leurs travaux au-delà du développement de nouveaux algorithmes. L’équipe utilise et conçoit également de nouveaux outils mathématiques qui accélèrent encore plus leurs algorithmes.

Ils ont notamment développé une nouvelle structure de données pour organiser les données réseau. Cela permet d’identifier très rapidement tout changement dans une connexion réseau. Et cela contribue à rendre la solution algorithmique étonnamment rapide.

Avec autant d’applications en ligne pour les algorithmes à temps quasi-linéaire et pour des outils tels que la nouvelle structure de données, la spirale globale de l’innovation pourrait bientôt tourner beaucoup plus vite qu’auparavant.

Cependant, poser les bases pour résoudre de très gros problèmes qui ne pouvaient auparavant pas être calculés efficacement n’est qu’un des avantages de ces algorithmes de flux nettement plus rapides, car ils modifient également la manière dont les ordinateurs calculent les tâches complexes en premier lieu.

« Au cours de la dernière décennie, il y a eu une révolution dans les fondements théoriques permettant d’obtenir des algorithmes rapides et démontrables pour les problèmes fondamentaux de l’informatique théorique », écrit un groupe international de chercheurs de l’Université de Californie à Berkeley, qui compte parmi ses membres Rasmus Kyng et Deeksha Adil, chercheur à l’Institut d’études théoriques de l’ETH Zurich.