GraphBU: MILP Instance Generation with Graph-Native Block Units

Technische Samenvatting: GraphBU – MILP-instantiegeneratie met graaf-native blokeenheden

Probleemstelling

MILP-instanties (Mixed-Integer Linear Programming) zijn essentieel voor het ontwikkelen en afstemmen van zowel klassieke als leergestuurde solvers. Het verkrijgen van representatieve gegevens is echter vaak moeilijk vanwege de propriëtaire aard van echte modelleringstrajecten of de hoge kosten van gegevensverzameling. Bestaande methoden voor instantiegeneratie kampen met een fundamentele beperking: ze missen een generatie-eenheid die expliciet vastlegt hoe een lokaal deel van een MILP koppelt met de rest van de instantie.

Huidige benaderingen vertrouwen op:

• Formuleringstemplates: Waarbij toegang tot het oorspronkelijke wiskundige model vereist is.
• Samenvattende statistieken: Het matchen van grove signalen (bijv. dichtheid, graad) die falen in het behoud van structurele connectiviteit.
• Lokale graafbewerkingen: Die de koppeling tussen subproblemen en het globale model kunnen verbreken.
• Matrixblokken: Die afhankelijk zijn van specifieke rij-kolomordeningen en geen expliciete logica voor herverbinding coderen.

Deze "generatie-eenheid mismatch" brengt het risico met zich mee dat geproduceerde instanties weliswaar haalbaar zijn, maar structureel ongelijksoortig aan de doelgroepfamilie, waardoor ze ineffectief zijn voor het trainen van leergestuurde solvers (zoals Predict-and-Search) die steunen op graafstructuren.

Methodologie: Graaf-native Blokeenheden (GraphBU)

GraphBU stelt een generatiekader voor dat gecentreerd is rond de Blokeenheid (BU), een graaf-native eenheid bestaande uit een lokaal beperkings-variabele subprobleem en zijn expliciete interface naar de rest van de instantie. De methode werkt in drie stadia:

1. Graaf-native Decompositie:

   • De MILP wordt gerepresenteerd als een gewogen bipartiete graaf $G = (C \cup V, E)$.
   • Interface Detectie: GraphBU identificeert "koppelings"-nodes (Master Constraints $M$ en Boundary Variables $B$) met behulp van een scoremechanisme gebaseerd op de verdeling van buurnode-groepen (span), entropie en graad. Nodes die meerdere variabele groepen verbinden, krijgen prioriteit als interface-kandidaten.
   • Residuele Decompositie: Het verwijderen van interface-nodes levert residuele componenten op. Als componenten te groot zijn, wordt graaf-snede verfijning (Stoer–Wagner of spectraal) toegepast.
   • Promotie: Een iteratief proces zorgt ervoor dat elke rand die twee verschillende residuele blokken verbindt, incident is aan ten minste één interface-node. Dit garandeert dat cross-block koppeling expliciet wordt gerepresenteerd in plaats van verborgen.

2. Constructie van een Graaf-native BU-bibliotheek:

   • Elke gedecodeerde component vormt een Blokeenheid $BU_k = (C_k, V_k, M_k, B_k, A_k, \theta_k)$.
   • $A_k$ bevat de coëfficiënt-slices voor de lokale module en de interfaces ($A_{C_k, V_k}$, $A_{M_k, V_k}$, $A_{C_k, B_k}$).
   • $\theta_k$ slaat metadata op (grenzen, typen, RHS).
   • Deze bibliotheek maakt het mogelijk om structurele modules op te slaan en te hergebruiken zonder ongerelateerde globale nodes mee te slepen.

3. Compatibele Generatie:

   • Om een nieuwe instantie te genereren, decomponeert GraphBU een doel-instantie en probeert de blokeenheden te vervangen door compatibele bron-eenheden uit de bibliotheek.
   • Compatibiliteitscontrole: Een vervanging is alleen geldig als de bron- en doelunits overeenkomen in:
     • Vorm-signaturen (dimensies van lokale en interface slices).
     • Interface-dimensies.
     • Metadata-signaturen (bijv. beperkingszintuigen/constraint senses).
   • Preservatie: Variabele typen en grenzen worden overgenomen van de doel-instantie om te waarborgen dat de haalbare regio goed gedefinieerd blijft.
   • Haalbaarheidsgarantie: Onder een "interface slack"-conditie (Propositie 2), als een lokale toewijzing voldoet aan de nieuwe lokale beperkingen en de residuele capaciteit van de master constraints, blijft de resulterende globale oplossing haalbaar.

Kernbijdragen

1. Graaf-native Blokeenheid: De introductie van de eerste generatie-eenheid die een lokaal subprobleem koppelt aan een expliciete interface, waarmee de disconnectie in bestaande methoden wordt aangepakt.
2. Theoretische Garanties:
   • Interface Separatie: Bewijs dat de decompositie ervoor zorgt dat alle cross-block randen incident zijn aan interface-nodes.
   • Haalbaarheidsconditie: Een voldoende voorwaarde voor het behoud van haalbaarheid onder interface-bewuste vervanging.
   • Permutatie-invariantie: Bewijs dat de constructie invariant is voor rij-kolom permutaties van de coëfficiëntmatrix, mits de groeperingsmodule equivariant is.
3. Empirische Validatie: Demonstratie over vier MILP-families (Combinatorial Auctions, Facility Location, Item Placement, Workload Appointment) waarbij GraphBU de graaf-statistische gelijkenis en haalbaarheid beter behoudt dan baselines (Random, G2MILP, MILP-StuDio).

Experimentele Resultaten

Geëvalueerd op vier datasets met modificatieverhoudingen ($\eta$) van 0,01, 0,05 en 0,10:

• Graaf-statistische Gelijkenis: GraphBU behaalde een gemiddelde gelijkenis van 0,934 (vs. aanzienlijk lagere scores voor baselines), waarbij de nauwe uitlijning met de structurele statistieken (grootte, ijver/sparsity, graad, clustering) van de bronfamilie behouden bleef.
• Haalbaarheid: De methode behield de haalbaarheid op de meeste datasets, met een gemiddelde haalbaarheidspercentage van 96,7%. Opvallend genoeg verbeterde het de haalbaarheid op de Item Placement (IP) dataset (88,0%) vergeleken met de block-structured baseline (68,0%).
• Downstream Nut (Predict-and-Search): Trainen op door GraphBU gegenereerde data verbeterde de downstream solver-prestaties op onafhankelijke originele instanties:
  • Gap-reductie: Verbeterde primal-dual gaps voor Combinatorial Auctions, Item Placement en Workload Appointment.
  • Runtime-reductie: Verminderde de gemiddelde rekentijd voor Facility Location-instanties (van 4,82s naar 3,61s).
    De verbeteringen waren het meest uitgesproken in families waar de gegenereerde data structureel dicht bij de bron bleef.

Betekenis en Claims

Het artikel beweert dat GraphBU een kritieke kloof in solver-ontwikkeling aanpakt: de noodzaak voor gegenereerde data die niet alleen haalbaar zijn, maar ook structureel getrouw aan de doel-instantiefamilie. Door de MILP als een graaf te behandelen en de interface tussen lokale modules en de globale instantie expliciet te beheren, stelt GraphBU de creatie van synthetische data mogelijk die het "structurele regime" behouden die nodig is voor leergestuurde policies.

De auteurs kaderen hun bijdrage bescheiden als een structurele verbetering van bestaande generatie-eenheden. Ze beweren niet het algemene probleem van MILP-hardheidbehoud of semantische decompositie-uniciteit op te lossen. In plaats daarvan demonstreren ze dat expliciete interface-afhandeling compatibele vervanging mogelijk maakt die haalbaarheid en graafstatistieken handhaaft, en daarmee kwalitatief betere trainingsdata biedt voor downstream Predict-and-Search training dan methoden die vertrouwen op grove statistieken of ongestructureerde graafbewerkingen.