Des chercheurs de l’ETH Zurich développent l’algorithme de flot le plus rapide possible

 (ethz.ch)
1 points par GN⁺ 2024-06-30 | 1 commentaires | Partager sur WhatsApp
  • L’équipe de recherche de Rasmus Kyng à l’ETH Zurich a développé un algorithme qui calcule le problème consistant à trouver le flot maximum dans un réseau et à minimiser les coûts de transport à une vitesse proche de la limite mathématique
  • Le nouvel algorithme adopte une approche en temps presque linéaire, produisant une réponse dans un temps presque comparable à celui nécessaire pour lire les données du réseau, et peut s’appliquer aux calculs sur des réseaux comme les chemins de fer, les routes, les voies navigables et Internet
  • Par le passé, si l’on note m le nombre de connexions, on en était jusqu’aux années 2000 à m^1.5, puis à m^1.33 en 2004, mais l’approche de Kyng réduit le temps de calcul supplémentaire après lecture des données à un niveau négligeable
  • L’équipe a étendu ses travaux au-delà des réseaux statiques et orientés à des graphes incrémentaux, où des connexions sont ajoutées, et à des graphes décrémentaux, où elles sont supprimées, tout en calculant les plus courts chemins et le flot maximum à coût minimal en temps presque linéaire
  • Cela jette les bases d’un recalcul rapide des itinéraires optimaux lorsque des réseaux réels changent, comme lors de la fermeture puis de la réouverture partielle du tunnel de base du Gothard, ou après un glissement de terrain sur l’autoroute A13

Calculer les problèmes de flot de réseau à une vitesse proche de la limite

  • L’algorithme de flot de réseau de l’équipe de Rasmus Kyng traite le problème consistant à trouver le flot maximal possible dans un réseau tout en minimisant les coûts de transport
  • Un exemple typique consiste à trouver l’itinéraire permettant d’acheminer le plus de marchandises possible de Copenhague à Milan, le plus vite et au moindre coût
  • Il permet de calculer un flot optimal à faible coût dans des réseaux dotés de connexions et de capacités, comme les chemins de fer, les routes, les voies navigables ou Internet
  • La vitesse de calcul a été réduite à un niveau presque équivalent au temps nécessaire à un ordinateur pour lire les données du réseau

Pourquoi parle-t-on de l’algorithme « le plus rapide »

  • Auparavant, le temps nécessaire pour calculer un flot optimal était bien plus long que celui requis pour traiter les données du réseau
  • Plus le réseau devenait vaste et complexe, plus le temps de calcul augmentait plus vite que la taille du problème
  • L’approche de Kyng fait en sorte que le temps de calcul et la taille du réseau augmentent dans la même proportion
    • Si l’on note m le nombre de connexions du réseau, la simple lecture des données demande déjà un temps de m
    • Jusqu’aux années 2000, il n’existait pas d’algorithme calculant plus vite que m^1.5
    • En 2004, la quantité de calcul nécessaire pour résoudre le problème a été ramenée à m^1.33
    • L’algorithme de Kyng abaisse ensuite à un niveau négligeable le temps de calcul supplémentaire nécessaire pour parvenir à la solution après lecture des données

Évaluation et extension des algorithmes en temps presque linéaire

  • L’équipe de Kyng a publié il y a deux ans un article présentant la preuve mathématique de ce concept
  • Un algorithme aussi rapide, presque optimal, est qualifié d’algorithme en temps presque linéaire
  • Daniel A. Spielman a comparé cet algorithme à une Porsche dépassant une calèche
  • L’article a reçu le Best Paper Award lors de l’IEEE Annual Symposium on Foundations of Computer Science, FOCS, en 2022
  • Communications of the ACM a également mis en lumière ces travaux, et la rédaction de Quanta a classé l’algorithme de Kyng parmi les 10 plus grandes découvertes en informatique de 2022

Des réseaux statiques aux réseaux qui évoluent

  • L’algorithme initial se concentrait sur des réseaux fixes et statiques à connexions orientées
    • Une connexion orientée correspond, par exemple, à une rue à sens unique dans un réseau routier urbain
  • Par la suite, l’équipe a développé des algorithmes permettant de calculer le flot optimal dans des réseaux qui évoluent progressivement au fil du temps
  • Simon Meierhans a présenté à Vancouver, lors de l’Annual ACM Symposium on Theory of Computing, STOC, un nouvel algorithme en temps presque linéaire
    • Cet algorithme résout le problème du flot maximum à coût minimal dans des réseaux où de nouvelles connexions sont ajoutées
  • Un second article, accepté à l’IEEE Symposium on Foundations of Computer Science, FOCS, d’octobre, présente un algorithme capable de traiter aussi la suppression de connexions
  • Les deux algorithmes identifient les plus courts chemins dans des réseaux où des connexions sont ajoutées ou supprimées

Exemples de changements dans des réseaux réels

  • En Suisse, le tunnel de base du Gothard a été totalement fermé à partir de l’été 2023, puis partiellement rouvert
  • Une partie de l’autoroute A13, principal itinéraire de remplacement du tunnel routier du Gothard, a récemment été détruite par un glissement de terrain
  • Lorsqu’un tel changement survient, les ordinateurs, les services de cartographie en ligne et les planificateurs d’itinéraires doivent recalculer la connexion la moins coûteuse et la plus courte entre Milan et Copenhague
  • Le nouvel algorithme de Kyng calcule des itinéraires optimaux en temps presque linéaire, même dans des réseaux où des connexions sont ajoutées ou supprimées
  • Même lorsqu’un détour ou un nouvel itinéraire ajoute des connexions, le temps de calcul supplémentaire reste négligeable

Les deux stratégies classiques et la nouvelle manière de les combiner

  • Le calcul de flot dans un réseau nécessite d’analyser le réseau à plusieurs reprises pour trouver le flot optimal et les chemins de coût minimal
  • À chaque itération, on examine des variantes comme les connexions ouvertes ou fermées, ou celles qui ont atteint leur capacité maximale et sont congestionnées
  • Avant Kyng, les informaticiens utilisaient principalement l’une de deux stratégies
    • Modèle du réseau ferroviaire : à chaque itération, on calcule une section entière du réseau dont le flux de trafic a changé
    • Modèle du réseau électrique : à chaque itération, on calcule l’ensemble du réseau, mais on accélère le calcul en utilisant des valeurs moyennes statistiques pour les flux modifiés sur chaque section
  • L’équipe de Kyng a réuni les avantages de ces deux stratégies dans une nouvelle approche combinée
  • Maximilian Probst Gutenberg estime qu’en combinant de nombreuses petites étapes de calcul efficaces et peu coûteuses, on va beaucoup plus vite qu’avec quelques grandes étapes

Contexte historique des algorithmes de flot

  • Le problème du flot de réseau a été l’un des premiers problèmes résolus de manière systématique par des algorithmes dans les années 1950
  • Les algorithmes de flot ont joué un rôle majeur dans l’émergence de l’informatique théorique comme champ de recherche indépendant
  • L’algorithme bien connu de Lester R. Ford Jr. et Delbert R. Fulkerson date également de cette période
  • L’algorithme de Ford-Fulkerson résout efficacement le problème du flot maximum, qui consiste à transporter autant de marchandises que possible dans un réseau sans dépasser la capacité de chaque chemin
  • Les travaux ultérieurs ont montré que le problème du flot maximum, le problème du coût minimal et plusieurs autres problèmes de flot de réseau sont des cas particuliers du problème général du flot à coût minimal

Les limites des algorithmes précédents et le tournant de 2004

  • Avant les travaux de Kyng, de nombreux algorithmes pouvaient résoudre efficacement un problème spécifique, mais ils n’étaient pas assez rapides et s’étendaient difficilement au problème plus général du flot à coût minimal
  • John Edward Hopcroft, Richard Manning Karp et Robert Endre Tarjan, auteurs d’algorithmes pionniers de flot dans les années 1970, ont chacun reçu le prix Turing
    • Karp l’a reçu en 1985
    • Hopcroft et Tarjan l’ont reçu en 1986
  • En 2004, Daniel Spielman, Shang-Hua Teng, puis Samuel Daitch ont conçu des algorithmes offrant aussi des solutions rapides et efficaces au problème du flot à coût minimal
  • Ce groupe a déplacé la perspective du réseau ferroviaire vers le flux électrique dans un réseau d’alimentation
  • Dans un réseau électrique, le flux de courant peut déjà être partiellement dévié vers des connexions où un autre courant circule
  • Kyng n’a pas repris telle quelle la puissante approche algorithmique de Spielman pour l’ensemble du réseau, mais a appliqué l’idée de calcul de chemins partiels à l’approche antérieure de Hopcroft et Karp
  • Le calcul de chemins partiels à chaque itération a fortement contribué à accélérer le calcul du flot global

Nouveaux outils mathématiques et structures de données

  • Les avancées de l’équipe de l’ETH Zurich reposent non seulement sur de nouveaux algorithmes, mais aussi sur la conception d’outils mathématiques qui accélèrent encore le calcul
  • L’équipe a développé une nouvelle structure de données pour organiser les données du réseau
  • Cette structure de données permet d’identifier très rapidement les changements dans les connexions du réseau
  • Cette détection rapide des changements contribue à accélérer la résolution algorithmique
  • Les algorithmes en temps presque linéaire et cette nouvelle structure de données ouvrent la voie à la résolution de problèmes très vastes qui ne pouvaient auparavant pas être calculés efficacement

Articles et ressources associés

À lire aussi

1 commentaires

 
GN⁺ 2024-06-30
Avis sur Hacker News

  • Cet algorithme est asymptotiquement presque linéaire dans la limite n -> inf
    À la fin de la vidéo, il est dit qu’il serait difficile pour n’importe quelle implémentation de cet algorithme de battre les algorithmes existants dans le monde réel
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • Encore un algorithme galactique, alors ?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • C’est assez décevant après toute l’attente créée au début
    • J’étais très sceptique dès que j’ai vu le titre
      L’expression vitesse la plus rapide possible est une affirmation vraiment audacieuse
    • Dans ce genre de cas, un autre indice est qu’il faut une solution quasiment absolument optimale
      Il est souvent bien plus pratique d’obtenir 99 % de qualité en n’utilisant que 1 % du temps

  • Fait intéressant, la même personne travaille aussi à rendre vraiment efficaces en pratique des algorithmes purement théoriques [1]
    Cela dit, le processus semble prendre encore une vingtaine d’années. [1] s’appuie sur une percée théorique de 2004 [2], et si j’ai bien compris, ces algorithmes n’ont commencé à fonctionner en pratique qu’en 2024. On peut donc peut-être espérer des algorithmes pratiques de flot à coût minimum en 2044
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    Passer de O(mn) à O(m), cela veut dire retirer N, c’est-à-dire le nombre de sommets, du calcul ; ce n’est pas trop beau pour être vrai ?

    • Les facteurs constants sont si grands que, sur des entrées réalistes, ce sera plus lent que les algorithmes existants asymptotiquement moins bons
      Mais cela reste un très beau résultat théorique

  • Les chiffres bruts montrent à eux seuls le chemin parcouru. Avant les années 2000, aucun algorithme ne pouvait calculer plus vite que m1.5. Ici, m désigne le nombre de connexions réseau que l’ordinateur doit traiter, et la simple lecture des données du réseau prend un temps m. En 2004, la vitesse de calcul nécessaire pour résoudre ce problème a été réduite à m1.33. Avec l’algorithme de Kyng, le temps de calcul « supplémentaire » nécessaire pour atteindre la solution après lecture des données du réseau devient désormais négligeable.
    L’article original n’explique pas la percée de Kyng sous l’angle de cette métrique m qu’il présente pourtant comme si importante ; je me demande pourquoi

  • Parfois, j’ai l’impression qu’on s’est complètement perdu en prenant la complexité comme métrique
    Il y a de plus en plus d’algorithmes qui optimisent les métriques de complexité à un niveau délirant, mais qui ne sont pas vraiment utiles en pratique

    • Ce phénomène existe depuis des décennies
      Une fois tous les résultats faciles épuisés, la recherche en algorithmique est devenue un autre domaine hautement spécialisé, et à moins d’être chercheur dans un domaine très proche, la plupart des articles ne valent pas vraiment le temps qu’on y consacre

  • Articles liés : https://news.ycombinator.com/item?id=31149038 (40 commentaires)
    https://news.ycombinator.com/item?id=31675015 (72 commentaires)

  • Où sont l’article ou le code ?

  • Il y a quelque chose qui me déroute ici : o(n) semble être une proposition plus forte que O(n)
    Tout algorithme en o(n) est en O(n), mais l’inverse n’est pas vrai. Et si o(n) s’applique même aux n aussi petits qu’on veut, tandis que O(n) ne s’applique que lorsque n -> inf, cet algorithme ne devrait-il pas être applicable aussi aux petits n ? Dans ce cas, ne devrait-ce pas être l’inverse de l’algorithme galactique mentionné plus haut ? Est-ce que je rate quelque chose ?

    • La notation petit o reste une proposition asymptotique, elle n’a donc pas besoin de s’appliquer aux petits n
      La définition de f(n) = o(g(n)) est, grosso modo, lim (n -> infinity) f(n)/g(n) = 0. Autrement dit, pour n suffisamment grand, g croît plus vite que f
      Par exemple, une fonction comme f(n) = 10n if n < 1000 else 1e1000 est en o(n). Quand n grandit, 1e1000/n tend vers 0. C’est une pseudo-expression Python d’une fonction par morceaux qui croît exponentiellement jusqu’à 101000 lorsque n = 1000, puis reste constante ensuite
    • Si la complexité d’un algorithme est 3↑↑64*n^0.999, alors cet algorithme est en o(n), mais on peut sans problème l’appeler un algorithme galactique

  • Si je me souviens bien, 3↑↑64 est le nombre de Graham

  • Maudits facteurs constants, ça me donne envie d’agiter le poing vers le ciel

  • Le résumé dit seulement que le temps est m^(1+o(1))
    Quelqu’un sait-il si une borne supérieure plus précise est donnée quelque part ?

    • Ici, o est le petit o, il capture donc un terme dont la « valeur divisée par 1 » tend vers 0 quand m tend vers l’infini
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • Cela signifie qu’on peut choisir les constantes de façon à se rapprocher autant qu’on veut de O(m)
      Autrement dit, c’est un schéma algorithmique permettant d’obtenir, pour tout ɛ>1, un algorithme s’exécutant en temps O(m^ɛ)
    • C’est précisément la borne supérieure concrète
      Le petit o est une fonction qui se rapproche de 0 quand n tend vers l’infini, et on dit qu’elle est asymptotiquement négligeable