GraphBU: MILP Instance Generation with Graph-Native Block Units

Resumo Técnico: GraphBU – Geração de Instâncias MILP com Unidades de Bloco Nativas de Grafos

Definição do Problema

Instâncias de programação linear inteira mista (MILP) são essenciais para o desenvolvimento e ajuste de solvers clássicos e baseados em aprendizado. No entanto, obter dados representativos é frequentemente difícil devido à natureza proprietária das pipelines de modelagem do mundo real ou ao alto custo da coleta de dados. Os métodos existentes de geração de instâncias enfrentam uma limitação fundamental: eles carecem de uma unidade de geração que capture explicitamente como uma parte local de um MILP se acopla ao restante da instância.

As abordagens atuais dependem de:

• Templates de formulação: Exigindo acesso ao modelo matemático original.
• Estatísticas de resumo: Correspondendo a sinais grosseiros (ex: densidade, grau) que falham em preservar a conectividade estrutural.
• Edições de grafos locais: Que podem romper o acoplamento entre os subproblemas e o modelo global.
• Blocos de matriz: Que dependem de ordenações específicas de linhas e colunas e não codificam explicitamente a lógica de reconexão.

Este "descompasso da unidade de geração" corre o risco de produzir instâncias que são viáveis, mas estruturalmente dissimilar das famílias alvo, tornando-as ineficazes para o treinamento de solvers baseados em grafos (ex: Predict-and-Search).

Metodologia: Unidades de Bloco Nativas de Grafos (GraphBU)

O GraphBU propõe um framework de geração centrado na Unidade de Bloco (BU - Block Unit), uma unidade nativa de grafo composta por um subproblema local de restrição-variável e sua interface explícita com o restante da instância. O método opera em três estágios:

1. Decomposição Nativa de Grafos:

   • O MILP é representado como um grafo bipartido ponderado $G = (C \cup V, E)$.
   • Detecção de Interface: O GraphBU identifica nós de "acoplamento" (Restrições Mestras $M$ e Variáveis de Fronteira $B$) usando um mecanismo de pontuação baseado na distribuição de grupos de vizinhos (span), entropia e grau. Nós que conectam múltiplos grupos de variáveis são priorizados como candidatos a interface.
   • Decomposição Residual: A remoção dos nós de interface gera componentes residuais. Se os componentes forem muito grandes, aplica-se o refinamento de corte de grafo (Stoer–Wagner ou espectral).
   • Promoção: Um processo iterativo garante que qualquer aresta conectando dois blocos residuais diferentes seja incidente a pelo menos um nó de interface. Isso garante que o acoplamento entre blocos seja explicitamente representado, em vez de oculto.

2. Construção da Biblioteca de BUs Nativas de Grafos:

   • Cada componente decomposto forma uma Unidade de Bloco $BU_k = (C_k, V_k, M_k, B_k, A_k, \theta_k)$.
   • $A_k$ contém os recortes de coeficientes para o módulo local e suas interfaces ($A_{C_k, V_k}$, $A_{M_k, V_k}$, $A_{C_k, B_k}$).
   • $\theta_k$ armazena metadados (limites, tipos, RHS).
   • Esta biblioteca permite o armazenamento e reuso de módulos estruturais sem carregar nós globais não relacionados.

3. Geração Compatível:

   • Para gerar uma nova instância, o GraphBU decompõe uma instância alvo e tenta substituir suas unidades de bloco por unidades de origem compatíveis da biblioteca.
   • Verificação de Compatibilidade: Uma substituição é válida apenas se a unidade de origem e a alvo coincidirem em:
     • Assinaturas de forma (dimensões dos recortes locais e de interface).
     • Dimensões de interface.
     • Assinaturas de metadados (ex: sentidos das restrições).
   • Preservação: Tipos de variáveis e limites são preservados da instância alvo para garantir que a região viável permaneça bem definida.
   • Garantia de Viabilidade: Sob uma condição de "folga de interface" (Proposição 2), se uma atribuição local satisfizer as novas restrições locais e a capacidade residual das restrições mestras, a solução global resultante permanece viável.

Principais Contribuições

1. Unidade de Bloco Nativa de Grafo: A introdução da primeira unidade de geração que pareia um subproblema local com uma interface de acoplamento explícita, abordando a desconexão em métodos existentes.
2. Garantias Teóricas:
   • Separação de Interface: Prova de que a decomposição garante que todas as arestas entre blocos sejam incidentes a nós de interface.
   • Condição de Viabilidade: Uma condição suficiente para a preservação da viabilidade sob substituição consciente da interface.
   • Invariância de Permutação: Prova de que a construção é invariante a permutações de linha-coluna da matriz de coeficientes, desde que o módulo de agrupamento seja equivariante.
3. Validação Empírica: Demonstração através de quatro famílias de MILP (Leilões Combinatórios, Localização de Instalações, Posicionamento de Itens, Agendamento de Carga de Trabalho) de que o GraphBU preserva a similaridade estatística de grafos e a viabilidade melhor do que os baselines (Random, G2MILP, MILP-StuDio).

Resultados Experimentais

Avaliado em quatro conjuntos de dados com razões de modificação ($\eta$) de 0.01, 0.05 e 0.10:

• Similaridade Estatística de Grafo: O GraphBU alcançou uma similaridade média de 0.934 (vs. pontuações significativamente menores para os baselines), mantendo um alinhamento próximo com as estatísticas estruturais da família de origem (tamanho, esparsidade, grau, agrupamento).
• Viabilidade: O método preservou a viabilidade na maioria dos datasets, com uma taxa de viabilidade média de 96.7%. Notavelmente, melhorou a viabilidade no dataset de Posicionamento de Itens (IP) (88.0%) em comparação com o baseline de estrutura de blocos (68.0%).
• Utilidade Downstream (Predict-and-Search): O treinamento nos dados gerados pelo GraphBU melhorou o desempenho do solver downstream em instâncias originais não vistas:
  • Redução de Gap: Melhorou os gaps primal-dual para Leilões Combinatórios, Posicionamento de Itens e Agendamento de Carga de Trabalho.
  • Redução de Tempo de Execução: Reduziu o tempo médio de resolução para instâncias de Localização de Instalações (de 4.82s para 3.61s).
  • As melhorias foram mais pronunciadas nas famílias onde os dados gerados permaneceram estruturalmente próximos da origem.

Significância e Alegações

O artigo afirma que o GraphBU aborda uma lacuna crítica no desenvolvimento de solvers: a necessidade de dados gerados que sejam não apenas viáveis, mas também estruturalmente fiéis à família de instância alvo. Ao tratar o MILP como um grafo e gerenciar explicitamente a interface entre módulos locais e a instância global, o GraphBU permite a criação de dados sintéticos que preservam o "regime estrutural" necessário para políticas de aprendizado.

Os autores enquadram modestamente sua contribuição como uma melhoria estrutural sobre as unidades de geração existentes. Eles não pretendem resolver o problema geral de preservação de dureza de MILP ou unicidade de decomposição semântica. Em vez disso, demonstram que o tratamento explícito da interface permite uma substituição compatível que mantém a viabilidade e as estatísticas de grafo, fornecendo assim dados de treinamento de maior qualidade para o treinamento de políticas Predict-and-Search do que métodos que dependem de estatísticas grosseiras ou edições de grafos não estruturadas.