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

Dans une percée qui rappelle Lucky Luke - l'homme qui tire plus vite que son ombre - Rasmus Kyng et son équipe ont mis au point un algorithme ultrarapide qui semble prêt à transformer tout un domaine de recherche. Les travaux novateurs de l'équipe de Rasmus Kyng portent sur ce que l'on appelle un algorithme de flux de réseau, qui s'attaque à la question de savoir comment obtenir un flux 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 recherchiez l'itinéraire le plus rapide et le moins cher pour transporter le plus grand nombre de marchandises possible de Copenhague à Milan. L'algorithme de Rasmus Kyng peut être appliqué dans de tels cas pour calculer le flux de trafic optimal et le moins coûteux pour n'importe quel type de réseau, qu'il soit ferroviaire, routier, fluvial ou 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 Rasmus Kyng, personne n'y était parvenu, bien que les scientifiques travaillent sur ce problème depuis environ 90 ans. Auparavant, il fallait beaucoup plus de temps pour calculer le flux optimal que pour traiter les données du réseau. Et au fur et à mesure que le réseau devenait plus grand et plus complexe, le temps de calcul nécessaire augmentait beaucoup plus vite, comparativement, que la taille réelle du problème de calcul. 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 Rasmus Kyng élimine ce problème : avec son algorithme, le temps de calcul et la taille du réseau augmentent au même rythme - un peu comme si l'on faisait une randonnée et que l'on gardait toujours le même rythme, même si le chemin est escarpé. Un coup d'œil aux chiffres bruts montre à quel point nous avons progressé : 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 d'un réseau que l'ordinateur doit calculer, et où le simple fait de lire une fois les données du réseau prend m de temps. En 2004, la vitesse de calcul requise pour résoudre le problème a été ramenée à m^1.33. En utilisant l'algorithme de Rasmus Kyng, le temps de calcul supplémentaire nécessaire pour atteindre la solution après avoir lu les données du réseau est désormais négligeable.

Comme une Porsche faisant la course avec une voiture hippomobile

Les scientifiques 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, Rasmus Kyng et son équipe ont présenté la preuve mathématique de leur concept dans un article révolutionnaire. Les scientifiques appellent ces nouveaux algorithmes d'une rapidité presque optimale des «algorithmes à temps quasi-linéaire», et la communauté des informaticiens et informaticiemmes théoriques a réagi à la percée de Rasmus Kyng avec un mélange d'étonnement et d'enthousiasme.

Le directeur de thèse de Rasmus 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 voitures à cheval. En plus d'avoir remporté le prix du meilleur article en 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 of the ACM, et le magazine scientifique Quanta a désigné l'algorithme de Rasmus Kyng comme l'une des dix plus grandes découvertes de l'informatique en 2022.

Les chercheurs et chercheuses 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, ce qui signifie 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 les flux optimaux pour des réseaux qui évoluent progressivement dans le temps. Le calcul rapide comme l'éclair est une étape importante pour aborder les réseaux très complexes et riches en données qui changent dynamiquement et très rapidement, tels que les molécules ou le cerveau en biologie, ou encore les amitiés humaines.

Des algorithmes rapides comme l'éclair pour des réseaux en mutation

Simon Meierhans, membre de l'équipe de Simon Kyng, a présenté un nouvel algorithme en temps quasi-linéaire lors du symposium annuel de l'ACM sur la théorie de l'informatique (STOC) à Vancouver. Cet algorithme résout le problème du flux maximal à coût minimal pour les réseaux qui changent progressivement au fur et à mesure que de nouvelles connexions sont ajoutées. En outre, dans un second article accepté par l'IEEE Symposium on Foundations of Computer Science (FOCS) en octobre, les chercheurs et chercheuses de l'ETH Zurich ont développé un autre algorithme qui gère également la suppression de connexions.

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 trafic réels, les exemples de tels changements en Suisse comprennent 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 est le principal itinéraire alternatif 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 peut-il calculer la liaison la moins chère et la plus rapide entre Milan et Copenhague ? Les nouveaux algorithmes de Rasmus Kyng calculent également l'itinéraire optimal pour ces réseaux qui changent de manière incrémentielle ou décrémentielle en un temps presque linéaire - si rapidement que le temps de calcul pour chaque nouvelle connexion, qu'elle soit ajoutée par un réacheminement ou par la création de nouveaux itinéraires, est à nouveau négligeable.

Mais qu'est-ce qui rend l'approche de Rasmus Kyng tellement plus rapide que n'importe quel autre algorithme de flux de 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 à coût minimal. Ce faisant, elles passent par chacune des différentes variantes de connexions 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'entre elles s'inspirait du réseau ferroviaire et consistait à calculer une section entière du réseau avec un flux de trafic modifié à chaque itération. La seconde stratégie, inspirée par les 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 d'accélérer le calcul.

L'équipe de Rasmus Kyng a maintenant réuni les avantages respectifs de ces deux stratégies pour 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 beaucoup plus rapides que quelques grandes», explique Maximilian Probst Gutenberg, maître de conférences et membre du groupe de Rasmus Kyng, qui a joué un rôle clé dans le développement des algorithmes en temps quasi-linéaire.

Un bref regard sur l'histoire de cette discipline ajoute une dimension supplémentaire à l'importance de la percée de Rasmus 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 en tant que domaine de recherche à part entière. L'algorithme bien connu développé par les mathématiciens Lester R. Ford Jr. et Delbert R. Fulkerson date également de cette période. 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 avancées ont montré aux chercheuses et chercheurs que le problème du flux maximal, le problème du coût minimal (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 minimal. Avant les recherches de Rasmus Kyng, la plupart des algorithmes n'étaient capables de résoudre efficacement qu'un seul de ces problèmes, même si cela n'était pas particulièrement rapide, et ne pouvaient pas ê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éoriques John Edward Hopcroft, Richard Manning Karp et Robert Endre Tarjan ont chacun reçu un prix Turing, considéré comme le prix Nobel de l'informatique. Richard Manning Karp a reçu le sien en 1985 ; John Edward Hopcroft et Robert Endre Tarjan ont reçu le leur en 1986.

Changement de perspective des chemins de fer vers 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 minimal. C'est ce groupe qui a déplacé l'attention vers les flux d'énergie dans le réseau électrique. Leur changement de perspective, des chemins de fer à l'électricité, a conduit à une distinction mathématique essentielle : si un train est réacheminé 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 de courant soient partiellement détournés vers une connexion de réseau par laquelle un autre courant circule déjà. 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 à Daniel Spielman et à ses collègues de calculer ces changements d'itinéraires 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 Daniel Spielman qui consistait à créer les algorithmes les plus puissants possibles pour l'ensemble du réseau», explique Rasmus Kyng. «Nous avons plutôt appliqué son idée de calcul d'itinéraires partiels aux approches antérieures de John Edward Hopcroft et Richard Manning Karp.» Ce calcul d'itinéraires partiels à chaque itération a joué un rôle majeur dans l'accélération du calcul du flux global.

Un tournant dans les principes théoriques

Une grande partie des progrès réalisés par les scientifiques de l'ETH Zurich est due à la décision d'étendre leur travail 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 et elles ont notamment développé une nouvelle structure de données pour organiser les données de réseau, ce qui permet d'identifier très rapidement toute modification d'une connexion de réseau, ce qui contribue à rendre la solution algorithmique étonnamment rapide. Avec autant d'applications prévues 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 pourrait bientôt tourner beaucoup plus vite qu'auparavant.

Pourtant, jeter 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 nettement plus rapides, car ils modifient également la façon dont les ordinateurs calculent les tâches complexes en premier lieu. «Au cours de la dernière décennie, on a assisté à une révolution dans les fondements théoriques permettant d'obtenir des algorithmes manifestement rapides pour les problèmes fondamentaux de l'informatique théorique», écrit un groupe de recherche international de l'Université de Californie à Berkeley, qui compte parmi ses membres Rasmus Kyng et Deeksha Adil, chercheuse à l'Institut d'études théoriques de l'ETH Zurich.