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

Technische Samenvatting: Een Geamortiseerde Efficiëntiedrempel voor het Vergelijken van Neuronale en Heuristische Oplossers in Combinatorische Optimalisatie

Probleemstelling
Het artikel adresseert een veelvoorkomende kritiek in operations research en Green AI: dat neuronale oplossers voor combinatorische optimalisatie (CO) inherent minder energie-efficiënt zijn dan traditionele CPU-gebaseerde metaheuristieken, vanwege de aanzienlijke energiekosten die gepaard gaan met training op GPU's. De auteurs betogen dat deze kritiek rust op een gebrekkige inferentiële stap. Deze behandelt de grote, vaste voorafgaande kosten van training ten onrechte als een permanente diskwalificatie, en negeert het feit dat neuronale oplossers zeer kleine, geamortiseerbare kosten per instantie voor inferentie hebben, terwijl metaheuristieken constante marginale kosten maken voor elke opgeloste instantie. Het artikel stelt dat deze twee kostenprofielen (vast versus marginaal) niet als scalairen met elkaar vergelijkbaar zijn, maar dat ze vergeleken moeten worden over een specifiek implementatievolume.

Methodologie: De Geamortiseerde Efficiëntiedrempel (AET)
Om deze vergelijking te formaliseren, introduceert het artikel de Geamortiseerde Efficiëntiedrempel (AET), een kwantitatief raamwerk dat wordt gedefinieerd door drie kerncomponenten:

1. Definitie van AET: De AET is het implementatievolume ($N$) waarbij de cumulatieve energie (of koolstof) van een neuronale solver ($M$) gelijk is aan die van een baseline heuristische solver ($B$). Deze wordt berekend als:
   $$AET = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   Deze berekening is onderhevig aan een kwaliteit-buigzaamheidsbeperking: de verwachte optimaliteitsgap van de neuronale solver mag de gap van de baseline niet meer dan een door de gebruiker gedefinieerde tolerantie $\delta$ overschrijden. Deze beperking voorkomt dat "snelle maar onjuiste" oplossers de drempel kunstmatig verlagen.

   • $E_{train}(M)$ omvat de cumulatieve kosten van alle hyperparameter-sweeps, mislukte runs en prototypes, niet alleen het uiteindelijk geconvergeerde model.
   • $E_{inst}^{NN}$ is de energie voor inferentie per instantie, berekend op basis van batch-georiënteerde doorvoer ($\tau_{NN}$) in plaats van wall-time voor een enkele instantie, wat de parallelle aard van GPU-executie weerspiegelt.

2. Levenscyclusrekening (Geïncorporeerde Koolstof): Het raamwerk breidt operationele energierekening uit tot het omvatten van geïncorporeerde koolstof uit hardwarefabricage. Deze kosten worden lineair geamortiseerd over een configureerbare hardwarelevensduur (standaard vijf jaar) en symmetrisch toegepast op zowel de neuronale accelerator als de baseline CPU. Dit zorgt ervoor dat de vergelijking rekening houdt met de volledige levenscyclusimpact, waarbij wordt opgemerkt dat high-throughput GPU's een lagere geïncorporeerde last per instantie kunnen hebben dan CPU's indien efficiënt worden benut.

3. Asymptotisch Structureel Argument: Het artikel bewijst (Propositie 1) dat, als de energie per instantie van de neuronale solver strikt lager is dan die van de baseline ($E_{inst}^{NN} < E_{inst}^{base}$), de verhouding van hun cumulatieve energieën convergeert naar een constante die strikt kleiner is dan één wanneer $N \to \infty$. Cruciaal is dat deze limiet onafhankelijk is van de trainingskosten, datacenter-overhead (PUE) of regionale koolstofintensiteit, mits deze factoren symmetrisch op beide zijden van toepassing zijn.

Experimentele Instantiëring en Resultaten
Het raamwerk wordt geïnstantieerd op de Multi-Task Vehicle Routing Problem (MTVRP)-omgeving met $n=20$ klanten over 19 probleemvarianten.

• Baseline: Hybrid Genetic Search (HGS) geïmplementeerd in PyVRP.
• Neuronale Solver: Een geleerd beleid getraind op een enkele GPU over vijf zaden (seeds).
• Kernmetrieken:
  • Verhouding per instantie: De neuronale solver verbruikt ongeveer 0,41 Wh per instantie vergeleken met 1,32 Wh voor de single-threaded HGS-baseline (een efficiëntiewinst van ~2,4x per instantie).
  • Trainingskosten: De mediane trainingsenergie bedroeg 121,5 Wh.
  • Crossoverpunt (AET): De gemeten crossover vindt plaats bij ongeveer $1,58 \times 10^5$ geïmplementeerde instanties. Boven dit volume wordt de neuronale solver in totale cumulatieve energie energie-efficiënter.
  • Gevoeligheid: De auteurs analyseren een gevoeligheidsoppervlak van vijf assen (batchgrootte, kwaliteitstolerantie, baseline-threads, hardware-tier, trainingszaad). Zij constateren dat hoewel hardware-tier en kwaliteitstolerantie de AET-waarde significant verschuiven, de structurele convergentie van de verhouding robuust blijft.

Belangrijkste Bijdragen

1. Formalisatie van AET: Een metriek die het break-evenpunt voor neuronale oplossers kwantificeert onder expliciete kwaliteitsbeperkingen voor oplossingen, waardoor het debat verschuift van retoriek naar kwantificatie.
2. Levenscycluscorrectie: De opname van geïncorporeerde koolstof die symmetrisch wordt geamortiseerd, wat operationele alleen-rekenmethoden uitdaagt.
3. Asymptotisch Bewijs: Een wiskundige demonstratie dat het kwalitatieve oordeel (neuronale oplossers winnen op schaal) structureel gezond is en onafhankelijk van kalibratiegeschillen rondom trainingskosten of netintensiteit.
4. Open Instrumentatie: De release van meetprotocollen en scripts om energievolging en gevoeligheidsanalyse te reproduceren.

Betekenis en Claims
Het artikel claimt de bezwaren tegen "energie-efficiëntie" van neuronale CO-oplossers op te lossen door de vraag te herformuleren. Het stelt dat de bezwaren correct zijn wat betreft de premiss (training is duur), maar onjuist wat betreft de conclusie (de methode is netto inefficiënt).

• Regime-afhankelijkheid: Neuronale oplossers zijn alleen minder efficiënt onder de AET. Boven de AET compenseert de marginale kosten van de heuristiek zonder grens, terwijl de vaste kosten van de neuronale solver volledig worden geamortiseerd.
• Structureel Voordeel: Het artikel betoogt dat het structurele voordeel van batch-georiënteerde neuronale inferentie ten opzichte van seriële heuristische zoektocht impliceert dat het efficiëntieverschil aanzienlijk zal toenemen bij grotere probleemgroottes ($n=50, 100$), waar zoektijden van heuristieken superlineair schalen terwijl neuronale doorvoer relatief stabiel blijft.
• Bescheidenheid: De auteurs stellen expliciet dat de huidige resultaten een "illustratieve configuratie" zijn bij $n=20$. Zij erkennen dat de verhouding per instantie (0,41) gematigd is en dat de volledige empirische validatie van het gevoeligheidsoppervlak en grotere probleemgroottes wordt overgelaten aan toekomstig werk. Het artikel claimt niet dat neuronale oplossers universeel superieur zijn, maar biedt eerder het raamwerk om te bepalen wanneer en onder welke voorwaarden zij de milieuvriendelijkere keuze zijn.