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

arXiv: https://arxiv.org/abs/2411.19517 · HTML: https://mlsanity.com/paper/2411.19517/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 83 references that are in the map.
- First posted on arXiv 29 Nov 2024.

## Builds on (most cited first, 30 of 36)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [On Embeddings for Numerical Features in Tabular Deep Learning](https://mlsanity.com/paper/2203.05556/) (2022)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2402.16891/) (2024)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [End-to-End Feasible Optimization Proxies for Large-Scale Economic Dispatch](https://mlsanity.com/paper/2304.11726/) (2023)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)

## Built on by (most cited first, 1 of 1)

- [Accelerating Fleet Upgrade Decisions with Machine-Learning Enhanced Optimization](https://mlsanity.com/paper/2508.00915/) (2025)

## Abstract (arXiv)

Primal heuristics play a crucial role in quickly finding feasible solutions for NP-hard integer linear programming (ILP). Although textitend-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× lower primal gap and a 2.6× lower primal integral compared to existing start primal heuristics.