用强化学习优化大规模整数规划求解速度
HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
- 结合公式与强化学习动态选择变量邻域
- 在多个数据集上显著快于现有方法
- 轻量高效，适合超大规模问题
直接使用传统求解器求解大规模整数线性规划（ILP）因其NP难性质而效率低下。尽管基于大邻域搜索（LNS）的框架可加速求解，但其性能常受限于难以生成足够有效的邻域。为此，我们提出HyP-ASO——一种混合策略的自适应搜索优化框架，融合定制公式与深度强化学习（RL）。公式利用可行解计算每个变量在邻域生成中的选择概率，而RL策略网络则预测邻域大小。大量实验表明，HyP-ASO在大规模ILP上显著优于现有LNS方法。额外实验显示其轻量且高度可扩展，非常适用于大规模ILP求解。
原文摘要 · Abstract (English)
Directly solving large-scale Integer Linear Programs (ILPs) using traditional solvers is slow due to their NP-hard nature. While recent frameworks based on Large Neighborhood Search (LNS) can accelerate the solving process, their performance is often constrained by the difficulty in generating sufficiently effective neighborhoods. To address this challenge, we propose HyP-ASO, a hybrid policy-based adaptive search optimization framework that combines a customized formula with deep Reinforcement Learning (RL). The formula leverages feasible solutions to calculate the selection probabilities for each variable in the neighborhood generation process, and the RL policy network predicts the neighborhood size. Extensive experiments demonstrate that HyP-ASO significantly outperforms existing LNS-based approaches for large-scale ILPs. Additional experiments show it is lightweight and highly scalable, making it well-suited for solving large-scale ILPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。