GraphBU: MILP Instance Generation with Graph-Native Block Units

Resumen Técnico: GraphBU – Generación de Instancias MILP con Unidades de Bloque Nativas de Grafos

Planteamiento del Problema

Las instancias de programación lineal entera mixta (MILP) son esenciales para el desarrollo y ajuste de solvers tanto clásicos como basados en aprendizaje. Sin embargo, obtener datos representativos suele ser difícil debido a la naturaleza propietaria de los flujos de modelado del mundo real o al alto costo de la recolección de datos. Los métodos existentes de generación de instancias enfrentan una limitación fundamental: carecen de una unidad de generación que capture explícitamente cómo una parte local de un MILP se acopla con el resto de la instancia.

Los enfoques actuales dependen de:

• Plantillas de formulación: Requieren acceso al modelo matemático original.
• Estadísticas de resumen: Coinciden con señales gruesas (ej. densidad, grado) que no logran preservar la conectividad estructural.
• Ediciones de grafos locales: Que pueden romper el acoplamiento entre los subproblemas y el modelo global.
• Bloques de matrices: Que dependen de ordenamientos específicos de filas y columnas y no codifican explícitamente la lógica de reconexión.

Este "desajuste de la unidad de generación" conlleva el riesgo de producir instancias que son factibles pero estructuralmente disímiles a la familia objetivo, lo que las hace ineficaces para entrenar solvers basados en grafos (ej. Predict-and-Search).

Metodología: Unidades de Bloque Nativas de Grafos (GraphBU)

GraphBU propone un marco de generación centrado en la Unidad de Bloque (BU), una unidad nativa de grafos que consiste en un subproblema local de restricciones-variables y su interfaz explícita con el resto de la instancia. El método opera en tres etapas:

1. Descomposición Nativa de Grafos:

   • El MILP se representa como un grafo bipartito ponderado $G = (C \cup V, E)$.
   • Detección de Interfaz: GraphBU identifica nodos de "acoplamiento" (Restricciones Maestras $M$ y Variables de Frontera $B$) utilizando un mecanismo de puntuación basado en la distribución de grupos de vecinos (span), entropía y grado. Se priorizan los nodos que conectan múltiples grupos de variables como candidatos a interfaz.
   • Descomposición Residual: La eliminación de los nodos de interfaz genera componentes residuales. Si los componentes son demasiado grandes, se aplica un refinamiento de corte de grafo (Stoer–Wagner o espectral).
   • Promoción: Un proceso iterativo asegura que cualquier arista que conecte dos bloques residuales distintos sea incidente a al menos un nodo de interfaz. Esto garantiza que el acoplamiento entre bloques sea representado explícitamente en lugar de quedar oculto.

2. Construcción de la Librería de BUs Nativas de Grafos:

   • Cada componente descompuesto forma una Unidad de Bloque $BU_k = (C_k, V_k, M_k, B_k, A_k, \theta_k)$.
   • $A_k$ contiene las porciones de coeficientes para el módulo local y sus interfaces ($A_{C_k, V_k}$, $A_{M_k, V_k}$, $A_{C_k, B_k}$).
   • $\theta_k$ almacena metadatos (límites, tipos, RHS).
   • Esta librería permite el almacenamiento y la reutilización de módulos estructurales sin cargar con nodos globales no relacionados.

3. Generación Compatible:

   • Para generar una nueva instancia, GraphBU descompone una instancia objetivo e intenta reemplazar sus unidades de bloque con unidades de origen compatibles de la librería.
   • Verificación de Compatibilidad: Un reemplazo es válido solo si la unidad de origen y la de destino coinciden en:
     • Firmas de forma (dimensiones de las porciones locales y de interfaz).
     • Dimensiones de interfaz.
     • Firmas de metadatos (ej. sentidos de las restricciones).
   • Preservación: Los tipos de variables y los límites se preservan desde la instancia objetivo para asegurar que la región factible esté bien definida.
   • Garantía de Factibilidad: Bajo una condición de "holgura de interfaz" (Proposición 2), si una asignación local satisface las nuevas restricciones locales y la capacidad residual de las restricciones maestras, la solución global resultante permanece factible.

Contribuciones Clave

1. Unidad de Bloque Nativa de Grafos: La introducción de la primera unidad de generación que empareja un subproblema local con una interfaz de acoplamiento explícita, abordando la desconexión en los métodos existentes.
2. Garantías Teóricas:
   • Separación de Interfaz: Prueba de que la descomposición asegura que todas las aristas entre bloques sean incidentes a nodos de interfaz.
   • Condición de Factibilidad: Una condición suficiente para la preservación de la factibilidad bajo el reemplazo consciente de la interfaz.
   • Invarianza de Permutación: Prueba de que la construcción es invariante a las permutaciones de filas y columnas de la matriz de coeficientes, siempre que el módulo de agrupación sea equivariante.
3. Validación Empírica: Demostración en cuatro familias de MILP (Subastas Combinatorias, Localización de Instalaciones, Colocación de Artículos, Citas de Carga de Trabajo) que GraphBU preserva la similitud estadística de grafos y la factibilidad mejor que los baselines (Random, G2MILP, MILP-StuDio).

Resultados Experimentales

Evaluado en cuatro conjuntos de datos con ratios de modificación ($\eta$) de 0.01, 0.05 y 0.10:

• Similitud Estadística de Grafos: GraphBU logró una similitud promedio de 0.934 (frente a puntuaciones significativamente menores de los baselines), manteniendo una alineación cercana con las estadísticas estructurales de la familia de origen (tamaño, dispersión, grado, agrupamiento).
• Factibilidad: El método preservó la factibilidad en la mayoría de los conjuntos de datos, con una tasa de factibilidad promedio del 96.7%. Notablemente, mejoró la factibilidad en el conjunto de datos de Colocación de Artículos (IP) (88.0%) en comparación con el baseline de estructura de bloques (68.0%).
• Utilidad en el Descenso (Predict-and-Search): El entrenamiento en datos generados por GraphBU mejoró el desempeño del solver en instancias originales no vistas:
  • Reducción de Brecha (Gap): Mejoró las brechas primal-dual para Subastas Combinatorias, Colocación de Artículos y Citas de Carga de Trabajo.
  • Reducción de Tiempo de Ejecución: Redujo el tiempo promedio de resolución para instancias de Localización de Instalaciones (de 4.82s a 3.61s).
  • Las mejoras fueron más pronunciadas en las familias donde los datos generados permanecieron estructuralmente cercanos a la fuente.

Significancia y Reivindicaciones

El artículo sostiene que GraphBU aborda una brecha crítica en el desarrollo de solvers: la necesidad de datos generados que no solo sean factibles, sino también estructuralmente fieles a la familia de instancias objetivo. Al tratar el MILP como un grafo y gestionar explícitamente la interfaz entre los módulos locales y la instancia global, GraphBU permite la creación de datos sintéticos que preservan el "régimen estructural" requerido para las políticas de aprendizaje.

Los autores enmarcan modestamente su contribución como una mejora estructural sobre las unidades de generación existentes. No pretenden resolver el problema general de la preservación de la dureza de los MILP o la unicidad de la descomposición semántica. En su lugar, demuestran que el manejo explícito de la interfaz permite un reemplazo compatible que mantiene la factibilidad y las estadísticas de grafos, proporcionando así datos de entrenamiento de mayor calidad para el entrenamiento de Predict-and-Search que los métodos que dependen de estadísticas gruesas o ediciones de grafos no estructuradas.