Resumen Técnico: Forge: Representaciones de Optimización Fundacionales a partir de Incrustaciones de Grafos

1. Declaración del Problema

Los problemas de optimización combinatoria (CO), particularmente la Programación Entera Mixta (MIP), son fundamentales para la ciencia y la ingeniería, pero siguen siendo computacionalmente costosos de resolver. Aunque el aprendizaje automático (ML) ofrece alternativas prometedoras, los enfoques actuales basados en el aprendizaje sufren de limitaciones significativas de escalabilidad y generalización:

• Dependencia de Datos: El entrenamiento requiere típicamente resolver un gran número de instancias difíciles para generar datos etiquetados, lo que incurre en altos costos computacionales y depende de los mismos resolvedores que los investigadores pretenden acelerar.
• Falta de Generalización: Los métodos existentes suelen entrenar modelos dedicados para distribuciones de problemas, tareas o tamaños específicos. No logran generalizarse a través de diferentes dominios de problemas (por ejemplo, Set Cover frente a Combinatorial Auction) o tipos de tareas (por ejemplo, generación de cortes frente a guía de búsqueda).
• Limitaciones Estructurales: La mayoría de los métodos de CO dependen de Redes Neuronales de Grafos (GNN), las cuales capturan eficazmente la información local de variables y restricciones, pero tienen dificultades para codificar una estructura de instancia global significativa debido a su sesgo de localidad inherente.

El artículo postula la necesidad de una representación de optimización fundacional: un modelo pre-entrenado y de propósito general capaz de generar incrustaciones (embeddings) de MIP que se generalicen a través de tareas, problemas y tamaños, entrenado de manera no supervisada sin requerir soluciones óptimas.

2. Metodología: El Marco de Trabajo Forge

Forge (Foundational Optimization Representations from Graph Embeddings) es un marco de trabajo que pre-entrena un autoencoder de grafos cuantizado vectorialmente sobre una colección diversa de instancias de MIP. Se inspira en los modelos fundacionales de Procesamiento de Lenguaje Natural (NLP) y Visión Computacional (CV).

Arquitectura Central

El marco opera a través de las siguientes etapas (Figura 1):

1. MIP-a-BP (Representación Bipartita): Las instancias de MIP se representan como grafos bipartitos donde los nodos son variables y restricciones.
   • Características de los Nodos: A diferencia de trabajos previos que dependen de características generadas por el resolvedor (por ejemplo, de árboles de branch-and-bound), Forge utiliza únicamente propiedades básicas de entrada: sentido de la restricción (>, <, =) y valores RHS para las restricciones; tipo de variable, límites y coeficientes de la función objetivo para las variables. Esto asegura que el modelo no dependa de la resolución de la instancia.
2. BP-a-GNN: Una GNN basada en GraphSAGE (dos capas) procesa el grafo bipartito para generar incrustaciones continuas para cada nodo.
3. Libro de Códigos Cuantizado Vectorialmente (El "Vocabulario"): Para abordar la incapacidad de la GNN para captar la estructura global, las incrustaciones continuas pasan a través de un cuantizador vectorial. Este mapea cada nodo a un código discreto de un libro de códigos aprendible de tamaño $k$ (actuando como un vocabulario).
   • Este paso preserva la información estructural global al crear una distribución de códigos discretos a través de la instancia, de forma análoga a las distribuciones de tokens en los modelos de lenguaje.
4. Reconstrucción (Autoencoder): Los códigos discretos se mapean de vuelta a palabras de código (codewords) y se pasan a través de decodificadores para reconstruir las características originales de los nodos y los pesos de las aristas.
5. Función de Pérdida: El modelo se entrena de forma no supervisada para minimizar:
   • Pérdida de reconstrucción (características de nodos y aristas).
   • Pérdida del libro de códigos (moviendo las palabras de código hacia las incrustaciones).
   • Pérdida de compromiso (moviendo las incrustaciones hacia las palabras de código).

Representaciones

Una vez entrenado, Forge produce dos niveles de representaciones:

• Local: Palabras de código discretas para variables y restricciones individuales.
• Global: Una incrustación a nivel de instancia derivada de la distribución de frecuencia de los códigos asignados a lo largo de todo el grafo. La dimensión de la incrustación es igual al tamaño del vocabulario ($|codebook|$).

3. Contribuciones Clave

El artículo describe cinco contribuciones primarias:

1. Paso de Modelo Fundacional: Introducción de Forge, un único modelo pre-entrenado que genera incrustaciones de MIP tanto a nivel de instancia como a nivel fino (variable/restricción) sin supervisión.
2. Generalización No Supervisada: Demostración de que las incrustaciones de Forge pueden agrupar (clustering) instancias no vistas a través de diversos dominios de problemas y niveles de dificultad con alta precisión, superando a las características estáticas y a las lecturas (readouts) estándar de GNN.
3. Adaptabilidad Supervisada: Prueba de que el mismo modelo pre-entrenado puede ajustarse (fine-tuning) con datos mínimamente etiquetados y económicos para tareas radicalmente distintas (predicción de brecha de integrales y guía de búsqueda) a través de variados tamaños de problema.
4. Integración con Resolvedores: Integración exitosa de las predicciones de Forge en Gurobi, un resolvedor comercial, demostrando mejoras consistentes en las brechas primales (primal gaps) en múltiples tipos de problemas.
5. Aumento de ML: Mejora de los métodos de aprendizaje basados en el estado del arte (específicamente Li et al., 2025 y PS-Gurobi) mediante la concatenación de las incrustaciones de Forge, obteniendo ganancias significativas de rendimiento en instancias no vistas.

4. Resultados Experimentales

Agrupamiento No Supervisado (Unsupervised Clustering)

• Configuración: Entrenado en 1,800 instancias de MIPLIB; probado en 1,000 instancias no vistas de D-MIPLIB y strIPlib cubriendo 21 pares de dominio-dificultad.
• Métrica: Información Mutua Normalizada (NMI) para la precisión del agrupamiento.
• Desempeño: Forge logró un NMI de 0.953, superando significativamente al Mean Readout (0.726) y al Label Propagation (0.790). Las visualizaciones (PaCMAP) mostraron grupos distintos para cada tipo de problema y un gradiente claro de fácil a difícil, a pesar de que el modelo nunca vio estas instancias específicas durante el entrenamiento.

Tarea I: Predicción de la Brecha de Integralidad (Generación de Pseudo-Cortes)

• Objetivo: Predecir la brecha de integralidad para generar un pseudo-corte para el nodo raíz, estrechando el límite de la relajación LP.
• Entrenamiento: Ajustado con 450 instancias (CA, SC, GIS) con etiquetas generadas por Gurobi (timeout de 120s), evitando la optimalidad total.
• Resultados:
  • En instancias de prueba "muy difíciles" (incluyendo MVC, que no fue vista en el ajuste), Forge logró desviaciones absolas medias de 12–19% a través de tipos de problemas.
  • Impacto en el Resolvedor: La integración de los pseudo-cortes de Forge en Gurobi redujo la brecha primal hasta en un 85% (por ejemplo, una ganancia del 84.52% en Generalized Independent Set) comparado con Gurobi solo.
  • Comparación: Superó al método SOTA de Li et al. (2025) (18.63% de desviación vs. 20.14%) en 17,500 instancias no vistas sin entrenamiento adicional.

Tarea II: Guía de Búsqueda

• Objetivo: Predecir qué variables es probable que estén en la solución óptima para guiar la búsqueda de branch-and-bound.
• Entrenamiento: Ajustado con 700 instancias utilizando una combinación de Entropía Cruzada Binaria (BCE) y Pérdida de Triplete (Triplet Loss). Las etiquetas se derivaron de soluciones factibles encontradas en 5 minutos (no se requiere optimalidad).
• Resultados:
  • Impacto en el Resolvedor: Gurobi con la guía de búsqueda de Forge logró hasta un 48.75% de mejora en la brecha primal y hasta un 35% de aceleración en el tiempo de convergencia en instancias medianas.
  • Aumento de ML: Cuando se utilizó para aumentar PS-Gurobi (un método de guía de búsqueda basado en aprendizaje SOTA), las incrustaciones de Forge redujeron la brecha primal en más del 40% (Combinatorial Auction) y un 50% (Generalized Independent Set).

5. Significado y Reivindicaciones

El artículo afirma que Forge representa un paso significativo hacia los modelos fundacionales para la optimización. Su importancia radica en:

• Romper la Dependencia del Resolvedor: Aprende representaciones estructurales sin requerir acceso a soluciones óptimas o estados internos del resolvedor durante el pre-entrenamiento, abordando el problema del "huevo o la gallina" de necesitar resolvedores para entrenar resolvedores.
• Representación Universal: Demuestra que un solo modelo puede generalizarse a través de disparatados tipos de problemas (por ejemplo, Set Cover, Combinatorial Auction, Vertex Cover) y tipos de tareas (predicción de brecha, guía de búsqueda), una capacidad que anteriormente estaba limitada a modelos específicos de problemas o tareas.
• Utilidad Práctica: El marco no es meramente teórico; se integra directamente con resolvedores comerciales y mejora los flujos de trabajo de ML existentes, ofreciendo ganancias medibles e inmediatas en la eficiencia de resolución.
• Ciencia Abierta: Los autores liberan el código de entrenamiento, los pesos pre-entrenados y las incrustaciones para fomentar la investigación adicional en el aprendizaje de representaciones para la optimización.

Los autores mantienen la modestia respecto a las limitaciones, señalando que la escala actual (3.25M de parámetros) es pequeña comparada con otros modelos fundacionales, la semántica del "vocabulario" aprendido aún no ha sido explorada, y las integraciones actuales son de "un solo paso" (one-shot) en lugar de iterativas a lo largo del árbol de branch-and-bound. Sugieren que el trabajo futuro podría extender estos principios a Problemas de Satisfacción de Restricciones (CSP) y SAT.