Суть HyCO
HyCO — Hybrid Neural Solver for Combinatorial Optimization. La méthode construit un préfixe de solution à l'aide d'un solveur RL. Elle bascule ensuite de manière adaptative vers un modèle de diffusion conditionnel. Celui-ci complète les solutions restantes. L'hybride résout des problèmes d'optimisation combinatoire neuronale. Son objectif est de réunir les points forts de deux classes de solveurs.
Le travail est disponible sous la référence arXiv:2609.07990. Auteurs : Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong. Le preprint relève de cs.LG et cs.AI. Les auteurs ont soumis la version v1 le 7 Sep 2026. Ces données aident à retrouver la source originale et à vérifier les détails.
Sens pratique : HyCO ne remplace pas un solveur par un autre, mais gère la transition entre eux.
Où les stratégies isolées échouent
Les solveurs RL séquentiels et les solveurs DM globaux présentent des modes de défaillance complémentaires. Cela se voit dans le regret d'optimisation.
| Classe de solveur | Point fort | Point faible |
|---|---|---|
| Sequential RL | Faible regret marginal au début de la construction | Les erreurs s'accumulent sur l'horizon ; le regret croît de façon superlinéaire |
| Global DM | Évite l'accumulation sur l'horizon | Regret linéaire ou sous-linéaire par rapport à la dimension du sous-espace non résolu restant |
Conclusion : les défaillances ne coïncident pas. Le RL est bon au début, mais souffre de l'horizon. Le DM n'accumule pas d'erreur d'horizon, mais paie pour la taille du problème restant. L'hybridation exploite cet écart.
Cadre théorique du basculement
Les auteurs construisent un cadre théorique unifié de mise à l'échelle des erreurs. Sous des hypothèses explicites de mise à l'échelle des erreurs, le cadre démontre deux propositions.
- La structure hybride donne un regret attendu strictement inférieur à chacune des deux schémas de base pris séparément.
- Il existe un unique pas de basculement optimal qui minimise le regret de l'hybride.
Les auteurs définissent le pas optimal au niveau du regret attendu. Sur des trajectoires individuelles, il ne peut pas être calculé directement. Un déclencheur pratique est donc nécessaire.
Conclusion : la théorie explique pourquoi l'hybride aide et quand déclencher le transfert. Elle ne fournit pas de formule prête à l'emploi pour chaque trajectoire.
Comment fonctionne le déclencheur adaptatif
HyCO utilise un déclencheur adaptatif léger. Le déclencheur combine l'entropie de la politique et la divergence RL-DM. Ces signaux détectent le changement de régime au niveau de la trajectoire. Ils servent de proxy pratique. Un tel proxy est nécessaire, car le pas de basculement optimal ne se calcule pas sur une trajectoire individuelle.
Le déclencheur termine le préfixe RL. Le DM conditionnel complète les solutions restantes. Critère pratique : surveiller l'entropie de la politique et la divergence RL-DM. Ces signaux indiquent le changement de régime et le moment du transfert. Le déclencheur reste léger et adaptatif.
Expériences et critère de choix
Dans les expériences sur divers benchmarks, HyCO apporte des améliorations robustes par rapport aux deux solveurs de base. Les résultats confirment également l'efficacité empirique du déclencheur adaptatif.
Critère pratique de choix : il faut un algorithme d'inférence pour l'optimisation combinatoire. Il utilise le RL pour le préfixe précoce et le DM pour les solutions restantes. L'hybride réduit le regret attendu par rapport à chaque schéma de base. HyCO convient comme couche de basculement au-dessus de la recherche RL et du complètement par diffusion. Il gère la transition entre eux.
