Solving Integer Linear Programming with Parallel Tempering

📄 arXiv: 2605.29366v1 📥 PDF

作者: Kyuil Sim, Sanghyeok Choi, Jinkyoo Park

分类: cs.LG

发布日期: 2026-05-28

备注: Preprint. Code available at https://github.com/ski-sim/ILP-with-ParallelTempering

💡 一句话要点

提出基于Parallel Tempering的无求解器整数线性规划方法

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

关键词: 整数线性规划 组合优化 Parallel Tempering 采样优化 无求解器

📋 核心要点

  1. 现有基于学习的ILP方法泛化性差，依赖外部求解器，限制了其应用范围。
  2. 提出一种无求解器的采样优化框架，利用局部平衡提议和Parallel Tempering直接探索可行解。
  3. 实验表明，该方法在多个基准测试中优于SCIP，与Gurobi相当，且对分布偏移更鲁棒。

📝 摘要（中文）

整数线性规划(ILP)是建模各种组合优化问题的通用框架，通常由复杂的精确求解器或启发式算法解决。虽然最近基于学习的方法显示出有效性，但它们泛化到分布外实例的能力较差，并且固有地依赖于外部求解器。本文提出了一种无需求解器、基于采样的ILP优化框架，该框架直接探索离散可行区域，无需训练或外部求解器。利用ILP的线性结构，我们采用局部平衡提议来构建转移核，从而避免了梯度近似。为了克服ILP能量景观的高度多模态性，我们集成了Parallel Tempering。除了标准温度退火外，我们还引入了惩罚退火，它在保持可行解上的目标景观的同时，调节约束障碍。经验表明，我们的方法在所有四个基准测试中始终优于SCIP，在200秒预算内，在四个任务中的两个上匹配或超过Gurobi，并且比基于学习的方法对分布偏移的鲁棒性更高。此外，在MIPLIB 2017实例上，我们的框架在没有任何问题特定调整的情况下，仍然与经典求解器具有竞争力。

🔬 方法详解

问题定义：整数线性规划(ILP)旨在寻找满足一组线性约束的整数变量的最优解。现有方法，如精确求解器（Gurobi, SCIP）和启发式算法，计算成本高昂。而基于学习的方法虽然有进展，但泛化能力弱，依赖外部求解器，难以适应新的问题实例。

核心思路：本文的核心在于设计一种无需外部求解器和训练的采样方法，直接在离散可行域中搜索最优解。通过精心设计的转移核和Parallel Tempering策略，克服ILP问题解空间的多模态性，提高搜索效率。

技术框架：该框架主要包含以下几个部分：1) 局部平衡提议(Locally-Balanced Proposal)：利用ILP的线性结构，设计一种能够有效探索可行域的转移核，避免梯度近似。2) Parallel Tempering：采用多个不同温度的链并行搜索，高温链更容易跳出局部最优，低温链则负责精细搜索。3) 惩罚退火(Penalty Tempering)：在Parallel Tempering的基础上，引入约束惩罚项的退火，在保持可行解目标函数不变的情况下，调节约束的严格程度，进一步提高搜索效率。

关键创新：最重要的创新在于提出了一种完全无监督、无需求解器的采样优化方法，直接在离散可行域中进行搜索。通过局部平衡提议和Parallel Tempering的结合，有效克服了ILP问题解空间的多模态性，提高了搜索效率和鲁棒性。与现有方法相比，该方法不依赖外部求解器，具有更好的泛化能力。

关键设计：局部平衡提议的设计关键在于利用ILP的线性结构，保证转移核的局部平衡性，从而避免梯度近似。Parallel Tempering中，温度的选择和退火策略至关重要，需要根据具体问题进行调整。惩罚退火中，惩罚系数的设置需要在约束违反和目标函数优化之间进行权衡。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该方法在四个基准测试中始终优于SCIP，在200秒预算内，在四个任务中的两个上匹配或超过Gurobi。在MIPLIB 2017实例上，该框架在没有任何问题特定调整的情况下，仍然与经典求解器具有竞争力。更重要的是，该方法比基于学习的方法对分布偏移具有更强的鲁棒性，显示出良好的泛化能力。

🎯 应用场景

该研究成果可广泛应用于组合优化问题，如资源调度、生产计划、物流优化、网络设计等领域。其无需训练和外部求解器的特性，使其在资源受限或难以获取大量训练数据的场景下具有重要应用价值。未来，该方法有望扩展到更复杂的优化问题，并与其他优化技术相结合，进一步提升性能。

📄 摘要（原文）

Integer Linear Programming (ILP) serves as a versatile framework for modeling a wide range of combinatorial optimization problems, typically addressed by sophisticated exact solvers or heuristics. While learning-based approaches have recently shown their effectiveness, they suffer from poor generalization to out-of-distribution instances and inherent dependence on external solvers. In this work, we propose a solver-free, sampling-based optimization framework for ILP that directly explores discrete feasible regions without training or external solvers. Exploiting the linear structure of ILP, we employ a Locally-Balanced Proposal to construct a transition kernel, thereby avoiding the gradient approximation. To overcome the highly multimodal nature of ILP energy landscapes, we integrate Parallel Tempering. In addition to standard temperature tempering, we introduce penalty tempering, which modulates constraint barriers while preserving the objective landscape over feasible solutions. Empirically, our method consistently outperforms SCIP across all four benchmarks, matches or exceeds Gurobi on two of four tasks within a 200-second budget, and is substantially more robust to distribution shift than learning-based methods. Furthermore, on MIPLIB 2017 instances, our framework remains competitive with classical solvers without any problem-specific tuning.