An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization

Résumé technique : Un seuil d'efficacité amortie pour comparer les solveurs neuronaux et heuristiques en optimisation combinatoire

Énoncé du problème
L'article traite d'une critique répandue en recherche opérationnelle et en IA verte : celle selon laquelle les solveurs neuronaux pour l'optimisation combinatoire (OC) sont intrinsèquement moins économes en énergie que les métaheuristiques traditionnelles basées sur CPU, en raison des coûts énergétiques substantiels associés à l'entraînement sur GPU. Les auteurs soutiennent que cette critique repose sur une étape inférentielle erronée. Elle traite incorrectement le coût initial fixe et élevé de l'entraînement comme une disqualification permanente, en ignorant le fait que les solveurs neuronaux engendrent un coût d'inférence par instance très faible et amortissable, tandis que les métaheuristiques engendrent un coût marginal constant pour chaque instance résolue. L'article postule que ces deux profils de coûts (fixe versus marginal) ne sont pas commensurables en tant que scalaires, mais doivent être comparés sur un volume de déploiement spécifique.

Méthodologie : Le Seuil d'Efficacité Amortie (SEA)
Pour formaliser cette comparaison, l'article introduit le Seuil d'Efficacité Amortie (SEA), un cadre quantitatif défini par trois composantes principales :

1. Définition du SEA : Le SEA est le volume de déploiement ($N$) pour lequel l'énergie cumulative (ou le carbone) d'un solveur neuronal ($M$) égale celle d'un solveur heuristique de référence ($B$). Il est calculé comme suit :
   $$SEA = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   Ce calcul est soumis à une contrainte de faisabilité qualité : l'écart d'optimalité attendu du solveur neuronal ne doit pas dépasser celui de la référence de plus d'une tolérance $\delta$ définie par l'utilisateur. Cette contrainte empêche les solveurs « rapides mais incorrects » de réduire artificiellement le seuil.

   • $E_{train}(M)$ inclut le coût cumulatif de tous les balayages d'hyperparamètres, des échecs d'exécution et des prototypes, et pas seulement du modèle convergé final.
   • $E_{inst}^{NN}$ est l'énergie d'inférence par instance, calculée sur la base du débit par lots ($\tau_{NN}$) plutôt que du temps d'exécution wall-clock d'une seule instance, reflétant la nature parallèle de l'exécution sur GPU.

2. Comptabilité du cycle de vie (Carbone incorporé) : Le cadre étend la comptabilité énergétique opérationnelle pour inclure le carbone incorporé issu de la fabrication du matériel. Ce coût est amorti linéairement sur une durée de vie matérielle configurable (par défaut cinq ans) et appliqué symétriquement à la fois à l'accélérateur neuronal et au CPU de référence. Cela garantit que la comparaison prend en compte l'impact complet du cycle de vie, notant que les GPU à haut débit peuvent avoir une charge incorporée par instance plus faible que les CPU s'ils sont utilisés efficacement.

3. Argument structurel asymptotique : L'article démontre (Proposition 1) que si l'énergie par instance du solveur neuronal est strictement inférieure à celle de la référence ($E_{inst}^{NN} < E_{inst}^{base}$), le rapport de leurs énergies cumulées converge vers une constante strictement inférieure à un lorsque $N \to \infty$. Crucialement, cette limite est indépendante du coût d'entraînement, des surcoûts du datacenter (PUE) ou de l'intensité carbone régionale, à condition que ces facteurs s'appliquent symétriquement aux deux côtés.

Implémentation expérimentale et résultats
Le cadre est implémenté sur l'environnement du Problème de Routage de Véhicules Multi-Tâches (MTVRP) avec $n=20$ clients répartis sur 19 variantes de problèmes.

• Référence : Recherche Génétique Hybride (HGS) implémentée dans PyVRP.
• Solveur neuronal : Une politique apprise entraînée sur un seul GPU à travers cinq graines.
• Métriques clés :
  • Rapport par instance : Le solveur neuronal consomme environ 0,41 Wh par instance contre 1,32 Wh pour la référence HGS mono-thread (un gain d'efficacité d'environ 2,4x par instance).
  • Coût d'entraînement : L'énergie médiane d'entraînement était de 121,5 Wh.
  • Point de croisement (SEA) : Le point de croisement mesuré se situe à environ $1,58 \times 10^5$ instances déployées. Au-delà de ce volume, le solveur neuronal devient plus économe en énergie en termes d'énergie cumulative totale.
  • Sensibilité : Les auteurs analysent une surface de sensibilité à cinq axes (taille de lot, tolérance qualité, threads de la référence, niveau matériel, graine d'entraînement). Ils constatent que, bien que le niveau matériel et la tolérance qualité déplacent significativement la valeur du SEA, la convergence structurelle du rapport reste robuste.

Contributions principales

1. Formalisation du SEA : Une métrique qui quantifie le point d'équilibre pour les solveurs neuronaux sous des contraintes explicites de qualité de solution, déplaçant le débat du rhétorique au quantitatif.
2. Correction du cycle de vie : L'inclusion du carbone incorporé amorti symétriquement, remettant en question les méthodes de comptabilité purement opérationnelles.
3. Preuve asymptotique : Une démonstration mathématique que le verdict qualitatif (les solveurs neuronaux gagnent à grande échelle) est structurellement solide et indépendant des disputes de calibration concernant les coûts d'entraînement ou l'intensité du réseau électrique.
4. Instrumentation ouverte : La publication des protocoles de mesure et des scripts pour reproduire le suivi énergétique et l'analyse de sensibilité.

Portée et affirmations
L'article prétend résoudre l'objection de « l'efficacité énergétique » contre les solveurs neuronaux pour l'OC en reformulant la question. Il affirme que l'objection est correcte concernant la prémisse (l'entraînement est coûteux) mais incorrecte concernant la conclusion (la méthode est globalement inefficace).

• Dépendance du régime : Les solveurs neuronaux sont moins efficaces uniquement en dessous du SEA. Au-dessus du SEA, le coût marginal de l'heuristique s'accumule sans limite, tandis que le coût fixe du solveur neuronal est entièrement amorti.
• Avantage structurel : L'article soutient que l'avantage structurel de l'inférence neuronale par lots sur la recherche heuristique sérielle implique que l'écart d'efficacité s'élargira considérablement à des tailles de problèmes plus grandes ($n=50, 100$), où les temps de recherche heuristique évoluent de manière super-linéaire tandis que le débit neuronal reste relativement stable.
• Modestie : Les auteurs déclarent explicitement que les résultats actuels constituent une « configuration illustrative » à $n=20$. Ils reconnaissent que le rapport par instance (0,41) est modéré et que la validation empirique complète de la surface de sensibilité et des plus grandes tailles de problèmes est laissée pour un travail futur. L'article ne prétend pas que les solveurs neuronaux sont universellement supérieurs, mais fournit plutôt le cadre pour déterminer quand et sous quelles conditions ils constituent le choix environnementalement préférable.