RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs

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.

Have you ever struggled to pack for a trip, wanting to bring too many things but limited by weight and volume? Many real-world tasks—such as vehicle routing and resource allocation—share this structure: choosing the most valuable combination while respecting many strict rules. Such problems can be formulated as integer linear programs (ILP). Yet finding valid solutions for ILP remains an unsolved challenge for machine learning (ML) alone, since the number of possible combinations explodes, making ILP notoriously hard. We propose RL-SPH, a reinforcement-learning method in which an agent learns through trial and error, like a person gets better at packing after several trips. The agent focuses on broken rules, identifies which adjustments would improve the solution, and searches for valid solutions. Guided by feedback that rewards both rule satisfaction and solution quality, it gradually learns to reach valid, high-quality solutions. RL-SPH consistently achieves these results on its own, without external optimization solvers. Moreover, while most standalone ML methods are limited to simple ‘yes or no’ decisions, RL-SPH handles general whole numbers—deciding not just 0 or 1, but exactly how many units are needed. This represents a crucial leap for solving complex real-world tasks.