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

Resumo Técnico: Um Limiar de Eficiência Amortizado para Comparar Solucionadores Neurais e Heurísticos em Otimização Combinatória

Enunciado do Problema
O artigo aborda uma crítica prevalente em pesquisa operacional e IA Verde: a de que solucionadores neurais de otimização combinatória (OC) são inerentemente menos eficientes energeticamente do que metaheurísticas tradicionais baseadas em CPU devido aos custos energéticos substanciais associados ao treinamento em GPUs. Os autores argumentam que essa crítica baseia-se em um passo inferencial falho. Ela trata incorretamente o grande custo inicial fixo de treinamento como uma desqualificação permanente, ignorando o fato de que os solucionadores neurais incorrem em um custo de inferência por instância muito pequeno e amortizável, ao passo que as metaheurísticas incorrem em um custo marginal constante para cada instância resolvida. O artigo postula que esses dois perfis de custo (fixo versus marginal) não são comparáveis como escalares, mas devem ser comparados sobre um volume específico de implantação.

Metodologia: O Limiar de Eficiência Amortizado (AET)
Para formalizar essa comparação, o artigo introduz o Limiar de Eficiência Amortizado (AET), um quadro quantitativo definido por três componentes centrais:

1. Definição de AET: O AET é o volume de implantação ($N$) no qual a energia cumulativa (ou carbono) de um solucionador neural ($M$) iguala-se à de um solucionador heurístico de base ($B$). É calculado como:
   $$AET = \frac{E_{train}(M)}{\max(E_{inst}^{base} - E_{inst}^{NN}, \epsilon)}$$
   Este cálculo está sujeito a uma restrição de viabilidade de qualidade: a lacuna de otimalidade esperada do solucionador neural não deve exceder a lacuna da base em mais de uma tolerância definida pelo usuário $\delta$. Essa restrição impede que solucionadores "rápidos, mas incorretos" reduzam artificialmente o limiar.

   • $E_{train}(M)$ inclui o custo cumulativo de todas as varreduras de hiperparâmetros, execuções falhas e protótipos, não apenas do modelo final convergido.
   • $E_{inst}^{NN}$ é a energia de inferência por instância, calculada com base no rendimento em lote ($\tau_{NN}$) e não no tempo de parede de uma única instância, refletindo a natureza paralela da execução em GPU.

2. Contabilidade do Ciclo de Vida (Carbono Embutido): O quadro estende a contabilidade de energia operacional para incluir o carbono embutido da fabricação de hardware. Esse custo é amortizado linearmente ao longo de uma vida útil de hardware configurável (padrão de cinco anos) e aplicado simetricamente tanto ao acelerador neural quanto à CPU de base. Isso garante que a comparação considere o impacto de todo o ciclo de vida, observando que GPUs de alto rendimento podem ter um ônus embutido por instância menor do que CPUs se utilizadas de forma eficiente.

3. Argumento Estrutural Assintótico: O artigo prova (Proposição 1) que, se a energia por instância do solucionador neural for estritamente menor do que a da base ($E_{inst}^{NN} < E_{inst}^{base}$), a razão de suas energias cumulativas converge para uma constante estritamente inferior a um quando $N \to \infty$. Crucialmente, esse limite é independente do custo de treinamento, sobrecarga do datacenter (PUE) ou intensidade de carbono regional, desde que esses fatores se apliquem simetricamente a ambos os lados.

Instanciação Experimental e Resultados
O quadro é instanciado no ambiente de Problema de Roteamento de Veículos Multi-Tarefa (MTVRP) com $n=20$ clientes em 19 variantes de problema.

• Base: Busca Genética Híbrida (HGS) implementada em PyVRP.
• Solucionador Neural: Uma política aprendida treinada em uma única GPU em cinco sementes.
• Métricas Principais:
  • Razão por Instância: O solucionador neural consome aproximadamente 0,41 Wh por instância, comparado a 1,32 Wh para a base HGS de thread única (um ganho de eficiência de ~2,4x por instância).
  • Custo de Treinamento: A energia mediana de treinamento foi de 121,5 Wh.
  • Ponto de Interseção (AET): A interseção medida ocorre em aproximadamente $1,58 \times 10^5$ instâncias implantadas. Acima desse volume, o solucionador neural torna-se mais eficiente energeticamente em energia cumulativa total.
  • Sensibilidade: Os autores analisam uma superfície de sensibilidade de cinco eixos (tamanho do lote, tolerância de qualidade, threads da base, nível de hardware, semente de treinamento). Eles constatam que, embora o nível de hardware e a tolerância de qualidade desloquem significativamente o valor do AET, a convergência estrutural da razão permanece robusta.

Contribuições Principais

1. Formalização do AET: Uma métrica que quantifica o ponto de equilíbrio para solucionadores neurais sob restrições explícitas de qualidade de solução, movendo o debate de retórico para quantitativo.
2. Correção do Ciclo de Vida: A inclusão de carbono embutido amortizado simetricamente, desafiando métodos de contabilidade apenas operacionais.
3. Prova Assintótica: Uma demonstração matemática de que o veredito qualitativo (solucionadores neurais vencem em escala) é estruturalmente sólido e independente de disputas de calibração sobre custos de treinamento ou intensidade da rede.
4. Instrumentação Aberta: A liberação de protocolos de medição e scripts para reproduzir o rastreamento de energia e a análise de sensibilidade.

Significado e Alegações
O artigo alega resolver a objeção de "eficiência energética" contra solucionadores neurais de OC ao reformular a questão. Ele afirma que a objeção está correta quanto à premissa (o treinamento é caro), mas incorreta quanto à conclusão (o método é ineficiente em líquido).

• Dependência de Regime: Os solucionadores neurais são menos eficientes apenas abaixo do AET. Acima do AET, o custo marginal da heurística compõe-se sem limites, enquanto o custo fixo do solucionador neural é totalmente amortizado.
• Vantagem Estrutural: O artigo argumenta que a vantagem estrutural da inferência neural em lote sobre a busca heurística serial implica que a lacuna de eficiência se ampliará significativamente em tamanhos de problema maiores ($n=50, 100$), onde os tempos de busca heurística escalam de forma superlinear, enquanto o rendimento neural permanece relativamente estável.
• Modéstia: Os autores afirmam explicitamente que os resultados atuais são uma "configuração ilustrativa" em $n=20$. Eles reconhecem que a razão por instância (0,41) é moderada e que a validação empírica completa da superfície de sensibilidade e de tamanhos de problema maiores fica para trabalhos futuros. O artigo não alega que solucionadores neurais são universalmente superiores, mas fornece o quadro para determinar quando e sob quais condições eles são a escolha ambientalmente preferível.