arXiv CSopen access

GraphBU: MILP Instance Generation with Graph-Native Block Units

GraphBU: MILP Instance Generation with Graph-Native Block Units Xiaolei Guo1 , Chenyu Zhou1 , Jianghao Lin1∗ , Dongdong Ge1

arXiv:2607.06532v1 [cs.LG] 7 Jul 2026

1 Shanghai Jiao Tong University {lionelgxl, chenyuzhou, linjianghao, ddge}@sjtu.edu.cn

Abstract

Generation Unit Matters

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%.

Existing MILP Generation Units Formulation

Statistics

expert-dependent

coarse match

variable

Graph patch

Matrix block interface

coupling disturbed

layout-dependent

Generation-unit mismatch global MILP

local piece

interface not explicit GraphBU: Graph-native Block Unit master constraints

local module

boundary variables

∗

Corresponding author. Copyright © 2027, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

compatible replacement Target BU

Introduction Mixed-integer linear programming (MILP) is a standard way to model decisions that mix discrete choices with linear constraints, and it appears in applications such as scheduling, planning, logistics, and chip design. In deployed optimization systems, even small changes in solve time can affect throughput, resource utilization, or service quality. Solver development therefore depends on representative instance data: classical solvers use it for parameter tuning and stress testing, while learning-based solvers require it for training(Bengio, Lodi, and Prouvost 2021; Khalil et al. 2016; Nair et al. 2020; Han et al. 2023). Benchmarks also need various instances to expose failures that a small test set would miss. The difficulty is that real MILP instances are often expensive to collect, tied to private business data, or generated inside closed modeling

constraint

shape + interface + metadata

explicit interface

preserve modules

Source BU

control coupling

support solver data

Figure 1: Generation-unit mismatch in MILP instance generation. GraphBU uses graph-native block units with explicit interfaces.

pipelines. This motivates the task of MILP instance generation, which aims to produce additional instances that behave like a target family without requiring access to its original modeling pipeline. A generated MILP is useful only if it remains faithful to the target instance family. Feasibility alone is only a minimal requirement. The generated instances should preserve the

scale, sparsity, coefficient patterns, feasibility behavior, and solving difficulty of the source family. This requirement is especially strict for learning-based solver modules, which learn policies from the graph structure of training instances(Gasse et al. 2019; Prouvost et al. 2020). If generation changes how constraints and variables are connected, a policy trained on the generated data may not transfer to the original family. The choice of generation unit therefore becomes a design issue: the generator must decide which part of a MILP can be reused without breaking the structure that solvers rely on. Existing generators expose the same issue from different angles. When the formulation is known, new instances can be sampled from the model template itself(Bowly 2019). This is often reliable, but it assumes access to the problem type and its mathematical description. Once that assumption is removed, many generators fall back to coarser signals, such as density, degree, or coefficient distributions(Bowly 2019). These signals are easy to measure, but they do not say which constraints and variables should be treated as one reusable part. Graph-based generation moves closer to the representation used by learned solvers; a local graph edit, however, can still cut through the coupling between a subproblem and the rest of the model(Geng et al. 2023). Matrix-block methods reuse repeated submatrices, but the resulting blocks depend on row-column ordering and do not explicitly encode how a block reconnects to the remaining rows and columns(Geng et al. 2024). What is missing is the unit itself: a reusable part of the MILP should contain a graph-local subproblem and the interface through which it attaches to the full instance. We build GraphBU around this unit. GraphBU represents a MILP as a constraint-variable bipartite graph, finds nodes that behave like couplings, and removes them before decomposing the residual graph. If a residual edge still crosses two local blocks, one endpoint is promoted into the interface. Each block unit then contains a local subproblem and the adjacent interface slices needed to reconnect it. Generation replaces a target unit with a source unit only when their shapes, interface dimensions, variable domains, and row metadata match. In experiments on four MILP families, GraphBU improves the two properties that matter for generated solver data. First, the generated instances remain close to the source families in graph-statistical similarity while preserving feasibility and nontrivial solving behavior. Second, the same generated data improves downstream Predict-and-Search training on original test instances, suggesting that the preserved block-unit structure is useful beyond matching summary statistics. Our contributions are: • We introduce GraphBU, the first graph-native block unit for MILP instance generation. Each unit pairs a local constraint-variable module with an explicit coupling interface, and GraphBU operationalizes this unit through interface detection, block-unit extraction, reusable library construction, and compatibility-checked replacement. • We provide theoretical guarantees for the construction, including interface separation, a sufficient feasibility condition under interface slack, and invariance to row-column

permutations. • We show on four MILP families that GraphBU better preserves graph-statistical similarity and feasibility than representative generators, and that the generated data improves downstream Predict-and-Search on held-out original instances.

Related Work MILP data for solver development. Large MILP benchmarks are hard to curate. MIPLIB 2017, for example, uses a data-driven selection process to avoid a benchmark dominated by near-duplicate or trivial instances (Gleixner et al. 2021). ML4CO makes the same point from the learning side: learned solver components are evaluated on distributions of related instances, not on isolated examples (Gasse et al. 2022). For generated data to play the same role, it must preserve the properties that these benchmarks were selected to test. Learning-enhanced MILP solvers. Learning-based solvers often represent a MILP as a constraint-variable bipartite graph (Gasse et al. 2019; Prouvost et al. 2020). This representation has been used for branching, neural MIP heuristics, and Predict-and-Search training (Khalil et al. 2016; Nair et al. 2020; Han et al. 2023). The data requirement is strict: generated instances should expose the same graph patterns that the learned policy will see at test time. MILP instance generation. General generators can match coarse statistics such as density or degree profiles (Bowly 2019). Learned graph generators modify components of the bipartite graph (Geng et al. 2023). Block-structured generators build libraries from reordered coefficient matrices and then apply block operations (Geng et al. 2024). In these approaches, the reusable unit is still not explicit. GraphBU treats it as a graph-local module plus its coupling interface. MILP structure and decomposition. Classical decomposition separates local subproblems from global coupling constraints. Dantzig-Wolfe and Benders-type methods are standard examples (Dantzig and Wolfe 1960; Benders 2005; Geoffrion 1972), and reformulation methods use similar ideas to expose integer-program structure (Vanderbeck and Wolsey 2010). We use this vocabulary for generation rather than for solving. In GraphBU, master constraints and boundary variables record how a reusable local module reconnects to the full instance.

Preliminaries MILP Instance Generation A MILP instance consists of a sparse linear objective, linear constraints, bounds, and integrality restrictions. In this paper, instance generation starts from source instances in a target family and produces additional instances for the same family. The generated data is judged by whether it stays close to the source family in graph statistics and feasibility behavior, and by whether it helps downstream Predict-and-Search training.

MILP Graph Representation

Interface detection. GraphBU starts from an initial grouping of constraints and variables. This grouping can be obtained by graph embeddings followed by clustering; subsequent stages only require group labels

We consider a MILP instance min c⊤ x x

s.t.

a⊤ i = 1, . . . , m, i x ▷◁i bi , l ≤ x ≤ u, xj ∈ Z ∀j ∈ I, m×n

a⊤ i

where A ∈ R is sparse, is row i of A, and ▷◁i ∈ {≤, =, ≥} is the constraint sense. We represent the instance as a weighted bipartite graph G = (C ∪ V, E), where C = {c1 , . . . , cm } denotes constraint nodes and V = {v1 , . . . , vn } denotes variable nodes. An edge (ci , vj ) ∈ E exists if and only if Aij ̸= 0, with edge attribute Aij . Constraint metadata includes the right-hand side and constraint sense; variable metadata includes objective coefficient, lower and upper bounds, and variable type. The graph is invariant to row and column permutations of the coefficient matrix up to node renaming. A row permutation only relabels constraint nodes, and a column permutation only relabels variable nodes. We use the bipartite graph as the structural object for block-unit discovery and recombination.

Local Modules and Interfaces A structured MILP often contains local groups of constraints and variables that meet the rest of the model through a smaller set of couplings. We use the terms local module and interface for generation, not for a solver decomposition. A local module is the part we may store and replace. The interface records how that part reconnects to the rest of the instance.

Method Overview Figure 2 shows the pipeline. GraphBU starts by finding coupling nodes in the bipartite graph and decomposing what remains. Each residual component is stored with the interface slices that touch it. Generation is a constrained replacement step: a target block unit can be replaced only by a source unit with the same local shape, interface dimensions, and metadata signature.

Graph-Native Decomposition GraphBU first decomposes the MILP bipartite graph into local modules and coupling interfaces. Let M ⊆ C denote master constraints and B ⊆ V denote boundary variables. Removing these interface nodes yields the residual graph Gres = G[(C \ M ) ∪ (V \ B)].

(2)

Let {(Ck , Vk )}K k=1

denote the residual components after connected-component decomposition and optional graph-cut refinement. For each residual component, the relevant interface is the subset that actually touches that component: Mk = {m ∈ M : ∃v ∈ Vk , (m, v) ∈ E}, Bk = {b ∈ B : ∃c ∈ Ck , (c, b) ∈ E}.

gC : C → RC ,

(1)

(3) (4)

The three coefficient slices needed to reinsert the component are grouped as
Ak = ACk ,Vk , AMk ,Vk , ACk ,Bk . (5)

gV : V → RV .

(6)

For a constraint ci , let N (ci ) be its neighboring variables. The distribution of its neighbors over variable groups is pi (r) =

|{vj ∈ N (ci ) : gV (vj ) = r}| . |N (ci )|

(7)

We define span(ci ) = |{r : pi (r) > 0}|, X 1 ent(ci ) = − log span(ci )

(8) pi (r) log pi (r),

(9)

r:pi (r)>0

deg(ci ) = |N (ci )|.

(10)

When span(ci ) = 1, we set ent(ci ) = 0. Constraints are ranked lexicographically by (span, ent, deg); high-ranking constraints are treated as candidate master constraints because they couple multiple variable groups. Boundary variables are detected symmetrically by computing the span, entropy, and degree of neighboring constraint groups. The scores have different roles. Span finds nodes that touch multiple groups, entropy filters out nodes whose edges are concentrated in only one group, and degree avoids decisions based on very few edges. None of these scores uses row or column coordinates from the coefficient matrix. Residual decomposition and promotion. After selecting candidate interface nodes M and B, GraphBU decomposes the residual graph Gres . Connected components are accepted as candidate blocks. If a residual component is oversized, we recursively apply graph-cut refinement subject to balance and size constraints; in implementation we use a hybrid routine that applies Stoer–Wagner minimum cut on small components and balanced spectral refinement on larger components. These cuts are used only to propose local blocks; the corresponding edges in the original MILP remain represented through interfaces. After residual decomposition, GraphBU checks the original graph for cross-block coupling. Let βC (c) and βV (v) denote the current local-block labels of non-interface constraints and variables. The violated edge set is E× = {(c, v) ∈ E : βC (c) ̸= βV (v), c ∈ / M, v ∈ / B}. (11) While E× is nonempty, GraphBU promotes at least one endpoint of each violated edge into the interface set, using the span/entropy/degree score to choose the more coupling-like endpoint and a fixed constraint-side tie break. It then recomputes the residual blocks and repeats this detect-promote step until no non-interface cross-block edge remains. Graph-cut edges are represented as interfaces instead of being hidden inside stale residual components. Proposition 1 (Interface separation). After cross-block promotion terminates, every edge in the original graph that connects two different local blocks is incident to at least one interface node in M ∪ B.

Figure 2: GraphBU overview. The three stages are graph-native decomposition, graph-native BU library construction, and compatible generation. Proof. Let

unit contains both the local subproblem and the interface terms needed to reinsert it into a full MILP, without carrying unrelated global interface nodes.

I (t) = M (t) ∪ B (t) , (t)

(t)

(t)

E× = {(c, v) ∈ E : βC (c) ̸= βV (v), c∈ /I

(t)

, v∈ /I

(t)

(12)

}.

The promotion step satisfies (t)

∀(c, v) ∈ E× ,

{c, v} ∩ I (t+1) ̸= ∅.

(13)

Since I (t) ⊆ I (t+1) and |C ∪ V | < ∞, the process reaches a fixed point. At termination, (∗)

(∗)

c∈ / I (∗) , v ∈ / I (∗) } = ∅.

(14)

Therefore (∗)

The extracted block units form a library L = {BU1 , . . . , BUN }. To generate a new instance, GraphBU decomposes a target instance and tries to replace one of its block units with a compatible source unit from L. Compatibility is checked before any coefficient slice is copied. We define the shape signature Φ(BU) = shape(AC,V ),

(∗)

E× = {(c, v) ∈ E : βC (c) ̸= βV (v),

Compatible Generation

(∗)

βC (c) ̸= βV (v) =⇒ {c, v} ∩ (M (∗) ∪ B (∗) ) ̸= ∅, (15) which is the claimed interface separation property.

Graph-Native BU Library The decomposition stage produces block units that can be stored and reused. For a residual component (Ck , Vk ), the corresponding block unit is
BUk = Ck , Vk , Mk , Bk , Ak , θk , (16) where θk stores the local metadata associated with Ck and Vk , including right-hand sides, constraint senses, objective coefficients, bounds, and variable types. The internal slice ACk ,Vk describes the local module, while AMk ,Vk and ACk ,Bk record its interaction with adjacent master constraints and boundary variables. A block

shape(AM,V ),
shape(AC,B ) ,

(17)

and require Φ(BUt ) = Φ(BUs ). The target keeps its variable types and bounds. These fields are not treated as style metadata; changing them can change the feasible region even when the graph shape is unchanged. For a modification ratio η, experiments set the replacement budget to q = ⌊η|T |⌋, where T is the target block-unit set. The generator does not solve the sufficient condition in Proposition 2; it keeps the quantities that make that condition well defined. Table 1 summarizes the replacement policy. Source and target rows and columns are aligned by the deterministic order stored during extraction: local constraints, local variables, master-interface rows, and boundary-interface columns are sorted by extraction order with stable originalindex tie breaks. If any required metadata signature or interface shape is incompatible, the selected target unit is left unchanged.

Table 1: Compatible replacement policy for a target block unit and a sampled source block unit. Component

Policy

ACk ,Vk AMk ,Vk ACk ,Bk

copied from source local slice copied from source master-interface slice copied from source boundary-interface slice bCk , cVk copied from source after sense check Sense sequence must match target sequence Variable type, bounds preserved from target Interface shape must match exactly Alignment stable extraction order

Proposition 2 (Feasible replacement under interface slack). Write all affected rows in ≤ form. Let x be a feasible solution of the original MILP, and suppose only block k is replaced while all variables outside Vk are kept fixed. Let Rk be the set of rows that are neither local rows Ck nor affected master rows Mk . Assume rows in Rk and the coefficients on outside variables are unchanged. Define the residual master capacity ρMk = bMk − Aold Mk ,−Vk x−Vk .

(18)

If there exists a local assignment x̃Vk such that lVk ≤ x̃Vk ≤ uVk , x̃j ∈ Z ∀j ∈ I ∩ Vk , new new ACk ,Vk x̃Vk + ACk ,Bk xBk ≤ bnew Ck , new AMk ,Vk x̃Vk ≤ ρMk ,

(19) (20) (21)

then x̃ = (x−Vk , x̃Vk ) is feasible for the replaced MILP. Proof. The replaced solution satisfies the domain constraints by lVk ≤ x̃Vk ≤ uVk ,

x̃j ∈ Z ∀j ∈ I∩Vk . (22) The local rows are feasible directly from Eq. (20):

x̃−Vk = x−Vk ,

new new new Anew Ck ,: x̃ = ACk ,Vk x̃Vk + ACk ,Bk xBk ≤ bCk .

(23)

For affected master rows, Eq. (21) gives new old Anew Mk ,: x̃ = AMk ,Vk x̃Vk + AMk ,−Vk x−Vk

≤ ρMk + Aold Mk ,−Vk x−Vk = bMk .

(24)

For all remaining rows Rk , the row coefficients and variables are unchanged, hence old Anew Rk ,: x̃ = ARk ,: x ≤ bRk .

Combining the three row groups,  new   new  ACk ,: bCk Anew   bMk  , x̃ ≤ Mk ,: bR k Anew Rk ,:

(25)

(26)

and the domain constraints also hold. Therefore x̃ is feasible for the replaced MILP. ExtractBU(P ) denotes the same extraction routine for source and target instances. It builds the bipartite graph, selects initial interface nodes from grouped neighborhoods, runs residual decomposition with promotion, and returns block-local units with their adjacent interfaces.

Algorithm 1 GraphBU block-unit generation Require: source set D; target MILP P ; budget q Ensure: generated MILP P̂ 1: L ← ∅ 2: for each source instance Ps ∈ D do 3: L ← L ∪ ExtractBU(Ps ) 4: end for 5: P̂ ← P 6: T ← ExtractBU(P̂ ) 7: for r = 1, . . . , q do 8: sample a target unit BUt ∈ T 9: C ← source units compatible with BUt 10: if C = ∅ then 11: continue 12: end if 13: sample BUs ∈ C 14: replace local and interface slices using Table 1 15: preserve target variable types, bounds, and interface dimensions 16: end for 17: return P̂

Structural Properties The next property states the row-column order invariance implied by the graph representation. Let two MILP instances be equivalent if one can be obtained from the other by permuting constraint rows and variable columns. Proposition 3 (Permutation invariance). Suppose two MILP instances differ only by row and column permutations. If the grouping module is equivariant to the induced graph isomorphism up to group-label renaming, then GraphBU produces equivalent interface sets, residual blocks, and block units up to node renaming. Proof. Let ϕ = (ϕC , ϕV ) be the graph isomorphism induced by the row and column permutations, and let ρC , ρV be the corresponding renamings of constraint and variable group labels. Equivariance of the grouping module means ′ gC (ϕC (c)) = ρC (gC (c)), gV′ (ϕV (v)) = ρV (gV (v)). (27) For any constraint c, the neighbor distribution is therefore preserved up to label renaming: p′ϕC (c) (ρV (r)) = pc (r). (28) Thus (span′ , ent′ , deg′ )(ϕC (c)) = (span, ent, deg)(c), (29) and the same argument holds symmetrically for variables. The lexicographic ranking consequently selects corresponding interfaces, M ′ = ϕC (M ) and B ′ = ϕV (B). Removing these nodes gives G′res = ϕ(Gres ), (30) so connected components and graph-cut refinements correspond under ϕ. The promotion rule depends only on adjacency and block labels, which are preserved by ϕ, and therefore also commutes with the permutation. Finally, block-unit extraction applies the same node renaming to the internal and interface slices. Hence the interface sets, residual blocks, and block units are equivalent up to node renaming.

Experiments

Similarity at η = 0.10 0.98

0.88

0.25

0.55

FA

0.81

0.71

0.09

0.00

0.6

IP

0.90

0.69

0.34

0.17

0.4

WA

0.99

0.88

0.25

0.00

Experimental Setup

• Datasets. We use four MILP families: combinatorial auctions (CA), capacitated facility location (FA), item placement (IP), and workload appointment (WA). Appendix Table 4 reports their original scales. • Metrics. Generation quality is measured by graphstatistical similarity, feasible ratio, and average Gurobi solve time. For a statistic z, let dz ∈ [0, 1] be its normalized distributional distance after clipping. We report X Similarity = |Z|−1 (1 − dz ), (31) z∈Z

so larger values mean closer agreement with the original family under size, sparsity, degree, coefficient, clustering, and modularity statistics. Downstream utility is measured by Predict-and-Search (PS) performance on heldout original instances. • Baselines. We compare against random replacement, G2MILP, and MILP-StuDio. These cover unstructured replacement, learned graph-level generation, and block generation from reordered coefficient matrices. • Experimental details. We evaluate modification ratios η ∈ {0.01, 0.05, 0.10} and use a 1000-second Gurobi validation limit for all methods. Each generation-quality setting contains 100 CA, 50 FA, 100 IP, and 150 WA generated instances. Downstream PS models are trained on generated instances and evaluated on 40 held-out original instances per family; held-out instances are never used as generation sources or targets.

Overall Performance Similarity and hardness. Table 2 reports generation quality at η = 0.05. Similarity averages 1 − dz over the structural statistics z, where dz is a clipped normalized distance between generated and original distributions. A larger value means less drift from the target family. GraphBU has the highest similarity on all four datasets: 0.989 on CA, 0.813 on FA, 0.940 on IP, and 0.995 on WA. Feasibility is also stable on most families. CA and FA remain fully feasible, WA reaches 98.7%, and IP improves over the block-structured baseline (88.0% versus 68.0%). Solve time is reported as a hardness signal, but it should not be read alone. A fast infeasible or low-similarity instance is usually a degenerate sample, not an easy case worth training on. Figure 3 repeats the comparison at η = 0.10. GraphBU is still closest to the original distribution on all four datasets.

0.8

0.2 0.0

BU

ph

Gra

St

o udi

M

G2

ILP

n

Ra

dom

Figure 3: Graph-statistical similarity at η = 0.10. Blue cells indicate stronger agreement with the original family.

Gap reduction Improvement (%)

We evaluate whether the generated instances remain usable as data from the target MILP family.

1.0

CA

Runtime reduction

PS+MILP-StuDio PS+GraphBU

2

Improvement (%)

These propositions give structural guarantees without asserting a unique semantic decomposition or universal hardness preservation. Cross-block coupling is represented through explicit interfaces. Interface-aware replacement keeps the quantities needed by the sufficient feasibility condition. Under equivariant grouping, block discovery is independent of arbitrary row-column order.

0 2 CA

FA

IP

WA

20 10 0 CA

FA

IP

WA

Figure 4: Relative improvement over PS baseline. CA/IP/WA use gap reduction; FA uses runtime reduction. Non-primary dataset-metric pairs are shown as zero.

WA is the clearest case: the decomposition finds many replaceable local units with compatible interfaces, so the replacement changes local slices without moving the global graph statistics much. The generated instances are not copies, since degree and coefficient moments still shift after replacement. Similarity matters here because learned solver policies depend on staying in the same structural regime. We still report feasibility, solve time, and PS performance because distributional closeness alone is too weak. Downstream Predict-and-Search. Table 3 tests the generated data in a downstream PS setting. CA, IP, and WA hit the time limit, so we compare final primal-dual gaps. FA is solved by all methods, so runtime is the relevant metric. Relative to the PS baseline, PS+GraphBU reduces the CA gap from 7.8165 to 7.7394, the IP gap from 74.8606 to 73.2195, and the WA gap from 0.4900 to 0.4724. On FA, the average runtime drops from 4.82s to 3.61s while all 40 instances remain solved. The gains are not large on every family, but they appear exactly where the generated data remains structurally close to the source family.

Block-Pool Statistics Figure 5 explains when compatible replacement has room to operate. The x-axis counts extracted block units on a log scale. Compatibility measures how often a target unit can find a source unit with the same shape and metadata. Bubble size shows whether one block dominates the library, and edge

Table 2: Generation quality at η = 0.05. Each dataset reports graph-statistical similarity, feasible ratio, and average solve time in seconds. Higher similarity and feasible ratio are better. Solve time should be read only when the generated distribution remains faithful and feasible. CA

Method

FA

Similarity ↑ Feas. ↑ Random G2MILP MILP-StuDio GraphBU

0.593 0.484 0.936 0.989

IP

WA

Similarity ↑ Feas. ↑ Time Similarity ↑ Feas. ↑

Time

100.0% 1000.00 100.0% 0.69 100.0% 1000.00 100.0% 1000.00

0.000 0.092 0.723 0.813

0.0% 1.8% 100.0% 100.0%

0.03 0.01 2.07 2.78

0.248 0.352 0.687 0.940

Time

Similarity ↑ Feas. ↑

98.0% 0.15 100.0% 0.14 68.0% 340.01 88.0% 715.37

0.040 0.484 0.910 0.995

Time

0.0% 0.15 0.0% 0.01 92.0% 270.39 98.7% 871.51

Table 3: Downstream Predict-and-Search performance on original test instances. CA, IP, and WA use gap reduction as gain because all methods hit the time limit. FA uses runtime reduction because all methods solve all instances. Objective values follow the direction of each dataset; gap/time and gain are the primary comparison metrics. Best PS-variant results are in bold. CA (timeout: 40/40)

Method

Obj. ↑ Gurobi baseline PS baseline PS+MILP-StuDio PS+GraphBU

Gap ↓

97416.6760 97467.1819 97384.0230 97529.0606

FA (optimal: 40/40)

Gain ↑ Time ↓

7.9177 – 7.8165 0.00% 8.0029 -2.38% 7.7394 0.99%

5.13 4.82 5.02 3.61

Compatible ratio

Block-pool diagnostics at = 0.10 1.0

FA

IP

Gap ↓

0.7 1.0

CA 1.5

Gain ↑

Obj. ↓

Gap ↓

Gain ↑

Obj. ↓

Gap ↓

11.1934 10.9523 11.0653 10.7780

61.1536 – 74.8606 0.00% 73.9103 1.27% 73.2195 2.19%

699.300 699.275 699.325 699.250

0.4864 – 0.4900 0.00% 0.4905 -0.10% 0.4724 3.59%

WA

size: largest BU edge: interface count 2.0

2.5

log10 (#BU)

3.0

3.5

WA (timeout: 40/40)

0.00173 – 0.00144 0.00% 0.00167 -4.15% 0.00144 25.10%

0.9 0.8

IP (timeout: 40/40)

4.0

Figure 5: Block-pool statistics at η = 0.10. The plot links the decomposition output to compatible generation: reusable block units matter when their interface signatures admit replacement.

width records how much coupling is exposed as interfaces. The datasets behave differently. IP has a small but highly compatible pool, which helps explain its improvement over the block-structured baseline. WA has many reusable units and enough matching interfaces; this is consistent with its high similarity. CA has fewer compatible matches, so the conservative replacement rule rejects more substitutions.

Conclusion GraphBU is a MILP instance generator built around graphnative block units. Each unit contains a local module and the interface through which it connects to the rest of the instance. Generation is not tied to a fixed row-column ordering, and replacement depends on explicit compatibility checks. The structural results are intentionally modest. Promo-

Gain ↑

tion makes cross-block coupling explicit. The replacement rule keeps the quantities needed by a sufficient feasibility condition. The graph representation removes dependence on row-column order under equivariant grouping. In experiments, GraphBU stays close to the source families in graph-statistical similarity and preserves feasibility on most datasets. The downstream PS results suggest that this structure matters for solver training, beyond matching summary statistics.

References Benders, J. F. 2005. Partitioning Procedures for Solving Mixed-Variables Programming Problems. Computational Management Science, 2(1): 3–19. Bengio, Y.; Lodi, A.; and Prouvost, A. 2021. Machine Learning for Combinatorial Optimization: A Methodological Tour d’Horizon. European Journal of Operational Research, 290(2): 405–421. Bowly, S. 2019. Stress Testing Mixed Integer Programming Solvers through New Test Instance Generation Methods. Ph.D. thesis, Monash University. Dantzig, G. B.; and Wolfe, P. 1960. Decomposition Principle for Linear Programs. Operations Research, 8(1): 101–111. Gasse, M.; Cappart, Q.; Charfreitag, J.; Charlin, L.; Chételat, D.; Chmiela, A.; Dumouchelle, J.; Gleixner, A. M.; Kazachkov, A. M.; Khalil, E. B.; Lichocki, P.; Lodi, A.; Lubin, M.; Maddison, C. J.; Morris, C.; Papageorgiou, D. J.; Parjadis, A.; Pokutta, S.; Prouvost, A.; Scavuzzo, L.; Zarpellon, G.; Yang, L.; Lai, S.; Wang, A.; Luo, X.; Zhou, X.; Huang, H.; Shao, S. C.; Zhu, Y.; Zhang, D.; Quan, T.; Cao, Z.; Xu, Y.; Huang, Z.; Zhou, S.; Chen, B.; He, M.; Hao, H.;

Zhang, Z.; An, Z.; and Mao, K. 2022. The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights. arXiv preprint arXiv:2203.02433. Gasse, M.; Chételat, D.; Ferroni, N.; Charlin, L.; and Lodi, A. 2019. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. arXiv preprint arXiv:1906.01629. Geng, Z.; Kuang, Y.; Li, B.; Li, X.; Liu, H.; Wang, J.; Wu, F.; Zhang, W.; and Zhang, Y. 2024. MILP-StuDio: MILP Instance Generation via Block Structure Decomposition. In Advances in Neural Information Processing Systems. Geng, Z.; Li, X.; Wang, J.; Li, X.; Zhang, Y.; and Wu, F. 2023. A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability. In Advances in Neural Information Processing Systems. Geoffrion, A. M. 1972. Generalized Benders Decomposition. Journal of Optimization Theory and Applications, 10(4): 237–260. Gleixner, A.; Hendel, G.; Gamrath, G.; Achterberg, T.; Bastubbe, M.; Berthold, T.; Christophel, P.; Jarck, K.; Koch, T.; Linderoth, J.; et al. 2021. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 13(3): 443–490. Han, Q.; Yang, L.; Chen, Q.; Zhou, X.; Zhang, D.; Wang, A.; Sun, R.; and Luo, X. 2023. A GNN-Guided Predict-andSearch Framework for Mixed-Integer Linear Programming. In International Conference on Learning Representations. Khalil, E. B.; Le Bodic, P.; Song, L.; Nemhauser, G. L.; and Dilkina, B. 2016. Learning to Branch in Mixed Integer Programming. In Proceedings of the AAAI Conference on Artificial Intelligence. Nair, V.; Bartunov, S.; Gimeno, F.; von Glehn, T.; Lichocki, P.; Lobov, I.; O’Donoghue, B.; Sonnerat, N.; Tjandraatmadja, C.; Wang, P.; Addanki, R.; Hapuarachchi, T.; Keck, T.; Keeling, J.; Kohli, P.; Ktena, I.; Li, Y.; Vinyals, O.; and Zwols, Y. 2020. Solving Mixed Integer Programs Using Neural Networks. arXiv preprint arXiv:2012.13349. Prouvost, A.; Dumouchelle, J.; Scavuzzo, L.; Gasse, M.; Chételat, D.; and Lodi, A. 2020. Ecole: A Gym-Like Library for Machine Learning in Combinatorial Optimization Solvers. arXiv preprint arXiv:2011.06069. Vanderbeck, F.; and Wolsey, L. A. 2010. Reformulation and Decomposition of Integer Programs. In 50 Years of Integer Programming 1958–2008, 431–502. Springer.

Additional Method Details

Compatibility Checks

Graph Construction and Metadata For each MILP instance, GraphBU constructs a weighted bipartite graph G = (C ∪V, E) from the nonzero pattern of the constraint matrix. The constraint side C contains one node per row of A, and the variable side V contains one node per decision variable. Each nonzero Aij induces an edge (ci , vj ) with edge weight Aij . The graph topology is used for decomposition, while MILP metadata is stored with the corresponding nodes and edges. Constraint metadata includes the right-hand side and constraint sense (≤, =, ≥). Variable metadata includes objective coefficient, lower bound, upper bound, and variable type. Edge metadata stores the coefficient value. This separation matters during generation. The adjacency pattern determines which constraints and variables are coupled, while metadata controls feasibility-critical details that should not be changed without compatibility checks. In particular, GraphBU preserves variable types and bounds during compatible replacement, since changing integrality or domain information can alter the feasible region even when graph shape is unchanged.

Symmetric Interface Scores The main text defines span, entropy, and degree scores for constraint nodes. Boundary variables are scored symmetrically. Let N (vj ) be the neighboring constraints of variable vj , and let gC : C → RC denote constraint group labels. Define |{ci ∈ N (vj ) : gC (ci ) = r}| qj (r) = . (32) |N (vj )| The variable-side coupling scores are span(vj ) = |{r : qj (r) > 0}|, X 1 ent(vj ) = − log span(vj )

(33) qj (r) log qj (r), (34)

For a target block unit BUt and a source block unit BUs , the main text requires matching internal shape and blocklocal interface dimensions. The replacement rule also checks metadata compatibility before replacement. In particular, the local constraint-sense sequence must match, and the variable type sequence and bound pattern of the target local variables are preserved. The source unit contributes local coefficient slices, local right-hand sides, and local objective coefficients only when these checks pass. If no compatible source exists for a selected target block, that target block is left unchanged and another target block is considered. These checks are intentionally conservative. They do not certify feasibility, but they rule out several avoidable failures: replacing a binary block with a continuous block, changing the number of local constraints incident to the block-local master interface, changing the number of boundary-variable columns seen by a local constraint, or mixing local rows with incompatible constraint senses.

Additional Structural Discussion Relation to Classical Decomposition Classical decomposition methods such as Dantzig-Wolfe decomposition use local subproblems and global coupling constraints to solve optimization problems. GraphBU uses the same vocabulary for a different purpose: generation rather than optimization. A graph-native block unit is not a pricing problem, and the master constraints in GraphBU are not used to derive a decomposition algorithm for solving. They are interface nodes that record how a local module connects to the rest of the MILP. This distinction limits the claims. GraphBU does not claim to recover a unique economic, physical, or semantic decomposition of an instance. It claims that, after interface promotion, cross-block coupling is represented explicitly and can be respected during generation.

r:qj (r)>0

deg(vj ) = |N (vj )|.

(35)

When span(vj ) = 1, we set ent(vj ) = 0. Variables with high span, entropy, and degree are candidate boundary variables because they connect multiple constraint groups.

Grouping Module GraphBU only assumes an initial grouping of constraint and variable nodes. This grouping can be instantiated by spectral biclustering on the sparse coefficient structure or by graph embeddings followed by clustering. The downstream block-unit extraction does not require the grouping labels to correspond to semantic classes: they are used to expose nodes whose neighborhoods span multiple groups. The reported experiments use graph embeddings clustered by HDBSCAN. Spectral biclustering provides an alternative grouping procedure. The interface detector is separated from a particular grouping method: different embeddings or domain-aware clustering schemes can be used without changing the definition of graph-native block units or the compatible replacement rule.

Expanded Proof of Interface Separation The main paper states that, after promotion, every crossblock edge in the original graph is incident to an interface node. We restate the argument with the block assignment made explicit. (t) (t) Let πC (ci ) and πV (vj ) denote residual block assignments at iteration t, and define I (t) = M (t) ∪ B (t) .

(36)

At each promotion iteration, (t)

(t)

(t)

E× = {(ci , vj ) ∈ E :πC (ci ) ̸= πV (vj ), ci ∈ / I (t) , vj ∈ / I (t) }.

(37)

For every violated edge, the update satisfies (t)

∀(ci , vj ) ∈ E× , with

{ci , vj } ∩ I (t+1) ̸= ∅,

I (t) ⊆ I (t+1) ⊆ C ∪ V.

(38) (39)

Since C ∪ V is finite, the monotone sequence reaches a fixed point I (∗) . The stopping condition is (∗)

E× = ∅.

(40)

Equivalently, ∀(ci , vj ) ∈ E,

(∗)

(∗)

πC (ci ) ̸= πV (vj ) ⇒

{ci , vj } ∩ I (∗) ̸= ∅. (41)

A Sufficient Condition for Feasibility Preservation This section gives a sufficient, not necessary, condition under which replacing one block unit preserves feasibility. It explains the role of interface-aware compatibility while avoiding a universal feasibility claim. For compactness, write the relevant local and master constraints in ≤ form; equality constraints can be represented by two inequalities, and ≥ rows can be multiplied by −1. Consider a feasible original solution x for a MILP. Suppose block k with local variables Vk is replaced, while all variables outside Vk are kept fixed. Let Bk be the block-local boundary variables and Mk be the block-local master constraints. If there exists a replacement local assignment x̃Vk satisfying the preserved domain constraints lVk ≤ x̃Vk ≤ uVk ,

x̃j ∈ Z

∀j ∈ I ∩ Vk ,

(42)

such that new new Anew Ck ,Vk x̃Vk + ACk ,Bk xBk ≤ bCk ,

old Anew Mk ,Vk x̃Vk ≤ AMk ,Vk xVk + sMk ,

(44)

sMk = bMk − Aold Mk ,: x,

(45)

then the concatenated solution x̃ = (x−Vk , x̃Vk ) is feasible for the replaced instance.

x̃j ∈ Z

The experiments use four MILP families: combinatorial auctions (CA), capacitated facility location (FA), item placement (IP), and workload appointment (WA). CA, IP, and WA are time-limit regimes under the 1000-second evaluation budget, so downstream Predict-and-Search (PS) utility is compared by final primal-dual gap. FA instances are solved by all PS variants, so runtime reduction is the relevant comparison. For generation quality, all methods are evaluated at modification ratios η ∈ {0.01, 0.05, 0.10}. The main paper reports the strongest setting, η = 0.10, while Tables 5 and 6 report the per-ratio results. Table 4 reports the scale of the original instance collections used in the experiments. The families differ substantially in both size and sparsity: IP is small but comparatively dense, FA and WA are much larger and very sparse, and CA lies between these regimes.

Additional Generation Results Additional Downstream Details Table 7 reports solver work units and node counts for the downstream PS evaluation. These diagnostics are not used as the primary comparison metric, but they provide additional context about the search process.

The block-pool statistics expose intermediate structure produced by GraphBU: the number of extracted block units, master constraints, boundary variables, compatible replacements, and largest-to-average block-size ratios. These quantities make the generator inspectable. For example, WA has many small reusable units, IP has a compact highly compatible pool, and CA has lower compatibility as the modification ratio increases. These diagnostics help explain why similarity, feasibility, and compatibility should be read together rather than as interchangeable indicators.

Block-Pool Scale and Nominal Block Size

Proof. The domain condition gives x̃ ∈ [l, u],

Datasets and Evaluation Regimes

Additional Diagnostics (43)

and its contribution to each master constraint does not exceed the original contribution plus remaining master slack,

where

Additional Experimental Protocol

∀j ∈ I.

(46)

new new Anew Ck ,Vk x̃Vk + ACk ,Bk xBk ≤ bCk .

(47)

For local rows in Ck ,

For master rows in Mk , old new Anew Mk ,: x̃ = AMk ,Vk x̃Vk + AMk ,−Vk x−Vk old ≤ Aold Mk ,Vk xVk + sMk + AMk ,−Vk x−Vk

(48)

old = Aold Mk ,: x + bMk − AMk ,: x = bMk .

For all rows outside Ck ∪ Mk , old Anew r,: x̃ = Ar,: x ≤ br .

(49)

Hence every constraint and domain restriction is satisfied by x̃.

Table 8 expands the η = 0.10 block-pool view with a nominal residual size per block unit. This quantity is computed from the average original instance scale after removing detected interface nodes, divided by the average number of extracted block units. It is a compact scale diagnostic rather than an exact histogram: the largest-to-average block-size ratio in the last column records how concentrated the block pool can become.

Table 4: Original dataset scale. Rows, variables, nonzeros, and density are averaged over the original instances; parentheses give the observed min–max range when it varies. Dataset CA FA IP WA

#Instances

Rows

Variables

Nonzeros / Density

100 50 100 150

2603.03 (2505–2685) 10201.00 195.00 64302.17 (64163–64428)

1500.00 10100.00 1083.00 61000.00

8330.28 (7745–8959) / 0.00213 40200.00 / 0.000390 7440.00 / 0.03523 361465.11 (346186–375920) / 0.0000922

Table 5: Graph-statistical similarity across modification ratios. Higher is better. η

Method

CA

FA

IP

WA

0.01 0.01 0.01 0.01

Random G2MILP MILP-StuDio GraphBU

0.857 0.854 0.955 0.988

0.000 0.358 0.823 0.813

0.419 0.337 0.687 0.972

0.163 0.854 0.937 0.999

0.05 0.05 0.05 0.05

Random G2MILP MILP-StuDio GraphBU

0.593 0.484 0.936 0.989

0.000 0.092 0.723 0.813

0.248 0.352 0.687 0.940

0.040 0.484 0.910 0.995

0.10 0.10 0.10 0.10

Random G2MILP MILP-StuDio GraphBU

0.549 0.249 0.884 0.976

0.000 0.091 0.707 0.806

0.169 0.336 0.687 0.900

0.001 0.249 0.878 0.992

Table 6: Average solve time and feasible ratio across modification ratios. Each cell reports time in seconds followed by feasible ratio in parentheses. η

Method

0.01 0.01 0.01 0.01 0.01

Original Random G2MILP MILP-StuDio GraphBU

1000.00 (100.0%) 3.33 (100.0%) 1000.00 (100.0%) 940.21 (100.0%) 1000.00 (100.0%) 0.01 (0.0%) 417.48 (98.0%) 0.11 (0.0%) 802.30 (100.0%) 0.02 (1.7%) 456.19 (49.0%) 12.01 (10.0%) 1000.00 (100.0%) 2.50 (100.0%) 340.02 (68.0%) 658.62 (98.0%) 1000.00 (100.0%) 3.00 (100.0%) 851.38 (89.0%) 946.48 (100.0%)

0.05 0.05 0.05 0.05 0.05

Original Random G2MILP MILP-StuDio GraphBU

1000.00 (100.0%) 3.20 (100.0%) 1000.00 (100.0%) 947.43 (100.0%) 1000.00 (100.0%) 0.03 (0.0%) 0.15 (98.0%) 0.15 (0.0%) 0.69 (100.0%) 0.01 (1.8%) 0.14 (100.0%) 0.01 (0.0%) 1000.00 (100.0%) 2.07 (100.0%) 340.01 (68.0%) 270.39 (92.0%) 1000.00 (100.0%) 2.78 (100.0%) 715.37 (88.0%) 871.51 (98.7%)

0.10 0.10 0.10 0.10 0.10

Original 1000.00 (100.0%) 4.05 (100.0%) 1000.00 (100.0%) 940.11 (100.0%) Random 1000.00 (100.0%) 0.04 (0.0%) 0.04 (89.0%) 0.24 (0.0%) G2MILP 0.72 (100.0%) 0.01 (2.0%) 0.03 (100.0%) 0.02 (0.0%) MILP-StuDio 972.24 (100.0%) 1.38 (100.0%) 340.02 (68.0%) 198.35 (91.0%) GraphBU 1000.00 (100.0%) 1.98 (100.0%) 571.83 (81.0%) 720.38 (99.3%)

CA

FA

IP

WA

Table 7: Detailed downstream PS diagnostics. Work and node counts are averaged over 40 held-out original test instances per family. Dataset

Method

Optimal

Time limit

Work units

Nodes

CA CA CA CA

Gurobi baseline PS baseline PS+MILP-StuDio PS+GraphBU

0/40 0/40 0/40 0/40

40/40 40/40 40/40 40/40

1325.31 1268.95 1158.28 1425.81

5371.62 5079.77 4708.75 5751.00

FA FA FA FA

Gurobi baseline PS baseline PS+MILP-StuDio PS+GraphBU

40/40 40/40 40/40 40/40

– – – –

5.075 4.743 5.202 4.767

296.25 296.93 337.55 298.03

IP IP IP IP

Gurobi baseline PS baseline PS+MILP-StuDio PS+GraphBU

0/40 0/40 0/40 0/40

40/40 40/40 40/40 40/40

625.074 676.782 923.124 865.219

458155.88 250009.95 337235.65 323478.58

WA WA WA WA

Gurobi baseline PS baseline PS+MILP-StuDio PS+GraphBU

0/40 0/40 0/40 0/40

40/40 40/40 40/40 40/40

1489.40 1364.39 1455.24 1516.53

1176.22 1044.20 1279.97 1284.53

Table 8: Block-pool scale and nominal block size at η = 0.10. Residual nodes per BU approximate the average number of non-interface rows and variables represented by each extracted block unit. The last column is the largest-to-average block-size ratio, not a fraction of total residual size. Dataset

#BU

#Master

#Boundary

Residual Nodes / BU

Compat.

Largest / Avg

CA FA IP WA

29.49 974.8 16.00 5754

1275 307 60 1938

734.2 303 380 1838

70.98 20.20 52.38 21.12

0.719 1.000 1.000 0.997

1.739 0.170 4.304 0.166