Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming

📄 arXiv: 2603.24033v1 📥 PDF

作者: Ruobing Wang, Xin Li, Yujie Fang, Mingzhong Wang

分类: cs.LG

发布日期: 2026-03-25

💡 一句话要点

提出SRG框架以加速混合整数线性规划求解

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 混合整数线性规划 拉格朗日松弛 随机微分方程 生成模型 优化算法

📋 核心要点

  1. 现有的MILP求解方法通常假设变量独立，导致解的多样性不足，需大量后续搜索以获得高质量解。
  2. 本文提出的SRG框架通过拉格朗日松弛引导的随机微分方程生成多样化的解候选，提升了解的质量和多样性。
  3. 在多个公共基准测试中，SRG在解的质量上始终优于现有的机器学习基线，且在未见问题上表现出色。

📝 摘要（中文）

预测与搜索（PaS）方法在加速混合整数线性规划（MILP）求解方面展现出潜力。然而，现有方法通常假设变量独立，并依赖于确定性的单点预测，这限制了解的多样性，往往需要大量后续搜索以获得高质量解。本文提出了SRG，一个基于拉格朗日松弛引导的随机微分方程（SDE）的生成框架，具有理论上的解质量保证。SRG利用卷积核捕捉变量间的依赖关系，同时整合拉格朗日松弛引导采样过程，朝向可行且近似最优的区域。SRG生成多样化的高质量解候选，定义紧凑有效的信任区域子问题，显著优于现有机器学习基线，并在未见的跨尺度/问题实例上展现出强大的零-shot迁移能力。

🔬 方法详解

问题定义：本文旨在解决混合整数线性规划（MILP）求解中的变量独立假设带来的多样性不足问题。现有方法往往依赖于单点预测，导致解的多样性和质量受限。

核心思路：SRG框架通过引入拉格朗日松弛和随机微分方程（SDE），在生成解的过程中考虑变量间的依赖关系，从而生成多样化的高质量解候选。

技术框架：SRG的整体架构包括数据预处理、卷积核提取变量依赖、拉格朗日松弛引导的采样过程，以及最终的解候选生成模块。各模块协同工作，以提高解的质量和多样性。

关键创新：SRG的主要创新在于结合了拉格朗日松弛与随机微分方程，能够在解的生成过程中有效引导采样，显著提升了解的质量和多样性。这与传统方法的单点预测形成鲜明对比。

关键设计：SRG采用卷积神经网络提取变量间的依赖关系，损失函数设计为优化解的多样性与质量，网络结构则通过多层卷积和非线性激活函数增强模型的表达能力。具体参数设置和超参数调优在实验中进行了详细探讨。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在多个公共基准测试中，SRG框架在解的质量上始终优于现有机器学习基线，且在未见的跨尺度/问题实例上表现出色，达到了与最先进的精确求解器相竞争的最优性，同时显著降低了计算开销。

🎯 应用场景

该研究的潜在应用领域包括优化调度、资源分配和物流管理等需要高效求解MILP问题的场景。SRG框架的引入能够显著提升求解效率和解的质量，具有广泛的实际价值和未来影响。

📄 摘要（原文）

Predict-and-search (PaS) methods have shown promise for accelerating mixed-integer linear programming (MILP) solving. However, existing approaches typically assume variable independence and rely on deterministic single-point predictions, which limits solution diversityand often necessitates extensive downstream search for high-quality solutions. In this paper, we propose \textbf{SRG}, a generative framework based on Lagrangian relaxation-guided stochastic differential equations (SDEs), with theoretical guarantees on solution quality. SRG leverages convolutional kernels to capture inter-variable dependencies while integrating Lagrangian relaxation to guide the sampling process toward feasible and near-optimal regions. Rather than producing a single estimate, SRG generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG consistently outperforms existing machine learning baselines in solution quality. Moreover, SRG demonstrates strong zero-shot transferability: on unseen cross-scale/problem instances, it achieves competitive optimality with state-of-the-art exact solvers while significantly reducing computational overhead through faster search and superior solution quality.