不依赖训练和外部求解器，用采样方法解决整数线性规划问题。
Solving Integer Linear Programming with Parallel Tempering
- 基于局部平衡提议与平行退火，直接采样可行解空间。
- 在4个基准上优于SCIP，200秒内媲美或超过Gurobi。
- 对分布外数据鲁棒，无需调参即可在MIPLIB上保持竞争力。
整数线性规划（ILP）是建模组合优化问题的通用框架，通常由复杂精确求解器或启发式方法处理。尽管基于学习的方法近期表现有效，但其泛化能力差且依赖外部求解器。本文提出一种无训练、无外部求解器的采样优化框架，直接探索ILP的离散可行区域。利用ILP的线性结构，采用局部平衡提议构建转移核，避免梯度近似。为应对ILP能量景观的高度多模态特性，引入平行退火，并创新性地提出惩罚退火，调节约束障碍同时保持可行解的目标景观不变。实验表明，该方法在4个基准上持续优于SCIP，200秒内两个任务匹配或超越Gurobi，且对分布外数据的鲁棒性显著优于学习方法。在MIPLIB 2017实例上，无需特定调优即保持与经典求解器相当的性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。