---
title: "GraphBU：基于图原生块单元的 MILP 实例生成"
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实例生成","图原生块单元","组合优化"]
---

# GraphBU：基于图原生块单元的 MILP 实例生成

## AI 点评

> 这篇论文巧妙地将MILP实例的局部耦合关系编码进生成单元，解决了长期困扰研究者的数据稀缺问题。对从事运筹优化、自动算法配置以及基于学习的求解器开发的团队来说是必读的工作。

## 速览

GraphBU 是一种面向混合整数线性规划（MILP）实例生成的新型图原生方法，其基本单元为局部子问题及其与实例其余部分的接口。通过将耦合节点提升为主约束或边界变量，生成兼容性检查后的块单元进行替换，从而保留源实例的关键图结构和可行性。实验表明，该生成器在多个数据集上平均图统计相似度达 0.934，可行性约 96.7%，并能将下游 Predict-and-Search 训练的核心指标平均提升 8.0%。该方法有效解决了私有 MILP 实例难以获取且需保持结构一致性的难题。

## 关键点

- 提出图原生块单元概念，将局部子问题及其接口作为生成单位，显式记录耦合关系。
- 通过“提升”操作将耦合节点转化为主约束或边界变量，实现结构保留。
- 在多个公开私有数据集上验证，图统计相似度平均 0.934，可行性 96.7%，下游 PS 训练指标提升 8.0%。

## 全文

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

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_898b7d4b1cc6dda1c2e35018