用强化学习设计新启发式，能独立生成整数规划可行解。
RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
- 基于强化学习构建可独立生成解的启动启发式
- 可行性达100%，原始间隙平均降低28.6倍
- 适合需快速高质量解的整数规划场景
在求解NP难的整数线性规划（ILP）问题时，初始启发式对快速获得可行解至关重要。尽管已有端到端学习型启发式（E2EPH）被提出，但通常无法独立生成可行解。为此，我们提出一种基于强化学习的新型启动启发式RL-SPH，能够独立生成可行解，即使面对非二值整数变量的ILP也适用。实验表明，RL-SPH能快速获得高质量可行解，可行性率达100%，平均原始间隙比现有启动启发式降低28.6倍，原始积分降低2.6倍。
原文摘要 · Abstract (English)
Primal heuristics play a crucial role in quickly finding feasible solutions for NP-hard integer linear programming (ILP). Although $\textit{end-to-end learning}$-based primal heuristics (E2EPH) have recently been proposed, they are typically unable to independently generate feasible solutions. To address this challenge, we propose RL-SPH, a novel reinforcement learning-based start primal heuristic capable of independently generating feasible solutions, even for ILP involving non-binary integers. Empirically, RL-SPH rapidly obtains high-quality feasible solutions with a 100% feasibility rate, achieving on average a 28.6$\times$ lower primal gap and a 2.6$\times$ lower primal integral compared to existing start primal heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。