---
title: "GraphBU: MILP Instance Generation with Graph-Native Block Units"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.06532v1"
permalink: "https://feed.astralor.com/items/itm_898b7d4b1cc6dda1c2e35018"
published: "2026-07-07T17:39:06.000Z"
score: 78
channel: "ai"
tags: ["GraphBU","MILP Instance Generation","Graph-Native Block Unit","Portfolio Optimization"]
---

# GraphBU: MILP Instance Generation with Graph-Native Block Units

## AI commentary

> This paper cleverly encodes local coupling relationships into generation units, addressing the long-standing data scarcity issue. It is a must-read for teams working on operations research, automatic algorithm configuration, and learning-based solver development.

## At a glance

GraphBU is a novel graph-native generator for Mixed-Integer Linear Programming (MILP) instances, where the basic unit is a local subproblem plus its interface to the rest of the instance. By promoting coupling nodes into master constraints or boundary variables and performing compatibility-checked block replacements, it preserves the key graph structure and feasibility of source families. Experiments show that on multiple datasets, the average graph-statistical similarity reaches 0.934, average feasibility is about 96.7%, and the downstream Predict-and-Search training improves its main index by 8.0% on average. This addresses the challenge of obtaining private MILP instances while maintaining structural fidelity.

## Key points

- Introduces graph-native block units where each unit is a local subproblem plus its interface, explicitly modeling coupling. 
- Promotion operation turns coupling nodes into master constraints or boundary variables to preserve structure. 
- Achieves average graph-statistical similarity of 0.934, feasibility of 96.7%, and 8.0% improvement in downstream Predict-and-Search training. 

## Full text

Mixed-integer linear programming (MILP) instances used for solver development are hard to obtain when models come from private or application-specific pipelines. A generator must keep the structure that solvers and learned policies rely on. Existing general generators usually choose their generation unit from a formulation template, summary statistics, local graph edits, or blocks found after recombination. These units do not explicitly record how a local part of the MILP is coupled to the rest of the instance. We propose GraphBU, a graph-native generator whose basic unit is a local subproblem plus its interface. The method promotes coupling nodes into master constraints or boundary variables and uses the resulting block units for compatibility-checked replacement. The analysis focuses on the properties needed by this construction: promotion separates interfaces, replacement can preserve feasibility under an interface-slack condition, and the graph construction is invariant to row-column permutations. On MILP instances generation, this unit keeps graph statistics close to the source family, preserves feasibility on most datasets, and improves downstream Predict-and-Search training. Genrated by GraphBU, The average graph-statistical similarity was approximately 0.934, the average feasibility was approximately 96.7%, and the average increase in the main index of downstream PS was approximately 8.0%.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_898b7d4b1cc6dda1c2e35018