Resumo Técnico: A Aquisição de Restrições Precisa de Melhores Benchmarks

Declaração do Problema

O campo de Aquisição de Restrições (AR) e o domínio mais amplo de Mineração de Modelos de Programação Matemática (MMPM)—que abrange a descoberta, verificação de conformidade e aprimoramento de modelos de PM utilizando artefatos de conhecimento de domínio—encontra-se atualmente impedido pela falta de benchmarks adequados. As suites de benchmark existentes (por exemplo, CSPLib, MiniZinc Challenge, MIPLIB) foram projetadas principalmente para avaliar o desempenho de solucionadores, e não algoritmos que mineram modelos a partir de conhecimento de domínio. Esses benchmarks legados sofrem de várias deficiências críticas:

• Inconsistência: Carecem de organização padronizada de arquivos, utilizam linguagens de modelagem heterogêneas e armazenam ou omitem de forma inconsistente artefatos essenciais de conhecimento de domínio (por exemplo, soluções de exemplo, contraexemplos, descrições em linguagem natural).
• Não reprodutibilidade: Protocolos experimentais frequentemente omitem detalhes cruciais relativos à geração de instâncias, limites de cardinalidade de restrições e distribuições de dados.
• Escopo Limitado: Focam predominantemente em problemas combinatórios, muitas vezes negligenciando problemas contínuos e de inteiros mistos, apesar de sua relevância prática.
• Avaliação Ad-hoc: Pesquisadores frequentemente empregam procedimentos personalizados e não documentados para gerar artefatos ausentes, tornando impossível a comparação entre estudos e impedindo a maturação dos métodos de AR além do Nível de Prontidão Tecnológica 3.

Metodologia: MPMMine

Para abordar essas lacunas, os autores introduzem o MPMMine, uma suite de benchmarks projetada especificamente para avaliar algoritmos que descobrem, validam e aprimoram modelos de PM. O desenvolvimento do MPMMine é guiado por seis princípios centrais: Consistência, Padronização, Completude, Extensibilidade, Abertura e Controle de Versão.

1. Padronização Estrutural

O MPMMine impõe uma estrutura de diretórios hierárquica uniforme de quatro camadas para todos os problemas:

1. Problema: Um diretório raiz para cada problema (por exemplo, P001).
2. Modelos de PM: Subdiretórios para diferentes codificações/formulações do problema.
3. Descrições Abstratas e Instâncias: Separação de descrições independentes de instância e instâncias de dados concretas.
4. Artefatos: Armazenamento para soluções específicas de instância, não soluções e descrições em texto.

O conjunto de dados depende exclusivamente de formatos abertos: MiniZinc (.mzn) para modelos, CommonMark (.md) para descrições em texto, JSON para metadados e .dzn para dados de instância. Uma convenção de nomenclatura estrita (por exemplo, MPMMine-P003M002I003S00055) garante a referência global única de cada arquivo.

2. Geração de Artefatos

• Soluções Exemplares: Para gerar amostras uniformes a partir de regiões viáveis, os autores empregam uma técnica de amostragem uniforme "melhor esforço". Isso envolve codificar modelos como problemas de Programação Linear (PL) ou Programação Linear de Inteiros Mistos (PLIM) e coletar soluções intermediárias encontradas pelo solucionador Gurobi (utilizando algoritmos de Ramificação e Corte e Simplex). Para evitar viés, funções objetivo aleatórias são extraídas periodicamente. Para modelos contínuos, combinações convexas de soluções existentes são construídas para preencher o interior da região viável. As restrições são apertadas em $10^{-4}$ para evitar instabilidade numérica próxima aos limites.
• Não Soluções Exemplares: Estas são geradas para se assemelhar a soluções válidas, mas contêm pequenos erros deliberados que violam restrições enquanto respeitam os domínios das variáveis. Para problemas inteiros, valores são reamostrados a partir dos domínios; para problemas contínuos, valores aleatórios são amostrados. As restrições são ligeiramente afrouxadas durante a amostragem para garantir classificação robusta.
• Descrições em Linguagem Natural: As descrições são curadas para consistência com os modelos de PM. Elas são obtidas de repositórios originais, escritas por especialistas humanos ou geradas por Modelos de Linguagem de Grande Escala (LLMs) e subsequentemente revisadas manualmente para garantir precisão.

3. Escopo e Conteúdo

A versão inicial do MPMMine compreende 16 problemas (variando de P001 a P016), incluindo tipos combinatórios, contínuos e mistos. Notavelmente, seis problemas são contínuos, abordando uma lacuna na literatura existente. Cada problema está associado a:

• Múltiplos modelos (codificações).
• Dezenas de instâncias por modelo.
• Milhares de soluções e não soluções por instância.
• Descrições em linguagem natural em inglês.

Contribuições Principais

1. Primeiro Benchmark Dedicado a MMPM: O MPMMine é apresentado como o primeiro conjunto de dados criado explicitamente para avaliar métodos de mineração de modelos de PM, distinguindo-se de benchmarks centrados em solucionadores.
2. Infraestrutura Padronizada: Fornece um framework consistente, aberto e com controle de versão que facilita a reprodutibilidade e a comparação justa entre estudos.
3. Cobertura Abrangente de Artefatos: Ao contrário de conjuntos de dados anteriores, inclui o espectro completo de artefatos de conhecimento de domínio necessários para AR: modelos estruturados, instâncias diversas, milhares de soluções/não soluções rotuladas e descrições em linguagem natural.
4. Extensibilidade: O design permite a adição transparente de novos tipos de problemas, modelos e artefatos por meio de contribuições da comunidade (pull requests).

Resultados e Validação

O artigo não apresenta resultados experimentais comparando algoritmos específicos de AR, uma vez que o benchmark é uma nova infraestrutura. Em vez disso, os "resultados" focam na validação da construção do conjunto de dados:

• Verificação de Uniformidade: A Análise de Componentes Principais (PCA) foi utilizada para visualizar distribuições de soluções e não soluções em 4D. As visualizações (Figuras 1a–1d) demonstram que os pontos amostrados preenchem uniformemente as regiões viáveis para modelos inteiros e contínuos, com variâncias explicadas variando de 31% a 52%.
• Robustez: Os procedimentos de amostragem foram testados contra métodos padrão (Monte Carlo, Hit-and-Run, Gibbs), que foram encontrados falhando ou produzindo distribuições enviesadas para os tipos de problemas-alvo. A amostragem "melhor esforço" proposta gerou com sucesso conjuntos de dados válidos.
• Precisão de Classificação: A correção da classificação de solução/não solução foi verificada usando ferramentas independentes, garantindo robustez contra imprecisões de ponto flutuante.

Significado e Alegações

Os autores afirmam que o MPMMine aborda o principal gargalo na maturação da pesquisa em Aquisição de Restrições: a ausência de uma infraestrutura de pesquisa dedicada e padronizada. Ao fornecer um ambiente consistente, aberto e rico em artefatos, o MPMMine visa:

• Habilitar experimentos reprodutíveis documentando protocolos de geração.
• Facilitar a comparabilidade entre estudos eliminando a necessidade de configurações experimentais ad-hoc.
• Apoiar o desenvolvimento de métodos texto-para-modelo e artefato-misto-para-modelo através da inclusão de descrições em linguagem natural.
• Preencher a lacuna entre pesquisa básica e aplicação prática ao cobrir problemas contínuos e mistos frequentemente negligenciados na literatura de MMPM.

O artigo conclui modestamente, reconhecendo que a coleção atual de 16 problemas é um passo inicial. O objetivo de longo prazo é escalar o conjunto de dados para pelo menos 100 problemas e lançar uma suite de software dedicada para apoiar a criação de futuras versões e avaliação algorítmica sistemática.