Des 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 porte sur ce que l’on appelle un algorithme de flux de réseau, qui aborde la question de savoir comment obtenir le flux maximal 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 le plus de marchandises 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 de chemin de fer, de route, de voie navigable 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 à quel point nous avons progressé : jusqu’au tournant du millénaire, aucun algorithme n’a réussi à 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 nécessaire pour résoudre le problème a été réduite à m^1,33. Grâce à l’algorithme de Kyng, le temps de calcul « supplémentaire » requis pour atteindre la solution après la lecture des données du réseau est désormais négligeable.

Comme une Porsche faisant la course en calèche

Les chercheurs de l’ETH Zurich ont ainsi développé l’algorithme de flux de réseau le plus rapide possible en théorie. Il y a deux ans, Kyng et son équipe ont présenté la preuve mathématique de leur concept dans un article révolutionnaire. Les scientifiques qualifient ces nouveaux algorithmes, presque optimalement rapides, d’« algorithmes à temps quasi linéaire », et la communauté des informaticiens théoriciens a accueilli 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 de remporter le prix du meilleur article 2022 lors du Symposium annuel de l’IEEE sur les fondements de l’informatique (FOCS), leur article a également été mis en avant dans la revue informatique Communications de l’ACMet les rédacteurs du magazine scientifique populaire Quanta ont nommé l’algorithme de Kyng 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 à temps quasi linéaire. Le premier algorithme, par exemple, était encore axé sur des réseaux fixes et statiques 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 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 presque linéaire au Symposium annuel de l’ACM sur la théorie de l’informatique (STOC 2024) à Vancouver. Cet algorithme résout le problème du coût minimum et du débit maximum pour les réseaux qui changent progressivement à mesure que de nouvelles connexions sont ajoutées.

En outre, dans un deuxième article accepté par le Symposium de l’IEEE sur les fondements de l’informatique (FOCS) en octobre, les chercheurs de l’ETH ont développé un autre algorithme qui gère également la suppression des connexions.

Concrètement, 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 transport réels, de tels changements en Suisse incluent par exemple 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, principale voie alternative au 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 principales pour résoudre ce problème. L’une d’entre elles était calquée sur le réseau ferroviaire et impliquait de calculer 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’intégralité du réseau à chaque itération mais utilisait des valeurs moyennes statistiques pour le flux modifié de chaque section du réseau afin d’accélérer le calcul.

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.

C’est également à cette époque que date le célèbre algorithme 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 vise à déterminer comment transporter le plus de marchandises possible à travers un réseau sans dépasser la capacité des différentes voies.

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, et ne pouvaient pas non plus ê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 – et plus tard Samuel Daitch – ont réussi à écrire des algorithmes qui fournissaient également une solution rapide et efficace au problème du flux à coût minimum. C’est ce groupe qui a déplacé l’attention vers les flux d’énergie dans le réseau électrique.

Leur changement de perspective du ferroviaire vers l’électricité a conduit à une distinction mathématique clé : si un train est dérouté sur le réseau ferroviaire parce qu’une ligne est hors service, le prochain meilleur itinéraire 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 par 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

Les chercheurs de l’ETH Zurich ont en grande partie progressé grâce à leur 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 davantage leurs algorithmes.

Ils ont notamment développé une nouvelle structure de données pour organiser les données du réseau. Cela permet d’identifier extrêmement rapidement toute modification apportée à une connexion réseau. Et cela, à son tour, contribue à rendre la solution algorithmique incroyablement rapide.

Avec autant d’applications en attente pour les algorithmes à temps presque 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.

Pourtant, poser les bases de la résolution de très gros problèmes qui ne pouvaient pas être calculés efficacement auparavant n’est qu’un des avantages de ces algorithmes de flux beaucoup plus rapides, car ils modifient également la manière dont les ordinateurs calculent des 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 dont la rapidité a été prouvée pour résoudre des problèmes fondamentaux en informatique théorique”, écrit un groupe international de chercheurs de l’Université de Californie à Berkeley, qui comprend parmi ses membres Rasmus Kyng et Deeksha Adil, chercheuse à l’Institut d’études théoriques de l’ETH Zurich.