Resumo Técnico: Forge: Representações de Otimização Fundacionais a partir de Embeddings de Grafos

1. Declaração do Problema

Problemas de otimização combinatória (CO), particularmente Programação Inteira Mista (MIP), são fundamentais para a ciência e engenharia, mas permanecem computacionalmente caros para resolver. Embora o aprendizado de máquina (ML) ofereça alternativas promissoras, as abordagens atuais baseadas em aprendizado sofrem de limitações significativas de escalabilidade e generalização:

• Dependência de Dados: O treinamento normalmente requer a resolução de um grande número de instâncias difíceis para gerar dados rotulados, o que acarreta altos custos computacionais e depende dos próprios solvers que os pesquisadores visam acelerar.
• Falta de Generalização: Os métodos existentes frequentemente treinam modelos dedicados para distribuições de problemas, tarefas ou tamanhos específicos. Eles falham em generalizar entre diferentes domínios de problemas (ex: Set Cover vs. Leilão Combinatório) ou tipos de tarefas (ex: geração de cortes vs. orientação de busca).
• Limitações Estruturais: A maioria dos métodos de CO baseia-se em Redes Neurais de Grafos (GNNs), que capturam efetivamente informações locais de variáveis-restrições, mas têm dificuldade em codificar uma estrutura global de instância significativa devido à inerente tendência de localidade.

O artigo postula a necessidade de uma representação de otimização fundacional: um modelo pré-treinado e de propósito geral, capaz de gerar embeddings de MIP que se generalizem através de tarefas, problemas e tamanhos, treinado de forma não supervisionada sem a necessidade de soluções ótimas.

2. Metodologia: O Framework Forge

Forge (Foundational Optimization Representations from Graph Embeddings) é um framework que pré-treina um autoencoder de grafo com quantização vetorial em uma coleção diversificada de instâncias de MIP. Ele se inspira em modelos fundacionais de Processamento de Linguagem Natural (NLP) e Visão Computacional (CV).

Arquitetura Central

O framework opera através das seguintes etapas (Figura 1):

1. MIP-to-BP (Representação Bipartida): Instâncias de MIP são representadas como grafos bipartidos onde os nós são variáveis e restrições.
   • Recursos de Nó: Diferente de trabalhos anteriores que dependem de recursos gerados pelo solver (ex: de árvores de branch-and-bound), o Forge usa apenas propriedades básicas de entrada: sentido da restrição (>, <, =) e valores de RHS para restrições; tipo de variável, limites e coeficientes de objetivo para variáveis. Isso garante que o modelo não dependa da resolução da instância.
2. BP-to-GNN: Uma GNN baseada em GraphSAGE (duas camadas) processa o grafo bipartido para gerar embeddings contínuos para cada nó.
3. Codebook de Quantização Vetorial (O "Vocabulário"): Para abordar a incapacidade da GNN de capturar a estrutura global, os embeddings contínuos passam por um quantizador vetorial. Isso mapeia cada nó para um código discreto de um codebook aprendível de tamanho $k$ (atuando como um vocabulário).
   • Esta etapa preserva a informação estrutural global ao criar uma distribuição de códigos discretos pela instância, de forma análoga às distribuições de tokens em modelos de linguagem.
4. Reconstrução (Autoencoder): Os códigos discretos são mapeados de volta para codewords e passados por decoders para reconstruir os recursos originais dos nós e os pesos das arestas.
5. Função de Perda: O modelo é treinado de forma não supervisionada para minimizar:
   • Perda de reconstrução (recursos de nó e arestas).
   • Perda de codebook (movendo codewords em direção aos embeddings).
   • Perda de comprometimento (movendo embeddings em direção aos codewords).

Representações

Uma vez treinado, o Forge produz dois níveis de representações:

• Local: Codewords discretos para variáveis e restrições individuais.
• Global: Um embedding de nível de instância derivado da distribuição de frequência dos códigos atribuídos ao longo de todo o grafo. A dimensão do embedding é igual ao tamanho do vocabulário ($|codebook|$).

3. Principais Contribuições

O artigo descreve cinco contribuições primárias:

1. Passo de Modelo Fundacional: Introdução do Forge, um único modelo pré-treinado que gera embeddings de MIP tanto em nível de instância quanto em nível refinado (variável/restrição) sem supervisão.
2. Generalização Não Supervisionada: Demonstração de que os embeddings do Forge podem agrupar instâncias não vistas através de diversos domínios de problemas e níveis de dificuldade com alta precisão, superando recursos estáticos e leituras (readouts) padrão de GNN.
3. Adaptabilidade Supervisionada: Prova de que o mesmo modelo pré-treinado pode ser ajustado (fine-tuned) com dados minimamente rotulados e baratos para tarefas drasticamente diferentes (previsão de gap de integridade e orientação de busca) através de variados tamanhos de problema.
4. Integração com Solver: Integração bem-sucedida das previsões do Forge no Gurobi, um solver comercial, demonstrando melhorias consistentes nos gaps primais através de múltiplos tipos de problemas.
5. Aumento de ML: Melhoria de métodos de aprendizado de estado da arte (especificamente Li et al., 2025 e PS-Gurobi) ao concatenar embeddings do Forge, resultando em ganhos significativos de desempenho em instâncias não vistas.

4. Resultados Experimentais

Agrupamento Não Supervisionado

• Configuração: Treinado em 1.800 instâncias de MIPLIB; testado em 1.000 instâncias não vistas de D-MIPLIB e strIPlib cobrindo 21 pares de domínio-dificuldade.
• Métrica: Informação Mútua Normalizada (NMI) para precisão de agrupamento.
• Desempenho: O Forge alcançou um NMI de 0,953, superando significativamente o Mean Readout (0,726) e o Label Propagation (0,790). Visualizações (PaCMAP) mostraram clusters distintos para cada tipo de problema e um gradiente claro de fácil para difícil, apesar de o modelo nunca ter visto essas instâncias específicas durante o treinamento.

Tarefa I: Previsão de Integrality Gap (Geração de Pseudo-Corte)

• Objetivo: Prever o integrality gap para gerar um pseudo-corte para o nó raiz, estreitando o limite da relaxação LP.
• Treinamento: Ajustado (fine-tuned) em 450 instâncias (CA, SC, GIS) com rótulos gerados pelo Gurobi (timeout de 120s), evitando a otimalidade total.
• Resultados:
  • Em instâncias de teste "muito difíceis" (incluindo MVC, que não foi vista no ajuste fino), o Forge alcançou desvios absolutos médios de 12–19% entre tipos de problemas.
  • Impacto no Solver: Integrar pseudo-cortes do Forge no Gurobi reduziu o gap primal em até 85% (ex: ganho de 84,52% no Generalized Independent Set) comparado ao Gurobi sozinho.
  • Comparação: Superou o método de SOTA de Li et al. (2025) (18,63% de desvio vs. 20,14%) em 17.500 instâncias não vistas sem treinamento adicional.

Tarefa II: Orientação de Busca

• Objetivo: Prever quais variáveis provavelmente estarão na solução ótima para guiar a busca de branch-and-bound.
• Treinamento: Ajustado em 700 instâncias usando uma combinação de Binary Cross-Entropy (BCE) e Triplet Loss. Os rótulos foram derivados de soluções viáveis encontradas em 5 minutos (sem necessidade de otimalidade).
• Resultados:
  • Impacto no Solver: O Gurobi com orientação de busca do Forge alcançou até 48,75% de melhoria no gap primal e até 35% de aceleração no tempo de convergência em instâncias médias.
  • Aumento de ML: Quando usado para aumentar o PS-Gurobi (um método de orientação de busca baseado em aprendizado de SOTA), os embeddings do Forge reduziram o gap primal em mais de 40% (Combinatorial Auction) e 50% (Generalized Independent Set).

5. Significância e Alegações

O artigo afirma que o Forge representa um passo significativo em direção aos modelos fundacionais para otimização. Sua significância reside em:

• Quebrar a Dependência do Solver: Ele aprende representações estruturais sem exigir acesso a soluções ótimas ou estados internos do solver durante o pré-treinamento, abordando o problema do "ovo e da galinha" de precisar de solvers para treinar solvers.
• Representação Universal: Demonstra que um único modelo pode generalizar através de disparatados tipos de problemas (ex: Set Cover, Combinatorial Auction, Vertex Cover) e tipos de tarefas (previsão de gap, orientação de busca), uma capacidade anteriormente limitada a modelos específicos de problema ou tarefa.
• Utilidade Prática: O framework não é meramente teórico; ele se integra diretamente com solvers comerciais e melhora pipelines de ML existentes, oferecendo ganhos imediatos e mensuráveis na eficiência de resolução.
• Ciência Aberta: Os autores liberam o código de treinamento, pesos pré-treinados e embeddings para fomentar mais pesquisas em aprendizado de representação para otimização.

Os autores permanecem modestos quanto às limitações, observando que a escala atual (3,25M de parâmetros) é pequena comparada a outros modelos fundacionais, a semântica do "vocabulário" aprendido é inexplorada, e as integrações atuais são "one-shot" em vez de iterativas ao longo da árvore de branch-and-bound. Eles sugerem que trabalhos futuros podem estender esses princípios para Problemas de Satisfação de Restrições (CSP) e SAT.