Résumé Technique : Relaxation Analytique en Temps Polynomial du Problème du Voyageur de Commerce

Énoncé du Problème

Le Problème du Voyageur de Commerce (TSP - Travelling Salesman Problem) est identifié comme un défi d'optimisation combinatoire canonique de classe NP-difficile. Les solutions exactes traditionnelles, telles que la Programmation Linéaire en Nombres Entiers (ILP) et l'algorithme de programmation dynamique de Held-Karp, nécessitent l'évaluation de l'espace des cycles hamiltoniens d'un graphe pondéré. Ces méthodes sont limitées par des complexités computationnelles factorielles $O(N!)$ ou exponentielles $O(N^2 2^N)$, ce qui les rend impraticables pour des applications réelles impliquant des instances de problème dont $N > 25$.

Méthodologie

L'article propose un nouveau cadre analytique continu qui projette les espaces de permutations discrets sur une variété de tenseurs de flux de probabilité continue. Plutôt que de traverser des arbres de recherche discrets, la méthode reformule la tâche d'optimisation en un problème de propagation de tenseurs algébriques. L'approche est régie par trois postulats fondamentaux :

1. Plongement dans une Variété Continue : Les permutations discrètes sont plongées dans un espace de tenseurs de flux de probabilité continue $P \in \mathbb{R}^{N \times N}$. Les probabilités de transition sont définies par des lois de puissance inverses des gradients de coût des arêtes, où la probabilité $P_{ij}$ est inversement proportionnelle aux gradients de poids des arêtes élevés à un paramètre d'échelle $\alpha$.
2. Normalisation Cumulative et Transcendantale Dépendante de l'Historique : Pour imposer les contraintes hamiltoniennes sans masquage exponentiel de sous-ensembles, les probabilités de chemin sont pondérées dynamiquement. L'article introduit trois formulations analytiques :
   • Approche 1 (Flux de Probabilité Standard) : Évalue les transitions en fonction du ratio entre la probabilité et le coût de l'arête.
   • Approche 2 (Heuristique Pi-Exponentielle) : Applique une mise à l'échelle transcendantale utilisant $\pi$ aux valeurs de probabilité.
   • Approche 3 (Relaxation HK Transcendantale) : Utilise un facteur de tableau précalculé statique $\gamma(N) = \pi^{(N^2 / 2^N)}$.
3. Troncation de la Série Spectrale : Le permanent intraçable des couvertures de cycles est approximé par des expansions de séries de Maclaurin tronquées de la fonction génératrice exponentielle de matrice $e^{tW}$. Cela réduit l'extraction de coefficients à des limites de multiplication de matrices polynomiales, spécifiquement $O(N)$.

L'algorithme résultant opère en trois phases : Initialisation du Tenseur, Construction du Tenseur de Transition et Propagation d'État Séquentielle. Il exécute $N$ étapes pour évaluer les nœuds non visités, sélectionnant le score coût-probabilité minimal, atteignant un temps d'exécution déterministe strict de $O(N^3)$.

Contributions Clés

• Changement Algorithmique : Un algorithme déterministe qui contourne l'énumération exponentielle de sous-ensembles en utilisant des matrices stochastiques, des facteurs d'échelle transcendantaux et des approximations de séries de Maclaurin tronquées.
• Réduction de la Complexité : Réduction théorique de la génération de tours TSP d'un temps exponentiel à un temps polynomial strict de $O(N^3)$.
• Implémentation : Fourniture d'implémentations de code en Python (NumPy) et Java, démontrant la faisabilité de l'approche de propagation de tenseurs.
• Scalabilité : Démonstration d'une scalabilité stable pour les topologies de graphes à l'échelle de l'entreprise, les temps d'exécution restant faibles même lorsque $N$ augmente.

Résultats

L'article présente des résultats de benchmark complets pour des tailles de problèmes allant de $N = 1$ à $100$, comparant les approches analytiques proposées aux bases de référence exactes de Held-Karp.

• Temps d'Exécution : La méthode proposée en $O(N^3)$ démontre des temps d'exécution nettement plus rapides que Held-Karp. Pour $N=20$, la méthode proposée prend 0,205 ms, tandis que Held-Karp nécessite 870 000 ms. Pour $N=100$, la méthode proposée se termine en 15,80 ms, alors que Held-Karp est noté comme nécessitant des recherches dans des "Tableaux Statiques" (impliquant que la méthode exponentielle est infaisable).
• Qualité de la Solution : Les coûts de parcours générés par les approches proposées sont rapportés comme étant en alignement empirique avec les bases de référence optimales connues.
  • Approche 1 et Approche 3 : Ces méthodes produisent des coûts identiques à la base de référence exacte de Held-Karp sur toutes les instances testées ($N=1$ à $100$).
  • Approche 2 : Cette méthode présente des écarts mineurs (par exemple, pour $N=6$, le coût est de 399,10 contre 398,50 pour l'exact), mais reste proche de la base de référence optimale.
• Scalabilité à Grande Échelle : L'article inclut des projections pour des graphes ultra-larges allant jusqu'à $N=10\,000$. Il estime que pour $N=10\,000$, l'algorithme nécessiterait environ $1,00 \times 10^{12}$ FLOPs, 800 Mo de mémoire, et un temps d'exécution d'environ 15,80 minutes.

Signification et Revendications

L'article affirme qu'en recadrant l'optimisation combinatoire à travers des tenseurs algébriques continus, des mises à l'échelle transcendantales et des approximations de séries polynomiales, la génération de tours TSP peut être exécutée de manière déterministe en temps polynomial. L'auteur soutient que ce cadre permet de contourner l'énumération exponentielle de sous-ensembles tout en maintenant un alignement empirique avec les solutions optimales.

La signification de ce travail est présentée comme une solution potentielle aux limitations de scalabilité des solveurs TSP actuels, permettant de traiter des topologies de graphes à l'échelle de l'entreprise qui étaient auparavant restreintes à de petites instances. L'article conclut en notant que les travaux futurs exploreront l'accélération matérielle via les cœurs de tenseurs GPU pour optimiser davantage les performances pour les instances de graphes creux massives ($N > 10\,000$).