Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Cet article présente une formulation par réseaux de tenseurs pour le problème du voyageur de commerce et ses variantes, qui utilise des couches pondérées par Boltzmann et des filtres de comptage pour identifier les tournées optimales selon une règle marginale séquentielle, servant d'heuristique pour des applications industrielles à petite échelle plutôt que d'alternative supérieure aux solveurs classiques spécialisés.

L'essentiel

La Vue d'Ensemble : Résoudre l'Énigme du « Voyageur de Commerce » avec un Nouveau Type de Calculateur

Imaginez que vous êtes un voyageur de commerce. Vous avez une carte avec 10, 20, voire 100 villes. Vous devez visiter chaque ville exactement une fois et revenir chez vous, mais vous souhaitez le faire en parcourant la distance la plus courte possible pour économiser du carburant et du temps. C'est le célèbre Problème du Voyageur de Commerce (TSP).

Le problème est que, à mesure que vous ajoutez des villes, le nombre de routes possibles explose. C'est comme essayer de trouver la clé parfaite dans un tas de clés qui grandit si vite que vérifier chacune d'elles prendrait plus de temps que l'âge de l'univers. C'est pourquoi les ordinateurs peinent à le résoudre.

Cet article présente une nouvelle façon d'aborder ce problème en utilisant des Réseaux de Tenseurs. Imaginez un Réseau de Tenseurs non pas comme un programme informatique, mais comme un système de filtres géant et multicouche.

L'Analogie : Le Tamis à « Poudre d'Or »

Imaginez que vous avez un immense sac de sable mélangé à de la poudre d'or.

• Le Sable : Représente toutes les mauvaises, longues et inefficaces routes.
• L'Or : Représente la route parfaite et la plus courte.
• L'Objectif : Vous voulez séparer l'or du sable sans examiner chaque grain individuellement.

Les auteurs ont construit une machine (le Réseau de Tenseurs) pour faire cela :

1. Le Mélange Initial (La Superposition) : D'abord, la machine crée une « superposition ». Imaginez qu'elle crée magiquement une copie de chaque route possible en même temps. C'est comme avoir un million de versions différentes de vous-même, chacune empruntant un chemin différent.
2. Le Pondération (La Chaleur) : Ensuite, la machine applique une « température » (appelée $\tau$). Imaginez cela comme un lampadaire chauffant.
   • Les routes longues et inefficaces (le sable) chauffent et se transforment en lumière, s'estompant ainsi.
   • Les routes courtes et efficaces (l'or) restent fraîches et lourdes.
   • La machine utilise des mathématiques (facteurs de Boltzmann) pour faire disparaître les mauvaises routes plus rapidement que les bonnes.
3. Les Filtres (Les Règles) : C'est la partie la plus importante. Vous ne pouvez pas avoir n'importe quelle route ; vous ne pouvez pas visiter la même ville deux fois. Les auteurs ont construit des Filtres de Comptage spéciaux.
   • Imaginez un gardien de sécurité à chaque ville. Si un voyageur tente de visiter une ville où il est déjà allé, le gardien claque la porte sur cette route spécifique.
   • Ces filtres sont « épars », ce qui signifie qu'ils sont très efficaces pour bloquer les mauvais chemins sans avoir besoin de vérifier manuellement chaque possibilité.
4. Le Résultat (La Marginale) : Après avoir traversé la chaleur et les filtres, la machine comprime tout. Elle demande : « Si je regarde la première ville, laquelle a le plus de chances de faire partie de la route gagnante ? » Elle sélectionne celle-ci, la verrouille, puis répète le processus pour la deuxième ville, et ainsi de suite, jusqu'à ce que toute la route soit construite.

Ce Qu'ils Ont Réellement Fait (Les Expériences)

Les auteurs n'ont pas prétendu que cette méthode est une solution miracle qui résout tous les problèmes instantanément. Ils ont été très honnêtes sur ses limites.

• Petits Tests : Ils ont testé leur méthode sur de petites cartes (de 5 à 12 villes).
• Calibration : Ils ont découvert que le réglage de la « température » ($\tau$) est crucial. S'il est trop bas, les mauvaises routes ne s'estompent pas suffisamment. S'il est trop haut, l'ordinateur se perd dans de minuscules erreurs mathématiques. Ils ont dû régler soigneusement ce paramètre pour chaque taille de carte.
• Les Résultats :
  • Lorsqu'ils ont réglé les paramètres parfaitement, leur méthode trouvait la route parfaite environ 95 % du temps sur ces petites cartes.
  • Lorsqu'ils l'ont comparée aux méthodes informatiques standard (comme « Greedy » ou « Recuit Simulé »), leur méthode était souvent meilleure pour trouver la route parfaite.
  • Cependant, ils ont admis que pour des cartes très grandes, les mathématiques deviennent toujours trop lourdes (complexité exponentielle), tout comme les anciennes méthodes. Ce n'est pas un miracle de « temps polynomial » ; c'est simplement une façon différente et très structurée de faire les mathématiques.

Test Réel : Le Problème de Réaffectation des Emplois

Pour voir si cela fonctionne en dehors de la théorie, ils l'ont appliqué à un problème industriel réel pour ONCE (une organisation espagnole pour les aveugles).

• Le Problème : Ils avaient des travailleurs affectés à des emplois et certains emplois vacants. Ils devaient déterminer si le déplacement d'un travailleur vers un nouvel emploi rendrait l'ensemble de l'équipe plus productive.
• La Surprise : Ce n'est pas exactement un problème de « voyage », mais c'est similaire : vous devez attribuer des emplois uniques à des personnes uniques sans double réservation.
• Le Résultat : Ils ont comparé leur méthode de Réseau de Tenseurs à deux autres outils puissants (un recuiseur quantique et un recuiseur numérique).
  • Les résultats étaient identiques en termes de gain total de productivité.
  • Les seules différences concernaient des situations de « départage » où deux options étaient mathématiquement égales ; les machines en choisissaient simplement une au hasard.
  • Conclusion : Cela a prouvé que leur méthode fonctionne dans le monde réel et peut être intégrée dans des logiciels industriels, même si elle ne bat pas les outils spécialisés pour cette tâche spécifique.

Le Fond du Problème

L'article présente une nouvelle boîte à outils mathématique pour résoudre des énigmes de routage et d'affectation.

• Le Bon : Elle offre un moyen très clair et modulaire de gérer des règles complexes (comme « ne pas visiter la même ville deux fois ») et peut trouver des solutions parfaites sur de petits problèmes. C'est comme avoir un assistant très organisé, respectueux des règles, qui ne se fatigue jamais de vérifier les contraintes.
• Le Mauvais : Elle ne rend pas magiquement les énormes problèmes faciles. Les mathématiques deviennent toujours exponentiellement plus difficiles à mesure que le problème grandit. Elle nécessite un réglage soigneux (calibration) pour bien fonctionner.
• L'Essentiel : C'est une nouvelle façon puissante de penser à ces problèmes et un outil solide pour des tâches industrielles spécifiques et à petite échelle, mais ce n'est pas encore un remplacement pour tous les solveurs ultra-rapides existants.

En bref : Ils ont construit un tamis sophistiqué capable de filtrer les mauvaises routes et de trouver la meilleure, mais vous devez toujours lui fournir les bons réglages pour obtenir l'or.

Résumé technique

Résumé technique : Formulation par réseaux de tenseurs du problème du voyageur de commerce et de ses variantes

Définition du problème
L'article traite du problème du voyageur de commerce (TSP) et de plusieurs de ses généralisations, notamment le TSP dépendant du temps (TDTSP), le problème de réaffectation des tâches (JRP), et des variantes impliquant des contraintes de non-répétition, des règles de précédence, des contraintes de groupe et des objectifs de goulot d'étranglement. Le TSP est défini comme la recherche du plus court itinéraire visitant $N$ nœuds exactement une fois et revenant au point de départ, un problème connu pour être NP-difficile. Bien que des algorithmes exacts tels que Held-Karp ($O(N^2 2^N)$) et la méthode par séparation et évaluation existent, ils font face à une complexité exponentielle qui limite leur évolutivité pour les cas industriels. À l'inverse, les heuristiques (par exemple, algorithmes génétiques, recherche locale) offrent des solutions approximatives sans garanties d'optimalité. Les auteurs notent que les algorithmes quantiques émergents (QAOA, VQE) sont actuellement limités par le bruit matériel (ère NISQ), ce qui motive l'exploration de techniques classiques imitant les propriétés des systèmes quantiques.

Méthodologie
La contribution principale est une formulation par réseaux de tenseurs (TN) qui représente les itinéraires candidats comme des états dans un espace produit tensoriel. La méthode opère via trois mécanismes principaux :

1. Construction du réseau de tenseurs :

   • Initialisation ('+') : Crée une superposition uniforme de toutes les affectations de nœuds possibles pour chaque étape temporelle.
   • Optimisation ('S') : Applique un opérateur d'évolution en temps imaginaire $U = e^{-\tau C(\vec{y})}$, où $\tau$ est un facteur d'amortissement et $C(\vec{y})$ est le coût de l'itinéraire. Cela supprime exponentiellement les configurations à coût élevé, analogue à la recherche de l'état fondamental dans les systèmes quantiques.
   • Filtrage des contraintes ('F') : Introduit des couches d'opérateurs produit matriciel (MPO) pour imposer les contraintes. Pour le TSP standard, ces couches agissent comme des filtres de comptage assurant que chaque nœud apparaît exactement une fois. Les filtres utilisent des indices de liaison binaires pour suivre si un nœud spécifique a été visité, implémentant efficacement la contrainte du symbole de Levi-Civita $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$.
   • Extraction ('+') : Une couche de trace somme les amplitudes pour produire des poids marginaux.

2. Extraction marginale séquentielle :
   La solution est extraite de manière itérative. Pour un préfixe fixe de l'itinéraire, l'algorithme calcule le poids marginal $Z_p(a; \tau)$ pour chaque nœud candidat $a$ à la position suivante. Dans la limite de $\tau \to \infty$ et d'une arithmétique exacte, le nœud maximisant ce poids est garanti faire partie d'un itinéraire optimal (Proposition 3.2). L'algorithme sélectionne le nœud maximisant, met à jour le préfixe et répète l'opération jusqu'à ce que l'itinéraire soit complet.

3. Généralisations :
   Le cadre est adapté à diverses variantes du TSP en modifiant les couches de filtrage et d'évolution :

   • DNSNN (Nombre différent d'étapes/nœuds) : Les filtres permettent aux nœuds d'apparaître entre $N^0$ et $N^f$ fois.
   • NMTSP (Non-Markovien) : Utilise des MPO d'ordre supérieur pour gérer des coûts dépendant des $K$ étapes précédentes.
   • BTSP (Goulot d'étranglement) : Remplace l'évolution du coût par une couche suivant le coût d'arête maximal rencontré.
   • PTSP (Contraintes de groupe) : Les filtres imposent la visite d'exactement un nœud par classe.
   • TSPP (Précédence) : Des projecteurs locaux suppriment les nœuds si leurs prédécesseurs requis n'ont pas encore apparu.
   • JRP (Réaffectation des tâches) : Modélisé comme un problème d'affectation linéaire où un état « sans mouvement » est répétable, et des vacances spécifiques sont uniques.

4. Approximation et complexité :
   La contraction exacte du réseau de tenseurs complet est exponentielle, évoluant comme $O(\hat{N}^4 2^{\hat{N}})$ pour une contraction dense couche par couche. Pour traiter des instances plus grandes, les auteurs proposent :

   • Ablation de couches : Appliquer uniquement un sous-ensemble de couches de contraintes pour réduire la complexité, traitant le résultat comme une heuristique.
   • Contraction locale sparse : Exploiter la nature déterministe et sparse des tenseurs de filtre locaux pour réduire les facteurs prédictifs polynomiaux (par exemple, de $O(\hat{N}^4 2^{\hat{N}})$ à $O(\hat{N}^3 2^{\hat{N}})$) sans changer l'échelle exponentielle.
   • Heuristique à $\tau$ fini : Utiliser une précision finie et un $\tau$ fini pour approximer la limite de température zéro, reconnaissant que le contraste numérique et les dégénérescences affectent la qualité de la solution.

Contributions clés

• Formule marginale explicite : Dérivation d'une équation marginale par réseaux de tenseurs dont la limite à température zéro et à arithmétique exacte identifie un itinéraire réalisable optimal via une règle marginale séquentielle.
• Encodage des contraintes : Définition de couches MPO pour les contraintes de comptage (non-répétition) applicables à divers problèmes combinatoires.
• Cadre de généralisation : Une construction modulaire adaptant le formalisme TN aux variantes du TSP (TDTSP, JRP, BTSP, etc.) en modifiant des couches de tenseurs spécifiques.
• Implémentation heuristique : Une implémentation à précision finie et $\tau$ fini fonctionnant comme une heuristique calibrée, avec une analyse de son comportement concernant le contraste numérique et la dégénérescence.

Résultats
L'étude expérimentale se concentre sur de petites instances synthétiques ($N \in \{5, \dots, 12\}$) pour valider l'exactitude de la méthode et son comportement numérique plutôt que pour revendiquer une supériorité computationnelle par rapport aux solveurs spécialisés.

• Calibration : Le paramètre de temps imaginaire $\tau$ dépend de la taille. Un balayage de calibration ($\tau \in \{1, \dots, 40\}$) a considérablement amélioré le taux de solution optimale, passant de 55,56 % (à $\tau=1$) à 95,56 % sur l'ensemble d'évaluation.
• Comparaison avec les solveurs : Sur de petites instances, le solveur TN calibré a atteint un taux d'optimalité de 95,24 %, surpassant NetworkX greedy (26,67 %) et le recuit simulé (59,05 %), mais restant en deçà de la référence exacte Held-Karp (100 %).
• Ablation de couches : Le retrait des couches de contraintes a dégradé la qualité de la solution, confirmant que l'ensemble complet des filtres est nécessaire pour une haute précision.
• Cas industriel (JRP) : Dans une preuve de concept pour le problème de réaffectation des tâches ONCE, la méthode TN a produit des solutions avec des coûts accumulés identiques à ceux du Digital Annealer d'Azure, ne différant que dans les cas dégénérés où plusieurs affectations optimales existent.

Signification et revendications
Les auteurs déclarent explicitement une modestie concernant la puissance computationnelle de la méthode. Ils ne revendiquent pas un avantage computationnel général par rapport aux solveurs classiques spécialisés (comme Held-Karp, la séparation et coupe, ou les algorithmes spécifiques aux affectations) pour le TSP général.

• Représentation formelle : Le travail est présenté comme une « représentation formelle exacte à arithmétique exacte en temps exponentiel » et une « plateforme pour des approximations et extensions contrôlées ».
• Nature heuristique : L'implémentation à $\tau$ fini est caractérisée comme une « heuristique calibrée à précision finie » dont le comportement dépend du contraste numérique et des dégénérescences.
• Utilité : La valeur principale réside dans le cadre modulaire des réseaux de tenseurs, qui permet l'intégration systématique de contraintes diverses (précédence, groupes, coûts non markoviens) et l'application de techniques d'approximation (suppression de couches, contractions sparse) au sein d'un formalisme unifié.
• Limitations : La méthode conserve une échelle exponentielle dans le pire des cas. Des problèmes de stabilité numérique (sous-dépassement, perte de contraste dans les cas dégénérés) et la nécessité d'une calibration dépendante de la taille sont identifiés comme des limitations significatives.

En résumé, l'article fournit un formalisme rigoureux par réseaux de tenseurs pour le TSP et ses variantes, démontrant sa capacité à retrouver des solutions optimales sur de petites instances et à intégrer des contraintes industrielles, tout en reconnaissant qu'il ne surmonte pas la complexité exponentielle fondamentale du problème.