Resumo Técnico: OPT-Engine: Avaliação dos Limites dos LLMs em Modelagem de Otimização via Escalonamento de Complexidade

1. Formulação do Problema

Embora os Grandes Modelos de Linguagem (LLMs) tenham demonstrado capacidades promissoras na interpretação de linguagem natural e na geração de modelos matemáticos para otimização, sua aplicação em Pesquisa Operacional (PO) do mundo real permanece frágil. Benchmarks existentes frequentemente dependem de instâncias estáticas e de escala fixa ou de problemas estilo livro didático que falham em capturar a complexidade combinatória e a densidade estrutural de aplicações industriais. Além disso, existe uma lacuna significativa de desempenho entre o sucesso dos LLMs em matemática competitiva e sua capacidade de formular e resolver problemas de otimização complexos, particularmente à medida que a escala do problema aumenta. A comunidade carece de um framework rigoroso e extensível para sondar sistematicamente os limites da formulação automatizada de problemas e para distinguir entre a eficácia de diferentes paradigmas de raciocínio (Raciocínio em Texto Puro vs. Raciocínio Integrado a Solvers) sob escalonamento controlado de complexidade.

2. Metodologia: O Framework OPT-Engine

Para abordar essas lacunas, os autores introduzem o OPT-Engine, um framework de benchmark extensível projetado para gerar instâncias de problemas com complexidade quantificável e controlável.

2.1. Taxonomia do Benchmark

O OPT-Engine abrange dez classes canônicas de problemas de PO, divididas em dois níveis:

• Programação Linear (PL): Problemas de Inventário, Alocação de Portfólio, Produção, Transporte e Controle de Poluição.
• Programação Mista-Inteira (PMI): Problema do Caixeiro Viajante (TSP), Mochila, Empacotamento em Binários, Agendamento de Job-Shop e Fluxo de Rede de Custo Mínimo.

2.2. Pipeline de Geração Escalável

O framework emprega um pipeline de quatro estágios para gerar instâncias de problemas verificáveis:

1. Geração de Instância Numérica: Um gerador $G$ mapeia uma classe de problema e um vetor de controle de dificuldade $\theta$ (por exemplo, número de cidades $N_{cities}$ para TSP) para uma instância numérica. Crucialmente, este estágio utiliza um template de solver para calcular a solução ótima de verdade e o valor objetivo.
2. Construção do Problema Canônico: A instância numérica é mapeada para uma declaração formal e canônica do problema $s_c$ usando um template estruturado.
3. Aumento do Problema: Um agente LLM dedicado reescreve a declaração canônica em narrativas diversas e ricas em contexto ($s_r$) para simular cenários do mundo real, preservando a estrutura matemática subjacente.
4. Validação da Instância: Um módulo de validação, combinando um LLM como Juiz e verificadores baseados em regras, garante que as narrativas reescritas mantenham equivalência estrutural e consistência numérica com a verdade fundamental.

2.3. Paradigmas de Avaliação

O framework avalia duas abordagens principais de raciocínio:

• Raciocínio em Texto Puro (PTR): O LLM usa Cadeia de Pensamento (CoT) para deduzir a solução ponta a ponta sem ferramentas externas.
• Raciocínio Integrado a Solvers (SIR): O LLM traduz o problema em código executável (por exemplo, Gurobi/COPT), que é então resolvido por um solver determinístico externo.
• PTR Computacional (CompPTR): Uma abordagem intermediária onde o LLM usa primitivas Python para cálculos locais, mas é restrito de invocar solvers de otimização globais.

3. Resultados Chave

3.1. Escalonamento e Robustez

• Superioridade do SIR: À medida que a complexidade do problema escala (aumentando dimensões e restrições), o SIR mantém alta precisão ou exibe apenas degradação menor. Em contraste, o PTR sofre de uma lacuna crítica de robustez, com o desempenho colapsando significativamente à medida que o tamanho do problema aumenta.
• Efeitos da Escala do Modelo: Embora modelos menores (por exemplo, Qwen3-4B) possam superar o SIR em baixa complexidade devido a falhas na geração de código no SIR, essa vantagem é transitória. Com Aprendizado por Reforço a partir de Recompensas Verificáveis (RLVR) para melhorar a geração de código, o SIR supera consistentemente o PTR em todas as dimensões.

3.2. Modos de Falha Mecanísticos

• Aritmética vs. Estrutural: A decomposição de erros revela que as falhas do PTR são de dupla face: à medida que a complexidade cresce, os modelos primeiro falham em satisfazer restrições lógicas globais (colapso de viabilidade) e subsequentemente falham em alcançar precisão numérica.
• Limitações dos Auxílios Computacionais: Embora o CompPTR (adicionando ferramentas Python ao PTR) mitigue erros aritméticos e melhore a viabilidade local, ele falha em impor restrições de otimização globais. O modelo não consegue internalizar dependências combinatórias holísticas, levando a uma degradação de desempenho semelhante à do PTR padrão em escalas altas.

3.3. Diagnóstico de Gargalos

Os autores conduziram experimentos diagnósticos para isolar as principais fontes de falha:

• Complexidade Linguística: Variar a perplexidade (PPL) das descrições dos problemas teve um impacto negligenciável na precisão.
• Perturbações do Objetivo: Adicionar deslocamentos constantes às funções objetivo não degradou significativamente o desempenho.
• Aumento de Restrições: A introdução de restrições adicionais, matematicamente diretas (por exemplo, "exatamente uma de duas estradas deve ser incluída") causou uma queda substancial e consistente na precisão em todas as classes de problemas e paradigmas.

Conclusão sobre Gargalos: O principal gargalo para os LLMs SOTA atuais em otimização não é a compreensão linguística ou a formulação do objetivo, mas a formulação automatizada de restrições. Os modelos lutam para generalizar além de formulações canônicas e estilo livro didático para lidar com variações ricas e pesadas em restrições encontradas em aplicações do mundo real.

4. Contribuições

1. Framework OPT-Engine: Um benchmark abrangente e extensível que permite controle fino e escalável sobre estrutura matemática e linguagem para avaliar LLMs em modelagem de otimização.
2. Avaliação de Paradigmas: Evidência empírica demonstrando que o PTR carece de robustez em escala, enquanto o SIR é essencial para manter a precisão em cenários de alta complexidade.
3. Análise de Integração de Ferramentas: Descobertas de que, embora ferramentas computacionais externas auxiliem em cálculos locais, elas não resolvem a incapacidade fundamental dos LLMs de aderir a restrições de otimização globais sem integração de solver.
4. Identificação de Gargalos: Apontar a formulação de restrições como o ponto crítico de falha, distinguindo-a da compreensão do problema ou perturbação do objetivo.

5. Significado e Alegações

O artigo alega que o OPT-Engine fornece um rigor diagnóstico necessário para mover o campo além de demonstrações isoladas e comparações lado a lado em conjuntos de dados estáticos. Ao estabelecer um protocolo para escalonamento de complexidade, o framework revela que os LLMs atuais dependem fortemente de padrões de dados de treinamento canônicos e falham em raciocinar robustamente sobre combinações novas de restrições.

Os autores afirmam que essas descobertas esclarecem as limitações dos paradigmas atuais e oferecem um roteiro estruturado para o desenvolvimento de LLMs de próxima geração. Eles enfatizam que, para que a modelagem de otimização seja viável em ambientes industriais, os modelos devem ir além de "ilusões de raciocínio" e alcançar fidelidade na formulação de restrições. O artigo conclui reconhecendo que, embora se concentre em soluções exatas (PL/PMI), trabalhos futuros devem explorar heurísticas para problemas NP-difíceis e estender o framework para domínios não lineares e estocásticos. O código e os dados são liberados para facilitar essa pesquisa futura.