Resumen Técnico: EvoOptiGraph

Declaración del Problema

Automatizar la traducción de problemas de decisión en lenguaje natural a modelos de optimización matemática formal (específicamente, Programación Lineal Entera Mixta, o MILP) sigue siendo un desafío significativo para los Modelos de Lenguaje de Gran Escala (LLM). Los enfoques actuales enfrentan dos limitaciones primarias:

1. Falta de Diversidad Estructural en los Datos de Entrenamiento: Los benchmarks existentes (p. ej., NL4Opt, MAMO) cubren un subconjunto estrecho de formulaciones de optimización válidas. Las canalizaciones de síntesis de datos suelen depender de plantillas fijas con perturbaciones de parámetros, lo que impide generar la amplia diversidad estructural requerida para una generalización robusta.
2. Canalizaciones de Entrenamiento Estáticas: La mayoría de las configuraciones de entrenamiento utilizan un conjunto de datos congelado construido antes del entrenamiento del modelo. Este desacoplamiento impide que el sistema identifique regímenes estructurales específicos donde el modelo falla y genere nuevos casos para atacar esas debilidades.

Metodología: EvoOptiGraph

Los autores proponen EvoOptiGraph, un marco de coevolución impulsado por debilidades que acopla la generación de datos y el entrenamiento del modelo a través de una representación estructural explícita. El marco opera en un bucle cerrado que comprende tres componentes principales:

1. Representación Estructural Basada en Grafos

Cada MILP se representa como un grafo bipartito atribuido $G = (V, E, A)$:

• Nodos: Un nodo por variable de decisión ($V_{var}$) y uno por restricción más un nodo de objetivo dedicado ($V_{con}$).
• Aristas: Conectan variables con restricciones/objetivos donde los coeficientes son distintos de cero; los pesos de las aristas almacenan los valores de los coeficientes.
• Atributos: Los nodos almacenan metadatos como límites de variables, tipos (entero/continuo/binario), sentidos de las restricciones y valores del lado derecho (RHS).
  Esta representación permite una compilación determinista en código de solver (p. ej., Gurobi) y soporta operaciones genéticas que preservan la validez.

2. Generación de Datos Controlable mediante Evolución de Grafos

En lugar de perturbar texto o parámetros, EvoOptiGraph evoluciona instancias de optimización directamente en el espacio de grafos utilizando operadores genéticos:

• Crossover (Cruce): Intercambia subgrafos compatibles entre instancias progenitoras (p. ej., combinando una restricción de programación de producción con una restricción de mochila). Se permite el cruce entre clases para aumentar la diversidad estructural.
• Mutación: Opera en tres niveles:
  • Parámetro: Perturba coeficientes, límites y valores RHS.
  • Estructural: Inserta, elimina o modifica variables/restricciones manteniendo la linealidad.
  • Escala: Cambia el tamaño del problema (p. ej., expandiendo nodos de oferta/demanda).
• Función de Aptitud (Fitness): Los candidatos se califican según:
  • Dificultad: Derivada de estadísticas del solver (tiempo de resolución, nodos de branch-and-bound).
  • Diversidad: Medida por la Distancia de Edición de Grafos (GED) respecto a la población actual.
  • Alineación con Debilidades: Similitud de coseno entre las características estructurales de la instancia y el vector de debilidad actual del modelo.

3. Entrenamiento de Modelo en Dos Etapas y Bucle de Coevolución

El proceso de entrenamiento alterna entre el ajuste del modelo y la evolución de los datos:

1. Calentamiento (SFT): El LLM base es ajustado mediante aprendizaje supervisado (fine-tuning) sobre una población inicial de instancias verificadas generadas a partir de generadores semilla expertos.
2. Análisis de Debilidades: El modelo actual se evalúa en un conjunto de validación mantenido aparte. Un clasificador XGBoost predice fallos basándose en características estructurales derivadas del grafo. Se calculan los valores SHAP sobre los casos de error para generar un vector de debilidad ($w$) que destaca las propiedades estructurales más asociadas con los fallos del modelo.
3. Aprendizaje por Refuerzo Impulsado por Debilidades (RLVR): El generador evolutivo se sesga hacia instancias cuyas características estructurales se alinean con el vector de debilidad ($\tilde{f}_{weak}$). El modelo se actualiza entonces mediante Aprendizaje por Refuerzo con Recompensas Verificables (RLVR).
   • Recompensas: Una suma de múltiples etapas basada en la ejecutabilidad del código, la factibilidad de la solución, la proximidad al objetivo de la verdad de campo (dentro de un error relativo del 10%) y la corrección exacta.
   • Optimización: Se utiliza la Optimización de Política Relativa de Grupo (GRPO) para actualizar la política, equilibrando la maximización de la recompensa con la regularización de la divergencia KL contra la referencia de SFT.

Principales Contribuciones

1. Marco de Coevolución de Bucle Cerrado: A diferencia de métodos anteriores que separan la síntesis de datos de la optimización del modelo, EvoOptiGraph los vincula mediante el análisis de debilidades a nivel de grafo, permitiendo que la distribución de entrenamiento se adapte dinámicamente a los modos de fallo en evolución del modelo.
2. Generador Controlable Basado en Grafos: El marco realiza cruces y mutaciones directamente en grafos bipartitos atribuidos, permitiendo la evolución a nivel estructural más allá de las simples perturbaciones de parámetros. Esto soporta la exploración sistemática de diversas estructuras de optimización.
3. Adaptación Impulsada por Debilidades con Retroalimentación Verificable: El sistema diagnostica patrones de error estructural utilizando características de grafos y evoluciona nuevas instancias dirigidas específicamente a esos fallos, optimizando el modelo con recompensas verificables basadas en solvers.

Resultados Experimentales

El marco fue evaluado en seis benchmarks públicos: NL4Opt, MAMO (Easy/Complex), NLP4LP, ComplexOR e IndustryOR.

• Desempeño: EvoOptiGraph (utilizando un backbone de 8B parámetros) alcanzó una exactitud macro-promedio Pass@1 del 78.1%, superando a modelos generalistas más grandes (p. ej., GPT-4o, DeepSeek-V3), métodos agénticos (p. ej., OptiMUS, Chain-of-Experts) y líneas base especializadas ajustadas (p. ej., ORLM, LLMOPT).
• Diversidad de Datos: Las instancias generadas por EvoOptiGraph mostraron una similitud estructural del 66.93% con los tipos de problemas originales, significativamente menor (indicando mayor diversidad) que la similitud del 93.04% lograda por el método basado en texto OptMATH.
• Estudios de Ablación: Eliminar el bucle de coevolución (solo SFT o solo RL) resultó en caídas de rendimiento del 9.6% y 14.7% respectivamente, confirmando que tanto el anclaje supervisado inicial como la generación adaptativa impulsada por debilidades son críticos.
• Generalización: El modelo demostró una generalización robusta, particularmente en conjuntos de datos estructuralmente desafiantes como ComplexOR y MAMO-Complex, sugiriendo que la evolución de datos dirigida es más efectiva que simplemente escalar el tamaño del modelo.

Significado y Reivindicaciones

El artículo sostiene que la coevolución dirigida de datos-modelo es una estrategia efectiva para mejorar los LLM en tareas de modelado de optimización. Al representar los MILP como grafos y usarlos para impulsar tanto la generación de datos como el diagnóstico de fallos, EvoOptiGraph crea un bucle de automejora que actualiza continuamente la distribución de entrenamiento para abordar los puntos ciegos específicos del modelo.

Los autores enfatizan que su enfoque demuestra que la evolución de datos estructurales puede producir mejores resultados que simplemente aumentar la escala del modelo o depender de conjuntos de datos estáticos. El marco logra cerrar la brecha entre el espacio de hipótesis de las formulaciones de optimización válidas y la capacidad real del modelo, proporcionando una vía hacia canalizaciones de entrenamiento más adaptativas para el razonamiento formal y la investigación de operaciones.

Limitaciones Reconocidas:

• El marco actual está limitado a MILP y la cobertura de los generadores semilla disponibles.
• La verificación se vuelve computacionalmente costosa para instancias más grandes.
• El vector de debilidad sirve como una señal de priorización práctica más que como un relato causal de los errores.