RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs
This addresses the challenge of ensuring feasibility in primal heuristics for ILP, which is critical for combinatorial optimization, though it appears incremental by extending learning-based methods to non-binary variables.
The paper tackled the problem of generating feasible solutions for integer linear programs (ILP), especially with non-binary integer variables, and proposed RL-SPH, a reinforcement learning-based start primal heuristic that independently produces feasible solutions, achieving on average a 44x lower primal gap and 2.3x lower primal integral compared to existing methods.
Integer linear programming (ILP) is widely utilized for various combinatorial optimization problems. Primal heuristics play a crucial role in quickly finding feasible solutions for NP-hard ILP. Although $\textit{end-to-end learning}$-based primal heuristics (E2EPH) have recently been proposed, they are typically unable to independently generate feasible solutions and mainly focus on binary variables. Ensuring feasibility is critical, especially when handling non-binary integer variables. 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. Experimental results demonstrate that RL-SPH rapidly obtains high-quality feasible solutions, achieving on average a 44x lower primal gap and a 2.3x lower primal integral compared to existing primal heuristics.