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

Resumen Técnico: Un Umbral de Eficiencia Amortizada para Comparar Solucionadores Neuronales y Heurísticos en Optimización Combinatoria

Enunciado del Problema
El artículo aborda una crítica prevalente en investigación operativa e IA Verde: que los solucionadores neuronales de optimización combinatoria (OC) son inherentemente menos eficientes energéticamente que los metaheurísticos tradicionales basados en CPU debido a los sustanciales costos energéticos asociados con el entrenamiento en GPUs. Los autores argumentan que esta crítica se basa en un paso inferencial defectuoso. Trata incorrectamente el gran costo fijo inicial del entrenamiento como una descalificación permanente, ignorando el hecho de que los solucionadores neuronales incurren en un costo de inferencia por instancia muy pequeño y amortizable, mientras que los metaheurísticos incurren en un costo marginal constante para cada instancia resuelta. El artículo postula que estos dos perfiles de costos (fijo frente a marginal) no son comparables como escalares, sino que deben compararse sobre un volumen de despliegue específico.

Metodología: El Umbral de Eficiencia Amortizada (AET)
Para formalizar esta comparación, el artículo introduce el Umbral de Eficiencia Amortizada (AET), un marco cuantitativo definido por tres componentes principales:

1. Definición de AET: El AET es el volumen de despliegue ($N$) en el cual la energía (o carbono) acumulada de un solucionador neuronal ($M$) iguala a la de un solucionador heurístico de referencia ($B$). Se calcula como:
   $$AET = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   Este cálculo está sujeto a una restricción de viabilidad de calidad: la brecha de optimalidad esperada del solucionador neuronal no debe exceder la brecha de la referencia en más de una tolerancia definida por el usuario $\delta$. Esta restricción evita que los solucionadores "rápidos pero incorrectos" reduzcan artificialmente el umbral.

   • $E_{train}(M)$ incluye el costo acumulado de todos los barridos de hiperparámetros, ejecuciones fallidas y prototipos, no solo el modelo convergente final.
   • $E_{inst}^{NN}$ es la energía de inferencia por instancia, calculada basándose en el rendimiento por lotes ($\tau_{NN}$) en lugar del tiempo de pared de una sola instancia, reflejando la naturaleza paralela de la ejecución en GPU.

2. Contabilidad del Ciclo de Vida (Carbono Incorporado): El marco extiende la contabilidad de energía operativa para incluir el carbono incorporado de la fabricación de hardware. Este costo se amortiza linealmente sobre una vida útil de hardware configurable (por defecto cinco años) y se aplica simétricamente tanto al acelerador neuronal como a la CPU de referencia. Esto asegura que la comparación cuente el impacto completo del ciclo de vida, señalando que las GPUs de alto rendimiento pueden tener una carga incorporada por instancia menor que las CPUs si se utilizan eficientemente.

3. Argumento Estructural Asintótico: El artículo demuestra (Proposición 1) que si la energía por instancia del solucionador neuronal es estrictamente menor que la de la referencia ($E_{inst}^{NN} < E_{inst}^{base}$), la relación de sus energías acumuladas converge a una constante estrictamente inferior a uno cuando $N \to \infty$. Crucialmente, este límite es independiente del costo de entrenamiento, la sobrecarga del centro de datos (PUE) o la intensidad de carbono regional, siempre que estos factores se apliquen simétricamente a ambos lados.

Instanciación Experimental y Resultados
El marco se instancia en el entorno del Problema de Ruteo de Vehículos Multi-Tarea (MTVRP) con $n=20$ clientes a través de 19 variantes del problema.

• Referencia: Búsqueda Genética Híbrida (HGS) implementada en PyVRP.
• Solucionador Neuronal: Una política aprendida entrenada en una sola GPU a través de cinco semillas.
• Métricas Clave:
  • Relación por Instancia: El solucionador neuronal consume aproximadamente 0.41 Wh por instancia en comparación con 1.32 Wh para la referencia HGS de un solo hilo (una ganancia de eficiencia de ~2.4x por instancia).
  • Costo de Entrenamiento: La energía mediana de entrenamiento fue de 121.5 Wh.
  • Punto de Cruce (AET): El cruce medido ocurre aproximadamente en $1.58 \times 10^5$ instancias desplegadas. Por encima de este volumen, el solucionador neuronal se vuelve más eficiente energéticamente en energía acumulada total.
  • Sensibilidad: Los autores analizan una superficie de sensibilidad de cinco ejes (tamaño de lote, tolerancia de calidad, hilos de referencia, nivel de hardware, semilla de entrenamiento). Descubren que, aunque el nivel de hardware y la tolerancia de calidad desplazan significativamente el valor del AET, la convergencia estructural de la relación permanece robusta.

Contribuciones Clave

1. Formalización del AET: Una métrica que cuantifica el punto de equilibrio para solucionadores neuronales bajo restricciones explícitas de calidad de solución, moviendo el debate de retórico a cuantitativo.
2. Corrección del Ciclo de Vida: La inclusión de carbono incorporado amortizado simétricamente, desafiando los métodos de contabilidad solo operativos.
3. Prueba Asintótica: Una demostración matemática de que el veredicto cualitativo (los solucionadores neuronales ganan a escala) es estructuralmente sólido e independiente de disputas de calibración sobre costos de entrenamiento o intensidad de la red.
4. Instrumentación Abierta: La liberación de protocolos de medición y scripts para reproducir el seguimiento de energía y el análisis de sensibilidad.

Significado y Afirmaciones
El artículo afirma resolver la objeción de "eficiencia energética" contra los solucionadores neuronales de OC reformulando la pregunta. Afirma que la objeción es correcta respecto a la premisa (el entrenamiento es costoso) pero incorrecta respecto a la conclusión (el método es ineficiente en neto).

• Dependencia del Régimen: Los solucionadores neuronales son menos eficientes solo por debajo del AET. Por encima del AET, el costo marginal del heurístico se compila sin límite, mientras que el costo fijo del solucionador neuronal está completamente amortizado.
• Ventaja Estructural: El artículo argumenta que la ventaja estructural de la inferencia neuronal por lotes sobre la búsqueda heurística serial implica que la brecha de eficiencia se ampliará significativamente en tamaños de problema más grandes ($n=50, 100$), donde los tiempos de búsqueda heurística escalan de forma superlineal mientras que el rendimiento neuronal permanece relativamente estable.
• Modestia: Los autores declaran explícitamente que los resultados actuales son una "configuración ilustrativa" en $n=20$. Reconocen que la relación por instancia (0.41) es moderada y que la validación empírica completa de la superficie de sensibilidad y tamaños de problema más grandes queda para trabajo futuro. El artículo no afirma que los solucionadores neuronales sean universalmente superiores, sino que proporciona el marco para determinar cuándo y bajo qué condiciones son la opción ambientalmente preferible.