Des chercheurs s'approchent d'une nouvelle limite de vitesse pour le problème séminal | Magazine Quanta

Le problème du voyageur de commerce est l’une des plus anciennes questions informatiques connues. Il demande l'itinéraire idéal à travers une certaine liste de villes, en minimisant le kilométrage. Bien qu’il semble simple, le problème est notoirement difficile. Bien que vous puissiez utiliser la force brute pour vérifier tous les itinéraires possibles jusqu'à trouver le chemin le plus court, une telle stratégie devient intenable après seulement une poignée de villes. Au lieu de cela, vous pouvez appliquer un modèle mathématique rigoureux appelé programmation linéaire, qui se rapproche approximativement du problème sous la forme d'un ensemble d'équations et vérifie méthodiquement les combinaisons possibles pour trouver la meilleure solution.

Mais parfois, vous devez optimiser les problèmes impliquant des montants entiers. À quoi sert un plan d’optimisation d’une usine qui fabrique 500.7 canapés ? Pour cela, les chercheurs se tournent souvent vers une variante de programmation linéaire appelée programmation linéaire en nombres entiers (ILP). Il est populaire dans les applications qui impliquent des décisions discrètes, notamment la planification de la production, la planification des équipages des compagnies aériennes et l'itinéraire des véhicules. "Fondamentalement, l'ILP est le pain et le beurre de la recherche opérationnelle, tant en théorie que en pratique", a déclaré Santosh Vempala, informaticien au Georgia Institute of Technology.

Depuis qu'ils ont formulé pour la première fois l'ILP il y a plus de 60 ans, les chercheurs ont découvert divers algorithmes permettant de résoudre les problèmes ILP, mais ils ont tous été relativement lents en termes de nombre d'étapes requises. La meilleure version qu'ils pourraient proposer – une sorte de limite de vitesse – vient du cas trivial où les variables du problème (comme la visite ou non d'un vendeur dans une ville) ne peuvent prendre que des valeurs binaires (zéro ou 1). Dans ce cas, ILP a un temps d'exécution qui évolue de façon exponentielle avec le nombre de variables, également appelé dimension. (S'il n'y a qu'une seule variable, il suffit de deux étapes pour tester toutes les combinaisons possibles et résoudre le problème ; deux variables signifient quatre étapes, trois signifient huit étapes, et ainsi de suite.)

Malheureusement, une fois que les variables prennent une valeur supérieure à zéro et 1, la durée d'exécution de l'algorithme s'allonge beaucoup plus. Les chercheurs se demandent depuis longtemps s’ils pourraient se rapprocher de cet idéal trivial. Les progrès ont été lents, avec le record se déroulant dans les années 1980 et seulement progressif améliorations fait depuis.

Mais récente travail by Victor Reis, actuellement à l'Institute for Advanced Study, et Thomas Rothvoss, à l'Université de Washington, a réalisé le plus grand bond en termes d'exécution depuis des décennies. En combinant des outils géométriques pour limiter les solutions possibles, ils ont créé un nouvel algorithme plus rapide pour résoudre l'ILP presque en même temps que le cas binaire trivial. Le résultat a reçu le prix du meilleur article au salon 2023 Fondements de l'informatique conférence.

"Ce nouvel algorithme est extrêmement excitant", a déclaré Noah Stephens-Davidowitz, mathématicien et informaticien à l'Université Cornell. "Cela représente la première amélioration [majeure] des solveurs ILP depuis près de 40 ans."

ILP fonctionne en transformant un problème donné en un ensemble d'équations linéaires qui doivent satisfaire certaines inégalités. Les équations spécifiques sont basées sur les détails du problème d'origine. Mais même si ces détails peuvent différer, la composition fondamentale des problèmes ILP reste la même, offrant aux chercheurs un moyen unique d’aborder une multitude de problèmes.

Cela ne veut pas dire que c'est un travail facile. Ce n'est qu'en 1983 que le mathématicien Hendrik Lenstra prouvé que le problème général était même résoluble, en fournissant le premier algorithme capable de le faire. Lenstra a pensé l'ILP de manière géométrique. Premièrement, il a transformé les inégalités au cœur de l’ILP en une forme convexe, comme n’importe quel polygone régulier. Cette forme représente les contraintes du problème individuel que vous résolvez, qu'il s'agisse de la production de canapés ou de la planification d'une compagnie aérienne. L'intérieur de la forme correspond donc à toutes les valeurs possibles qui pourraient résoudre les inégalités, et donc le problème. Lenstra a appelé cette forme le corps convexe. La dimension du problème influence la dimension de cette forme : à deux variables elle prend la forme d'un polygone plat ; en trois dimensions c'est un Solide platonicien, Et ainsi de suite.

Lenstra a ensuite imaginé tous les entiers comme un ensemble infini de points de grille, connu en mathématiques sous le nom de treillis. Une version bidimensionnelle ressemble à une mer de points, et en trois dimensions, elle ressemble aux points de connexion des poutres en acier d'un bâtiment. La dimension du réseau dépend également de la dimension d'un problème donné.

Pour résoudre un problème ILP donné, Lenstra a montré qu'il suffit de rechercher l'endroit où les solutions possibles rencontrent l'ensemble des entiers : à l'intersection du corps convexe et du réseau. Et il a mis au point un algorithme capable de rechercher cet espace de manière exhaustive – mais pour être efficace, il devait parfois diviser le problème en morceaux de dimensions plus petites, ajoutant de nombreuses étapes au runtime.

Au cours des années suivantes, plusieurs chercheurs ont exploré comment rendre cet algorithme plus rapide. En 1988, Ravi Kannan et László Lovász ont introduit un concept appelé rayon de couverture, emprunté de l'étude de codes correcteurs d'erreurs, pour aider le corps convexe et le réseau à se croiser plus efficacement. En gros, le rayon de couverture garantit que le corps convexe contient toujours au moins un point entier, quel que soit l'endroit où vous le placez sur le réseau. En conséquence, la taille du rayon de couverture détermine également l’efficacité avec laquelle vous pouvez résoudre le problème ILP.

Tout se résumait donc à déterminer la taille du rayon de couverture idéal. Malheureusement, cela s'est avéré être un problème difficile en soi, et le mieux que Kannan et Lovász aient pu faire a été de affiner une valeur possible en recherchant des limites supérieures et inférieures. Ils ont montré que la limite supérieure – la taille maximale du rayon de couverture – augmentait linéairement avec la dimension. C'était assez rapide, mais pas suffisant pour accélérer considérablement le temps d'exécution ILP. Au cours des 30 prochaines années, d’autres chercheurs n’ont pu faire que légèrement mieux.

Ce qui a finalement aidé Reis et Rothvoss à percer, c'est un résultat mathématique sans rapport et axé uniquement sur les réseaux. En 2016, Oded Regev et Stephens-Davidowitz montré, en fait, combien de points du réseau pourraient tenir dans une forme spécifique. Reis et Rothvoss ont appliqué cela à d'autres formes, ce qui leur a permis de mieux estimer le nombre de points de réseau contenus dans un rayon de couverture ILP, abaissant ainsi la limite supérieure. "La dernière avancée majeure est venue avec la prise de conscience qu'il était possible de créer d'autres types de formes", a déclaré Regev.

Cette nouvelle limite supérieure resserrée constituait une amélioration considérable, permettant à Reis et Rothvoss d’accélérer considérablement l’algorithme ILP global. Leur travail amène le temps d'exécution à (log n)^O(n), Où n est le nombre de variables et O (n)signifie qu'il évolue linéairement avec n. (Cette expression est considérée comme « presque » identique au temps d’exécution du problème binaire.)

"C'est un triomphe à l'intersection des mathématiques, de l'informatique et de la géométrie", a déclaré Daniel Dadush de l'institut national de recherche CWI aux Pays-Bas, qui a contribué à la création de l'algorithme utilisé par Reis et Rothvoss pour mesurer le temps d'exécution de l'ILP.

Pour l'instant, le nouvel algorithme n'a pas été utilisé pour résoudre des problèmes logistiques, car il faudrait trop de travail pour mettre à jour les programmes actuels pour l'utiliser. Mais pour Rothvoss, ce n’est pas la question. « Il s'agit de la compréhension théorique d'un problème qui a des applications fondamentales », a-t-il déclaré.

Quant à savoir si l'efficacité informatique de l'ILP pourrait être encore améliorée, les chercheurs espèrent toujours qu'ils continueront à se rapprocher de la durée d'exécution idéale, mais pas de si tôt. "Cela nécessiterait une idée fondamentalement nouvelle", a déclaré Vempala.