用生成模型找整数规划的优质解，无需额外指导模块。
SRG: Score-based Relaxation-guided Generation for Mixed Integer Linear Programming
- 基于分数网络与松弛引导的随机微分方程生成解。
- 在多个基准上优于或媲美最强学习基线，尤其在难样本中提升明显。
- 零样本迁移能力强，适合新规模、新问题快速求解。
我们提出一种基于分数的松弛引导生成框架（SRG），通过近似松弛引导的随机微分方程（SDEs）解决混合整数线性规划（MILP）问题。SRG采用基于Transformer的分数网络，将可行性和最优性信号融入分数建模，使生成模型更集中于可行且高质量的解空间区域。推理时，直接从学习到的分数模型中采样多样化候选解，无需额外引导模块。这些候选解用于构建紧凑的信赖域子问题，供给标准MILP求解器使用。在多个公开基准上，SRG在解质量上达到或超越当前最强的学习基线，尤其在挑战性的候选生成场景中表现突出。此外，SRG展现出良好的零样本跨尺度、跨问题实例迁移能力，在若干情况下显著提升求解器目标值并缩短搜索时间，得益于更高品质的初始候选解和紧凑的信赖域搜索。
原文摘要 · Abstract (English)
We propose Score-based Relaxation-guided Generation (SRG), a generative framework based on an approximate formulation of relaxation-guided stochastic differential equations (SDEs) for mixed-integer linear programming. SRG employs a Transformer-based score network that incorporates feasibility and optimality signals into score modeling, encouraging the learned generative model to place more probability mass on feasible, high-quality regions of the solution space. At inference time, SRG directly samples diverse candidate solutions from the learned score model without requiring any additional guidance module. These candidates are then used to construct compact trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG matches or improves upon the solution quality of the strongest learning-based baselines, with particularly strong gains in challenging candidate-generation settings. Moreover, SRG shows promising zero-shot transferability to unseen cross-scale and cross-problem instances, improving solver objectives and reducing search time in several cases through higher-quality initial candidates and compact trust-region search.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。