mlsanityData to 14 Oct 2026

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

arXiv 2411.19517 ↗First posted 29 Nov 2024cs.LG cs.AIcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

36 of 83 references.

References · 36

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  5. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  6. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  7. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 613
  8. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  9. 2021A Survey of Transformerscited by 401
  10. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  11. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  12. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 195
24 more
  1. 2022On Embeddings for Numerical Features in Tabular Deep Learningcited by 186
  2. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  3. 2020Solving Mixed Integer Programs Using Neural Networkscited by 182
  4. 2020Graph-Bert: Only Attention is Needed for Learning Graph Representationscited by 177
  5. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 111
  6. 2022Transformer for Graphs: An Overview from Architecture Perspectivecited by 107
  7. 2020Hybrid Models for Learning to Branchcited by 95
  8. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 61
  9. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 50
  10. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  11. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 43
  12. 2023A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programmingcited by 41
  13. 2022The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insightscited by 39
  14. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  15. 2021Learning Large Neighborhood Search Policy for Integer Programmingcited by 35
  16. 2023End-to-End Feasible Optimization Proxies for Large-Scale Economic Dispatchcited by 35
  17. 2022Learning to Compare Nodes in Branch and Bound with Graph Neural Networkscited by 31
  18. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  19. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  20. 2021Learning Primal Heuristics for Mixed Integer Programscited by 14
  21. 2023Learning To Dive In Branch And Boundcited by 10
  22. 2021Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programmingcited by 8
  23. 2024Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusioncited by 8
  24. 2022Confidence Threshold Neural Divingcited by 5

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Accelerating Fleet Upgrade Decisions with Machine-Learning Enhanced Optimizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs
  2. 2022Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing
  3. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs
  4. 2025Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming
  5. 2024SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch
  6. 2022Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning
  7. 2025Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
  8. 2026Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming