💻 computer science

Connected by Construction: Learning Tractable Near-Tour Marginals for Traveling Salesman Problems

Le papier propose C2TSP, un pipeline d'apprentissage non supervisé de bout en bout qui apprend directement des structures hamiltoniennes interprétables pour le problème du voyageur de commerce à travers une famille de 1-arbres enracinés connectés par construction, atteignant une forte performance de parcours tout en préservant l'information structurelle via des perturbations d'arêtes résiduelles et un affinement guidé par certificat.

Auteurs originaux : Ke Sun, Xinyuan Zhang, Xinwu Qian

Publié 2026-07-15

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ke Sun, Xinyuan Zhang, Xinwu Qian

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de résoudre l'ultime casse-tête de livraison : le problème du voyageur de commerce (TSP). Vous avez une liste de villes, et vous devez trouver le chemin le plus court qui visite chacune d'entre elles exactement une fois et revient au point de départ. C'est un classique de la réflexion qui devient incroyablement difficile à mesure que l'on ajoute des villes.

Pendant longtemps, les informaticiens ont essayé d'apprendre aux machines à résoudre cela en utilisant des méthodes « basées sur l'apprentissage ». Pensez à ces méthodes comme à un étudiant à qui l'on donne une carte et à qui l'on demande de deviner le meilleur itinéraire. Mais voici le piège : la plupart de ces étudiants ne font en réalité que deviner une « carte de chaleur » (une image floue montrant quelles routes pourraient être bonnes) ou une liste de « règles de construction » (comment construire l'itinéraire étape par étape). Ils ne tiennent pas réellement le circuit fini et connecté entre leurs mains jusqu'à la toute fin, lorsqu'ils tentent de décoder leur supposition en un véritable chemin. C'est comme essayer de cuisiner un gâteau en ne devinant que les ingrédients et en espérant que le four les transformera par magie en un gâteau parfait à la fin.

Les auteurs de ce papier, Ke Sun, Xinyuan Zhang et Xinwu Qian, disent : « Attendez une minute. Si nous ne savons pas à quoi ressemble le gâteau avant qu'il n'entre dans le four, comment savoir si nous apprenons la bonne chose ? »

La Grande Idée : Construire d'abord un Squelette Connecté

Au lieu de deviner une carte de chaleur floue, les auteurs proposent une nouvelle façon d'apprendre appelée C2TSP. Leur ingrédient secret est un concept qu'ils appellent « connecté par construction » (connected-by-construction).

Imaginez que vous construisez un modèle du réseau routier d'une ville. La plupart des méthodes essaient de dessiner des lignes sur une feuille de papier en espérant qu'elles se connectent plus tard. C2TSP commence par construire un squelette spécifique et robuste appelé 1-arbre enraciné (rooted 1-tree).

Le Squelette : Imaginez un hub central (la ville « racine ») connecté à deux routes. Ensuite, imaginez un arbre de routes connectant toutes les autres villes à ce hub.
La Magie : En le construisant de cette façon, le modèle est garanti d'être connecté. Vous ne pouvez pas accidentellement dessiner une route qui ne mène nulle part ou diviser la ville en deux îles. C'est comme construire une maison avec des fondations qui garantissent que les murs toucheront toujours le toit.

La seule chose qui manque à ce squelette pour devenir un tour parfait (un cycle hamiltonien) est que chaque ville doit avoir exactement deux routes connectées à elle (une entrée, une sortie). Dans le 1-arbre, le hub possède deux routes, mais les autres villes peuvent en avoir trois ou seulement une.

La Solution : La Couche de « Rééquilibrage »

Pour corriger l'excès ou le manque de routes, l'équipe utilise un tour astucieux qu'ils appellent une couche d'équilibrage de Held–Karp lissée (smoothed Held–Karp equilibration layer).

Voyez cela comme un contrôleur de trafic très intelligent. Le modèle regarde le squelette du 1-arbre et demande : « Hé, la Ville A a trois routes, mais elle n'en a besoin que de deux. La Ville B en a une, mais en a besoin de deux. » Le contrôleur ne se contente pas de supprimer des routes ; il ajuste les « prix » des routes. Il rend les routes supplémentaires coûteuses et les routes manquantes bon marché, poussant le système jusqu'à ce que, en moyenne, chaque ville ait exactement deux routes.

C'est un événement majeur car, contrairement aux autres méthodes qui essaient de deviner tout l'itinéraire à la fois, cette méthode calcule la probabilité exacte de chaque route faisant partie de la solution tout en maintenant la structure connectée. Ils ont prouvé mathématiquement qu'ils peuvent effectuer ce calcul parfaitement, ce qui était auparavant considéré comme impossible pour le problème du tour complet.

Le « Certificat » : Un Filet de Sécurité

Même après le rééquilibrage, il peut rester un petit peu de « désordre ». Le squelette est connecté et équilibré en moyenne, mais il n'est peut-être pas encore un tour parfait.

Les auteurs introduisent un certificat, qui est comme un filet de sécurité ou une étiquette d'avertissement. Il mesure exactement quelle quantité de « désordre » (ou de masse de non-tour) subsiste dans le système. C'est une garantie mathématique qui dit : « Nous savons que la structure est prête à 99 %, et voici le nombre exact pour le 1 % restant. »

En utilisant ce certificat, ils appliquent une étape finale appelée aiguisage (sharpening). Imaginez que vous avez une photo légèrement floue d'un itinéraire. L'étape d'aiguisage rend les bonnes routes très brillantes et les mauvaises routes sombres, poussant le modèle vers un tour parfait et net.

Ce Qu'Ils Ont Trouvé

L'équipe a testé sa méthode sur des puzzles de 50, 100, 200, 500 et même 1 000 villes. Voici ce que les chiffres ont montré :

Décodage Pur : Lorsque les auteurs ont laissé le modèle choisir le meilleur itinéraire sans aide supplémentaire (comme une intervention humaine), C2TSP s'est révélé incroyablement fort. Sur un puzzle de 100 villes, il a trouvé un itinéraire avec un écart d'optimalité de seulement 1,90 % après 100 tours de recherche locale, et 4,83 % avec une simple supposition de « meilleur choix ».
Comparaison : D'autres méthodes populaires, comme DIFUSCO ou Fast-T2T, ont souvent eu du mal lorsque les puzzles devenaient grands (500+ villes), à moins d'utiliser beaucoup de temps de recherche supplémentaire. C2TSP est resté constant.
Le Test d'« Ablation » : Pour prouver que leurs idées fonctionnaient, ils ont retiré des parties de leur système.
- Sans la perturbation des arêtes (la partie qui apprend à ajuster les prix des routes), l'erreur est passée de 1,55 % à 12,74 %.
- Sans l'aiguisage, le modèle a appris une structure connectée mais n'est pas parvenu aussi près du tour parfait.
- Cela prouve que l'apprentissage des prix des routes et l'étape finale d'aiguisage sont tous deux nécessaires pour obtenir les meilleurs résultats.

Ce Qu'Ils Ne Revendiquent Pas

Il est important de noter ce que ce papier ne dit pas. Ils ne prétendent pas avoir résolu le problème du voyageur de commerce une fois pour toutes. Ils déclarent explicitement que leur méthode repose sur un « substitut traitable » (tractable surrogate) : une approximation intelligente. Le 1-arbre enraciné est un substitut du tour parfait. Bien qu'il s'en rapproche énormément, le papier admet que les « fluctuations de degré » restantes (les petites imperfections où une ville pourrait avoir 3 routes au lieu de 2) sont contrôlées et réduites, mais pas toujours éliminées exactement.

Ils notent également que pour les puzzles très larges (comme 1 000 villes), d'autres méthodes qui utilisent beaucoup de recherche locale (comme DIMES) peuvent encore être performantes, mais C2TSP excelle lorsque vous voulez un point de départ solide qui est déjà structurellement sain.

La Conclusion

En termes simples, C2TSP revient à apprendre à un robot à construire un tour en le forçant d'abord à construire un squelette connecté, puis en lui apprenant à équilibrer les routes, et enfin en lui donnant un certificat pour vérifier son travail. Au lieu de deviner une image floue en espérant qu'elle devienne un itinéraire, le robot apprend la forme même de l'itinéraire. Les résultats suggèrent que cette approche « connectée par construction » rend le processus d'apprentissage plus stable et les itinéraires finaux bien meilleurs, surtout lorsque les puzzles deviennent grands et complexes.

Résumé Technique : Connected by Construction (C2TSP)

Définition du Problème

Le papier traite du problème du Voyageur de Commerce (TSP), un problème d'optimisation combinatoire canonique nécessitant une solution qui satisfait deux contraintes structurelles : des contraintes de degré locales (chaque nœud doit avoir un degré de deux) et une connectivité globale (les arêtes sélectionnées doivent former un unique cycle hamiltonien).

Les méthodes actuelles d'apprentissage pour le TSP échouent souvent à représenter directement la structure connectée globale au sein de l'objet appris. Au lieu de cela, elles reposent sur :

La construction autorégressive : Génération séquentielle des tours avec masquage procédural.
Les approches basées sur des cartes de chaleur (heatmaps) : Prédiction de scores d'arêtes et recours à des processus de réparation, d'échantillonnage ou de recherche en aval pour obtenir un tour valide.
Les relaxations dans l'espace d'assignation : Modélisation d'objets lisses de type permutation qui ne capturent pas directement la structure d'adjacence des arêtes déterminant le coût du tour.

Ces approches souffrent de deux limitations principales : elles ne fournissent pas une distribution globale traitable sur des objets combinatoires connectés, et leurs performances sont étroitement liées aux processus de décodage ou de recherche en aval, ce qui rend difficile la séparation de la qualité de la représentation apprise des effets du post-traitement.

Méthodologie : C2TSP

Les auteurs proposent C2TSP (Connected by Construction), un pipeline d'apprentissage non supervisé de bout en bout qui apprend le TSP via un objet latent structurellement significatif : l'arbre racine 1 (rooted 1-tree).

1. Le substitut par l'Arbre Racine 1

Au lieu de tenter d'apprendre directement un cycle hamiltonien (qui possède une fonction de partition intraitable), le modèle opère sur la famille des arbres racines 1.

Définition : Un arbre racine 1 consiste en un arbre couvrant sur tous les nœuds non-racine ( $\bar{V}$ ) plus exactement deux arêtes incidentes à un nœud racine fixe ( $r$ ).
Garantie structurelle : Par construction, chaque configuration de cette famille est globalement connectée et satisfait la contrainte de degré de la racine ( $d_r = 2$ ).
Tractabilité : Contrairement à la distribution de Gibbs hamiltonienne, la famille des arbres racines 1 admet une factorisation exacte. Cela permet le calcul exact de la fonction de partition $Z_r(\eta)$ , des marginales d'arêtes $\mu(\eta)$ et des moments de degré, permettant un entraînement par coût attendu sans échantillonnage.

2. Équilibrage de Held–Karp lissé

Le principal défaut structurel d'un arbre racine 1 est que les nœuds non-racines peuvent ne pas avoir un degré de deux. Pour corriger cela, les auteurs introduisent une couche d'équilibrage de Held–Karp (HK) lissée.

Cette couche résout les variables duales additives aux nœuds ( $\lambda$ ) qui modifient les coûts des arêtes de telle sorte que le degré attendu de chaque nœud non-racine soit égal à deux sous la distribution de Gibbs modifiée.
La couche est entraînée de bout en bout via la différenciation implicite à travers la carte d'équilibre, suivant le paradigme des couches d'optimisation implicite.
Ce processus garantit que la distribution apprise est équilibrée en termes de degré en espérance, éliminant le « défaut de degré » tout en maintenant la connectivité.

3. Affinement guidé par certificat

Même après l'équilibrage HK, la distribution peut encore contenir une masse de probabilité sur des structures non-tour (arbres racines 1 qui ne sont pas des cycles hamiltoniens).

Certificat : Les auteurs dérivent un certificat qui borne cette « masse non-tour » ( $\gamma(q)$ ) en utilisant la variance totale des degrés des nœuds non-racines : $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$ .
Raffinement : Une étape d'affinement guidée par certificat utilise la dérivée d'un certificat de borne supérieure de Bernoulli pour pousser la distribution marginale vers des structures plus proches des tours. Cela agit comme un raffinement déterministe qui pénalise les arêtes de faible probabilité et récompense les arêtes de haute probabilité, réduisant ainsi la borne supérieure certifiée de la masse non-tour.

4. Pipeline d'apprentissage

Le pipeline apprend des perturbations résiduelles d'arêtes ( $\Gamma_\theta$ ) à partir du coût TSP non biaisé.

Passage direct (Forward Pass) : Les coûts bruts sont perturbés, projetés pour supprimer les composantes additives aux nœuds, passés à travers la couche d'équilibrage HK, et raffinés via l'affinement guidé par certificat.
Fonction de perte : Le modèle est entraîné à l'aide d'une perte non supervisée basée sur le coût attendu du TSP des marginales d'arêtes apprises, sans termes de pénalité explicites pour les contraintes structurelles (car celles-ci sont imposées par l'architecture).

Contributions Clés

Représentation par Arbre Racine 1 Traitable : Le papier introduit une représentation qui assure la connectivité globale par construction tout en admettant le calcul exact des marginales pour l'entraînement.
Pipeline C2TSP : Un cadre non supervisé de bout en bout combinant un réseau de neurones sur graphe (GNN) pour la perturbation résiduelle des arêtes et une couche Held–Karp lissée pour l'équilibrage des degrés.
Certificat de Masse Non-Tour : La dérivation d'un certificat bornant l'écart structurel résiduel, qui est ensuite utilisé pour guider un mécanisme d'affinement qui pousse la distribution vers les cycles hamiltoniens.
Validation Empirique : Démonstration que la représentation par arbre racine 1 produit de solides performances de décodage pur et reste robuste lorsqu'elle est intégrée dans des solveurs classiques comme LKH-3, contrairement à plusieurs bases de référence par cartes de chaleur qui se dégradent à des échelles plus grandes.

Résultats Expérimentaux

Les auteurs ont évalué C2TSP sur des instances de TSP euclidien symétrique en 2D (TSP-50 à TSP-1000) contre des bases de référence incluant DIFUSCO, DIMES, Fast-T2T, UTSP et NeuroLKH.

Décodage Pur : C2TSP a obtenu l'écart d'optimalité le plus bas dans 20 des 25 configurations testées (variant la taille du problème et le niveau de décodeur). Notamment, il a performé de manière optimale dans les régimes avec des budgets de recherche locale importants (ex: 100 itérations de 2-opt), suggérant que la distribution apprise encode déjà une forte structure de tour.
Intégration LKH : Utilisé comme source de candidats pour le solveur LKH-3, C2TSP est resté robuste à travers toutes les tailles de problèmes, restant à environ 1 partie pour dix mille (‱) du LKH-3 classique. En revanche, les méthodes basées sur des cartes de chaleur (DIFUSCO, Fast-T2T, UTSP) se sont considérablement dégradées pour les grandes tailles ( $n \geq 500$ ) lorsqu'elles étaient intégrées à LKH.
Études d'Ablation :
- La suppression de la perturbation d'arêtes a provoqué une chute substantielle des performances (l'écart moyen est passé de 1,55 % à 12,74 %), indiquant la nécessité d'apprendre la géométrie résiduelle des arêtes.
- L'affinement guidé par certificat a encore amélioré les performances en raffinant la distribution marginale, confirmant que le faible coût relaxé seul est insuffisant pour un décodage de haute qualité.

Signification et Revendications

Le papier affirme qu'un objet latent différentiable est un choix de modélisation central pour l'apprentissage du TSP. En encodant la connectivité avant le décodage, C2TSP expose une « marginale de quasi-tour » dont l'évolution structurelle peut être entraînée, certifiée et analysée.

Les auteurs positionnent leur travail comme un passage de l'apprentissage de scores d'arêtes non contraints vers l'apprentissage d'une marginale de quasi-tour traitable avec une signification structurelle explicite. Ils soutiennent que cette approche sépare la représentation apprise du post-traitement, permettant au modèle de fournir un point de départ globalement cohérent pour les procédures de recherche locale.

Le papier reconnaît une limitation inhérente à son choix de conception : l'arbre racine 1 relaxe l'appui exact du cycle hamiltonien. Bien que la connectivité soit imposée et que l'équilibre des degrés soit restauré en espérance, les fluctuations de degré restantes sont contrôlées via l'équilibrage et l'affinement plutôt qu'éliminées exactement. Les auteurs suggèrent que cela ouvre des directions pour des mises à jour plus strictes guidées par certificat et des familles connectées tractables plus riches.