RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
For optimization practitioners, RL-SPH provides a reliable way to quickly obtain high-quality feasible solutions for NP-hard ILP problems, addressing the key limitation of prior end-to-end learning heuristics.
RL-SPH is a reinforcement learning-based primal heuristic for integer linear programming that independently generates feasible solutions with 100% feasibility, achieving 28.6× lower primal gap and 2.6× lower primal integral on average compared to existing methods.
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.