GraphBU: MILP Instance Generation with Graph-Native Block Units
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-07-08 02:32 UTCglm-5.2pith:6A7YQFYBrecord.jsonopen to challenge →
The pith
MILP generator keeps local blocks wired to their interfaces
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central object is the graph-native block unit: a local constraint-variable module paired with its coupling interface (master constraints and boundary variables). The paper shows that if you decompose a MILP bipartite graph by first extracting coupling nodes and then promoting any residual cross-block edges into the interface, you get reusable units that can be recombined through compatibility-checked replacement while keeping the graph structure, feasibility behavior, and solver-training utility of the source family. The mechanism that carries the argument is the detect-promote loop: it guarantees that after termination, every edge connecting two different local blocks is incident to at,
What carries the argument
The detect-promote loop: GraphBU scores each node by span (how many local groups its neighbors touch), entropy (whether its edges are spread or concentrated in one group), and degree, then ranks nodes lexicographically to identify coupling candidates. After removing candidates and decomposing the residual, it checks for violated cross-block edges and promotes the more coupling-like endpoint of each into the interface set, iterating until no non-interface cross-block edge remains. This produces block units that carry both local content and interface slices, and replacement is gated by exact shape, interface-dimension, and metadata compatibility.
If this is right
- If the block-unit decomposition is as structure-preserving as claimed, generated MILP instances could serve as drop-in training data for learned solver components (branching, heuristic selection, Predict-and-Search) without the distributional drift that degrades policy transfer.
- The interface-slack feasibility condition, while only sufficient, suggests a practical path to generating provably feasible instances: if the generator can verify that a replacement local assignment exists within the residual master capacity, feasibility is guaranteed without solving the full MILP.
- The permutation-invariance property means the method does not depend on how a practitioner ordered rows or columns in their coefficient matrix, which removes a source of arbitrariness that affects matrix-block generators.
- If the grouping module can be made domain-aware (e.g., using problem-specific embeddings), the same detect-promote-replace pipeline could expose modular structure in application-specific MILPs where the formulation is private or unknown.
Where Pith is reading between the lines
- The paper evaluates on four families, but all are relatively structured combinatorial problems (auctions, facility location, item placement, workload appointment). Whether the detect-promote loop produces meaningful interfaces on irregular or densely coupled MILPs—where most constraints span multiple groups—remains an open question.
- The sufficient feasibility condition requires finding a local assignment satisfying the interface-slack inequalities, but the generator does not actually solve this condition during generation; it only keeps the quantities well-defined. A natural extension would be to check the condition cheaply (e.g., via LP relaxation of the local subproblem) and reject replacements that fail it, which could pus
- The downstream PS improvements are modest (1-3.6% gap reduction across families). Whether this improvement scales with the amount of generated data, or plateaus because the generated instances are too close to the originals, is not tested.
- The grouping module is treated as a pluggable component, but the paper does not report how sensitive the decomposition is to the choice of grouping method. A systematic comparison of HDBSCAN, spectral biclustering, and domain-specific groupings on the same instances would clarify whether the block-unit concept is robust or fragile to this choice.
Load-bearing premise
The entire decomposition depends on the initial grouping module producing group labels that meaningfully separate local modules from coupling nodes. If the grouping is poor, the span/entropy/degree ranking will misidentify interface nodes, and the block units will not capture the true modular structure of the MILP. The paper does not provide a sensitivity analysis showing that the decomposition is stable across different grouping methods or hyperparameters.
What would settle it
If one took the same MILP instances, ran GraphBU with two different grouping methods (e.g., HDBSCAN vs. spectral biclustering), and found that the resulting block units, interface sets, and compatibility ratios differed substantially, the claim that the block unit is a well-defined graph-native object would be weakened.
Figures
read the original abstract
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%.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces GraphBU, a MILP instance generator whose basic unit is a local constraint-variable subproblem paired with an explicit coupling interface (master constraints and boundary variables). The method detects interface nodes via span/entropy/degree ranking over graph-embedding group labels, promotes cross-block edges into the interface until a fixed point is reached, and performs compatibility-checked block-unit replacement for generation. Three structural propositions are proved: interface separation (monotone promotion to fixed point), a sufficient feasibility condition under interface slack, and permutation invariance under equivariant grouping. Experiments on four MILP families (CA, FA, IP, WA) compare graph-statistical similarity, feasibility, solve time, and downstream Predict-and-Search utility against Random, G2MILP, and MILP-StuDio baselines.
Significance. The core idea of making the generation unit a graph-local module plus its explicit interface is a clean and well-motivated contribution to the MILP instance generation literature. The three propositions are correctly proved and are appropriately scoped as structural rather than semantic guarantees. The compatibility-checked replacement policy is conservative and well-designed. The experimental comparison covers four diverse MILP families and three meaningful baselines. The block-pool diagnostics (Figure 5, Table 8) add interpretability. The downstream PS evaluation, while modest in per-dataset gains, tests the practical utility claim that preserved structure helps beyond matching statistics.
major comments (3)
- Abstract and Introduction: The headline claim of 'approximately 8.0% average increase in downstream PS' is computed by averaging heterogeneous metrics across datasets — gap reduction for CA/IP/WA (0.99%, 2.19%, 3.59%) and runtime reduction for FA (25.10%). The FA runtime reduction dominates the arithmetic mean; without it, the average drops to approximately 2.26%. This averaging of different metric types is misleading as a summary of overall improvement. The authors should either (a) report per-dataset gains without the cross-metric average, or (b) clearly state that the 8.0% figure mixes gap reduction and runtime reduction and is dominated by the FA result. This is load-bearing because the downstream utility claim is the paper's main differentiator from generators that only match statistics.
- Table 7: PS+GraphBU uses more work units than PS baseline on CA (1425.81 vs 1268.95) and IP (865.22 vs 676.78), suggesting the gap improvements on these datasets may come at the cost of more search effort rather than better solution quality per unit of work. The paper does not address this inconsistency. Since the downstream utility claim rests on these comparisons, the authors should discuss whether the gap reductions are attributable to the generated training data or to increased search effort, and ideally report a normalized comparison (e.g., gap reduction per work unit or per node).
- Section 'Graph-Native Decomposition,' Eqs. (6)-(10) and the 'Grouping Module' appendix: The entire decomposition pipeline depends on the initial grouping labels g_C and g_V, but no sensitivity analysis is provided. The paper states that HDBSCAN on graph embeddings is used in experiments and that spectral biclustering is an alternative, but does not report whether the interface detection, block-unit extraction, or downstream generation quality changes materially with different grouping methods or hyperparameters. Since the grouping quality determines which nodes are promoted to the interface, a brief sensitivity check (e.g., comparing HDBSCAN vs. spectral biclustering on at least one dataset) would substantially strengthen the claim that the method is robust to the grouping choice. If the method is brittle to this choice, that should be disclosed.
minor comments (8)
- Abstract: 'Genrated' should be 'Generated.'
- Table 2 caption: 'Feas.' should be written out as 'Feasible ratio.'
- Figure 4 caption: 'Non-primary dataset-metric pairs are shown as zero' is confusing. Consider stating explicitly which metric is primary for each dataset.
- Table 5: At η=0.01, GraphBU similarity on FA is 0.813, identical to η=0.05. This may be correct but appears suspicious; a brief note would help.
- Table 6: The solve-time column for CA is 1000.00 for all methods except G2MILP, which hits the time limit but reports 0.69-0.72s. This seems inconsistent and should be clarified.
- The paper uses 'GraphBU' and 'GraphBU' interchangeably; the styling should be consistent.
- Proposition 2 proof, Eq. (24): the notation A^{old}_{Mk,-Vk} x_{-Vk} is introduced only implicitly; a one-line definition would help readers.
- The references to Geng et al. 2023 and 2024 could benefit from a brief note on the relationship between GraphBU's block units and the matrix blocks in MILP-StuDio, since the comparison is central to the experimental evaluation.
Simulated Author's Rebuttal
We thank the referee for a careful and constructive report. All three major comments identify legitimate issues that we will address in the revised manuscript. Comment 1 (misleading cross-metric averaging of the 8.0% headline figure) is correct and we will revise the abstract and introduction to report per-dataset gains transparently. Comment 2 (work-unit confound in Table 7) raises a fair concern about whether PS gap improvements on CA and IP are attributable to better training data or more search effort; we will add a normalized comparison and a discussion of this issue. Comment 3 (missing sensitivity analysis for the grouping module) is a reasonable request; we will add a comparison of HDBSCAN vs. spectral biclustering on at least one dataset and report the impact on interface detection and generation quality. We can honestly address all three comments and have no standing objections.
read point-by-point responses
-
Referee: Abstract and Introduction: The headline claim of 'approximately 8.0% average increase in downstream PS' is computed by averaging heterogeneous metrics across datasets — gap reduction for CA/IP/WA (0.99%, 2.19%, 3.59%) and runtime reduction for FA (25.10%). The FA runtime reduction dominates the arithmetic mean; without it, the average drops to approximately 2.26%. This averaging of different metric types is misleading as a summary of overall improvement. The authors should either (a) report per-dataset gains without the cross-metric average, or (b) clearly state that the 8.0% figure mixes gap reduction and runtime reduction and is dominated by the FA result.
Authors: The referee is correct that the 8.0% headline figure averages heterogeneous metrics — gap reduction on CA/IP/WA and runtime reduction on FA — and that the FA runtime reduction (25.10%) dominates the arithmetic mean. Without FA, the average drops to approximately 2.26%, and even within the three gap-reduction datasets, the metric type is the same but the magnitudes vary considerably. Averaging across these different metric types is misleading as a summary of overall improvement, and we should not have presented it as a single headline number without qualification. We will revise the abstract and introduction to adopt option (a): report per-dataset gains individually (0.99% gap reduction on CA, 25.10% runtime reduction on FA, 2.19% gap reduction on IP, 3.59% gap reduction on WA) without computing a cross-metric average. We will also add a brief note in the experimental section explaining that CA/IP/WA use gap reduction because they hit the time limit, while FA uses runtime reduction because all instances are solved to optimality, so the metrics are not directly comparable across datasets. This is an important correction because the downstream utility claim is the paper's main differentiator, and the reader needs an honest picture of where the gains are concentrated. revision: yes
-
Referee: Table 7: PS+GraphBU uses more work units than PS baseline on CA (1425.81 vs 1268.95) and IP (865.22 vs 676.78), suggesting the gap improvements on these datasets may come at the cost of more search effort rather than better solution quality per unit of work. The paper does not address this inconsistency. Since the downstream utility claim rests on these comparisons, the authors should discuss whether the gap reductions are attributable to the generated training data or to increased search effort, and ideally report a normalized comparison (e.g., gap reduction per work unit or per node).
Authors: This is a fair and important observation. Table 7 does show that PS+GraphBU uses more work units than the PS baseline on CA (1425.81 vs 1268.95, a 12.4% increase) and IP (865.22 vs 676.78, a 27.8% increase), while achieving gap reductions of 0.99% and 2.19% respectively. This raises the legitimate concern that the gap improvements might be partially attributable to increased search effort rather than purely to better training data from GraphBU-generated instances. We can and should address this in the revision. First, we will add a normalized comparison: gap reduction per work unit. On CA, PS+GraphBU achieves 7.7394/1425.81 = 0.00543 gap per work unit vs 7.8165/1268.95 = 0.00616 for the baseline, which is an 11.8% improvement in gap-per-work-unit efficiency. On IP, PS+GraphBU achieves 73.2195/865.22 = 0.0846 vs 74.8606/676.78 = 0.1106, a 23.5% improvement. So the normalized comparison actually strengthens the case that the gains are not merely from more search effort. However, we acknowledge that work units are themselves influenced by the branching policy learned from the training data, so the causal story is not fully clean: better training data may lead the policy to explore more productively, which manifests as both more work units and better gaps. We will add this normalized comparison to the table and include a discussion of this subtlety. We will also note that on WA, where PS+GraphBU achieves a 3.59% gap reduction, the work units are comparable (1516.53 vs 1364.39, an 11.2% increase), and on FA, where the metric is runtime, PS+GraphBU actually uses slightly fewer work units (4.767 vs 4.743) while reducing runtime by 25.10%, so the effort confound is not uniformly present across datasets. revision: yes
-
Referee: Section 'Graph-Native Decomposition,' Eqs. (6)-(10) and the 'Grouping Module' appendix: The entire decomposition pipeline depends on the initial grouping labels g_C and g_V, but no sensitivity analysis is provided. The paper states that HDBSCAN on graph embeddings is used in experiments and that spectral biclustering is an alternative, but does not report whether the interface detection, block-unit extraction, or downstream generation quality changes materially with different grouping methods or hyperparameters. Since the grouping quality determines which nodes are promoted to the interface, a brief sensitivity check (e.g., comparing HDBSCAN vs. spectral biclustering on at least one dataset) would substantially strengthen the claim that the method is robust to the grouping choice. If the method is brittle to this choice, that should be disclosed.
Authors: The referee is right that the method's dependence on the initial grouping labels is underexplored in the current manuscript. The grouping labels determine which nodes are identified as high-span (coupling-like) and thus promoted to the interface, so the choice of grouping method could in principle materially affect the decomposition and downstream generation quality. We will add a sensitivity analysis comparing HDBSCAN on graph embeddings (the method used in all reported experiments) against spectral biclustering on the sparse coefficient structure, on at least one dataset. We plan to run this comparison on CA and IP, as they represent different structural regimes (CA has moderate density and moderate block count; IP is small, dense, and has a compact highly-compatible block pool). We will report the number of detected interface nodes, the number and size distribution of extracted block units, the compatible replacement ratio, and the graph-statistical similarity of generated instances under each grouping method. If the results are stable across grouping methods, this supports the robustness claim. If they are not, we will disclose this honestly and discuss which grouping method is better suited to which structural regime. We note that the interface detection mechanism (span/entropy/degree ranking over group labels) is designed to be relatively insensitive to the exact group boundaries: what matters is whether a node's neighbors span multiple groups, not the precise group assignments. But this design intuition should be verified empirically, and the referee is correct that the current manuscript does not provide that verification. revision: yes
Circularity Check
No significant circularity; propositions are self-contained and experiments use external baselines
full rationale
The paper's three propositions are standard algorithm-correctness arguments, not circular derivations. Proposition 1 (interface separation) proves that after the promotion loop terminates, no cross-block edge lacks an interface endpoint — this is a fixed-point argument where the termination condition (E× = ∅) is the claim, but this is a standard correctness proof pattern, not a fitted-input-renamed-as-prediction circularity. Proposition 2 (feasible replacement) is a sufficient condition whose proof directly verifies the inequalities; no parameter is fitted and then predicted. Proposition 3 (permutation invariance) derives from the equivariance assumption on the grouping module, which is an explicit stated assumption, not a hidden self-citation. The experimental results (similarity, feasibility, downstream PS) are measured against external baselines (Random, G2MILP, MILP-StuDio) and original instance distributions; no metric is fitted and then reproduced as a prediction. The citation to Han et al. 2023 (Predict-and-Search) is for the downstream evaluation framework and does not share authors with the present paper (Han et al. authors: Han, Yang, Chen, Zhou X., Zhang, Wang, Sun, Luo; present paper: Guo, Zhou C., Lin, Ge). The skeptic's concern about averaging heterogeneous metrics (gap reduction vs. runtime reduction) is a methodological correctness issue, not circularity. Score 1 reflects the trivially-true nature of Proposition 1's proof, which is a minor structural weakness but not circularity.
Axiom & Free-Parameter Ledger
free parameters (4)
- Modification ratio η =
{0.01, 0.05, 0.10}
- Grouping module hyperparameters =
unspecified
- Graph-cut balance/size constraints =
unspecified
- Constraint-side tiebreak rule =
fixed
axioms (4)
- domain assumption The grouping module g_C, g_V produces labels that meaningfully separate local modules from coupling nodes
- domain assumption Connected-component decomposition with optional graph-cut refinement produces meaningful local blocks
- domain assumption The sufficient feasibility condition (Prop. 2) is a reasonable proxy for actual feasibility preservation
- domain assumption Graph-statistical similarity (Eq. 31) is an adequate measure of instance fidelity
invented entities (2)
-
Block unit (BU)
independent evidence
-
Master constraints (M) and boundary variables (B) as interface nodes
independent evidence
Reference graph
Works this paper leans on
-
[1]
Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and others , journal =. 2021 , publisher =
work page 2021
-
[2]
The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
Gasse, Maxime and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch. The Machine Learning for Combinatorial Optimization Competition (. arXiv preprint arXiv:2203.02433 , year =
work page internal anchor Pith review Pith/arXiv arXiv
-
[3]
Exact Combinatorial Optimization with Graph Convolutional Neural Networks
Exact Combinatorial Optimization with Graph Convolutional Neural Networks , author =. arXiv preprint arXiv:1906.01629 , year =
work page internal anchor Pith review Pith/arXiv arXiv 1906
-
[4]
Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
Ecole: A Gym-Like Library for Machine Learning in Combinatorial Optimization Solvers , author =. arXiv preprint arXiv:2011.06069 , year =
work page internal anchor Pith review Pith/arXiv arXiv 2011
-
[5]
European Journal of Operational Research , volume =
Machine Learning for Combinatorial Optimization: A Methodological Tour d'Horizon , author =. European Journal of Operational Research , volume =
-
[6]
Proceedings of the AAAI Conference on Artificial Intelligence , year =
Learning to Branch in Mixed Integer Programming , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =
-
[7]
Solving Mixed Integer Programs Using Neural Networks
Solving Mixed Integer Programs Using Neural Networks , author =. arXiv preprint arXiv:2012.13349 , year =
work page internal anchor Pith review Pith/arXiv arXiv 2012
-
[8]
Han, Qingyu and Yang, Linxin and Chen, Qian and Zhou, Xiang and Zhang, Dong and Wang, Akang and Sun, Ruoyu and Luo, Xiaodong , booktitle =. A
-
[9]
Stress Testing Mixed Integer Programming Solvers through New Test Instance Generation Methods , author =
-
[10]
A Deep Instance Generative Framework for
Geng, Zijie and Li, Xijun and Wang, Jie and Li, Xiao and Zhang, Yongdong and Wu, Feng , booktitle =. A Deep Instance Generative Framework for
-
[11]
Geng, Zijie and Kuang, Yufei and Li, Bin and Li, Xijun and Liu, Haoyang and Wang, Jie and Wu, Feng and Zhang, Wanbo and Zhang, Yongdong , booktitle =
-
[12]
Operations Research , volume =
Decomposition Principle for Linear Programs , author =. Operations Research , volume =
-
[13]
Computational Management Science , volume =
Partitioning Procedures for Solving Mixed-Variables Programming Problems , author =. Computational Management Science , volume =
-
[14]
Journal of Optimization Theory and Applications , volume =
Generalized Benders Decomposition , author =. Journal of Optimization Theory and Applications , volume =
-
[15]
50 Years of Integer Programming 1958--2008 , pages =
Reformulation and Decomposition of Integer Programs , author =. 50 Years of Integer Programming 1958--2008 , pages =. 2010 , publisher =
work page 1958
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.