IA e os Problemas Difíceis do Mundo · Ciência da computação teórica · arXiv · 2026-10-22
Seleção interpretável de planos de corte para programação linear inteira mista usando programação genética
Título original: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
Planos de corte são um ingrediente-chave em solvers de programação linear inteira mista (MILP), mas as atuais estratégias de corte artesanais são estáticas, enquanto as estratégias aprendidas baseadas em redes neurais oferecem interpretabilidade limitada e nenhuma garantia de convergência. Os autores propõem o GPSCS, o primeiro framework baseado em aprendizado que generaliza heurísticas artesanais em uma política totalmente interpretável: a programação genética evolui uma função de pontuação simbólica que classifica os cortes candidatos, e um mecanismo leve baseado em estatísticas decide de forma adaptativa quantos cortes mais bem classificados adicionar a cada rodada de separação. Avaliado no SCIP em sete classes de benchmarks sintéticos e do mundo real cujas instâncias de avaliação são em média 41 vezes mais difíceis do que as de treinamento, o GPSCS melhora o tempo médio de resolução em 6% em relação ao padrão do SCIP e alcança uma aceleração de duas vezes tanto sobre uma abordagem neural recente quanto sobre uma linha de base sem cortes.