Resumo Técnico: EvoOptiGraph

Definição do Problema

Automatizar a tradução de problemas de decisão em linguagem natural para modelos matemáticos de otimização formais (especificamente, Programação Linear Inteira Mista, ou MILP) continua sendo um desafio significativo para Grandes Modelos de Linguagem (LLMs). As abordagens atuais enfrentam duas limitações primárias:

1. Falta de Diversidade Estrutural nos Dados de Treinamento: Benchmarks existentes (ex: NL4Opt, MAMO) cobrem apenas um subconjunto estreito de formulações de otimização válidas. Pipelines de síntese de dados geralmente dependem de templates fixos com perturbações de parâmetros, falhando em gerar a ampla diversidade estrutural necessária para uma generalização robusta.
2. Pipelines de Treinamento Estáticos: A maioria das configurações de treinamento utiliza um conjunto de dados congelado, construído antes do treinamento do modelo. Esse desacoplamento impede que o sistema identifique regimes estruturais específicos onde o modelo falha e gere novos instâncias para visar essas fraquezas.

Metodologia: EvoOptiGraph

Os autores propõem o EvoOptiGraph, um framework de coevolução orientado por fraquezas que acopla a geração de dados e o treinamento do modelo através de uma representação estrutural explícita. O framework opera em um ciclo fechado composto por três componentes principais:

1. Representação Estrutural Baseada em Grafos

Cada MILP é representado como um grafo bipartido atribuído $G = (V, E, A)$:

• Nós: Um nó por variável de decisão ($V_{var}$) e um por restrição, além de um nó de objetivo dedicado ($V_{con}$).
• Arestas: Conectam variáveis a restrições/objetivos onde os coeficientes são não-zero; os pesos das arestas armazenam os valores dos coeficientes.
• Atributos: Os nós armazenam metadados como limites de variáveis, tipos (inteiro/contínuo/binário), sentidos das restrições e valores do lado direito (RHS).
  Esta representação permite a compilação determinística em código de solver (ex: Gurobi) e suporta operações genéticas que preservam a validade.

2. Geração de Dados Controlável via Evolução de Grafos

Em vez de perturbar texto ou parâmetros, o EvoOptiGraph evolui instâncias de otimização diretamente no espaço de grafos usando operadores genéticos:

• Crossover: Troca subgrafos compatíveis entre instâncias pai (ex: combinando uma restrição de programação de produção com uma restrição de mochila). Crossover entre classes diferentes é permitido para aumentar a diversidade estrutural.
• Mutação: Opera em três níveis:
  • Parâmetro: Perturba coeficientes, limites e valores de RHS.
  • Estrutural: Insere, deleta ou modifica variáveis/restrições enquanto preserva a linearidade.
  • Escala: Altera o tamanho do problema (ex: expandindo nós de oferta/demanda).
• Função de Aptidão (Fitness): Os candidatos são pontuados com base em:
  • Dificuldade: Derivada de estatísticas do solver (tempo de solução, nós de branch-and-bound).
  • Diversidade: Medida pela Distância de Edição de Grafo (GED) em relação à população atual.
  • Alinhamento de Fraqueza: Similaridade de cosseno entre as características estruturais da instância e o vetor de fraqueza atual do modelo.

3. Treinamento de Modelo em Dois Estágios e Ciclo de Coevolução

O processo de treinamento alterna entre o ajuste do modelo e a evolução dos dados:

1. Aquecimento (SFT): O LLM base passa por ajuste fino supervisionado (Supervised Fine-Tuning) em uma população inicial de instâncias verificadas, geradas a partir de geradores semente especialistas.
2. Análise de Fraqueza: O modelo atual é avaliado em um conjunto de validação retido. Um classificador XGBoost prevê a falha com base em características estruturais derivadas do grafo. Valores SHAP são computados nos casos de erro para gerar um vetor de fraqueza ($w$) que destaca as propriedades estruturais mais associadas às falhas do modelo.
3. Aprendizado por Reforço Orientado por Fraquezas (RLVR): O gerador evolutivo é enviesado para instâncias cujas características estruturais se alinham com o vetor de fraqueza ($\tilde{f}_{weak}$). O modelo é então atualizado usando Aprendizado por Reforço com Recompensas Verificáveis (RLVR).
   • Recompensas: Uma soma de múltiplos estágios baseada em executabilidade de código, viabilidade da solução, proximidade ao objetivo real (dentro de 10% de erro relativo) e correção exata.
   • Otimização: O Group Relative Policy Optimization (GRPO) é usado para atualizar a política, equilibrando a maximização da recompensa com a regularização de divergência KL contra a referência SFT.

Principais Contribuições

1. Framework de Coevolução de Ciclo Fechado: Ao contrário de métodos anteriores que separam a síntese de dados da otimização do modelo, o EvoOptiGraph os vincula via análise de fraqueza em nível de grafo, permitindo que a distribuição de treinamento se adapte dinamicamente aos modos de falha em evolução do modelo.
2. Gerador Controlável Baseado em Grafos: O framework realiza crossover e mutação diretamente em grafos bipartidos atribuídos, permitindo a evolução ao nível estrutural além de simples perturbações de parâmetros. Isso suporta a exploração sistemática de diversas estruturas de otimização.
3. Adaptação Orientada por Fraquezas com Feedback Verificável: O sistema diagnostica padrões de erro estruturais usando características de grafo e evolui novas instâncias visando especificamente essas falhas, otimizando o modelo com recompensas verificáveis baseadas em solver.

Resultados Experimentais

O framework foi avaliado em seis benchmarks públicos: NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR e IndustryOR.

• Desempenho: O EvoOptiGraph (usando um backbone de 8B parâmetros) alcançou uma precisão média macro de Pass@1 de 78,1%, superando modelos generalistas maiores (ex: GPT-4o, DeepSeek-V3), métodos agentes (ex: OptiMUS, Chain-of-Experts) e baselines especializados ajustados (ex: ORLM, LLMOPT).
• Diversidade de Dados: As instâncias geradas pelo EvoOptiGraph mostraram uma similaridade estrutural de 66,93% com os tipos de problemas originais, significativamente menor (indicando maior diversidade) do que a similaridade de 93,04% alcançada pelo método baseado em texto OptMATH.
• Estudos de Ablação: Remover o ciclo de coevolução (apenas SFT ou apenas RL) resultou em quedas de desempenho de 9,6% e 14,7%, respectivamente, confirmando que tanto o nivelamento supervisionado inicial quanto a geração adaptativa orientada por fraquezas são críticos.
• Generalização: O modelo demonstrou uma generalização robusta, particularmente em datasets estruturalmente desafiadores como ComplexOR e MAMO-Complex, sugerindo que a evolução de dados direcionada é mais eficaz do que simplesmente escalar o tamanho do modelo.

Significância e Alegações

O artigo alega que a coevolução direcionada de dados-modelo é uma estratégia eficaz para melhorar LLMs em tarefas de modelagem de otimização. Ao representar MILPs como grafos e usá-los para impulsionar tanto a geração de dados quanto o diagnóstico de falhas, o EvoOptiGraph cria um loop de autoaperfeiçoamento que atualiza continuamente a distribuição de treinamento para abordar os pontos cegos específicos do modelo.

Os autores enfatizam que sua abordagem demonstra que a evolução de dados estruturais pode render melhores resultados do que simplesmente aumentar a escala do modelo ou depender de conjuntos de dados estáticos. O framework consegue unir o espaço de hipóteses de formulações de otimização válidas com a capacidade real do modelo, fornecendo um caminho para pipelines de treinamento mais adaptáveis para o raciocínio formal e pesquisa operacional.

Limitações Reconhecidas:

• O framework atual é limitado a MILPs e à cobertura dos geradores semente disponíveis.
• A verificação torna-se computacionalmente cara para instâncias maiores.
• O vetor de fraqueza serve como um sinal de priorização prático, em vez de um relato causal dos erros.