# Learning Primal Heuristics for Mixed Integer Programs

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 22 references that are in the map.
- First posted on arXiv 2 Jul 2021.

## Builds on (most cited first, 4 of 4)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)

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

- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Confidence Threshold Neural Diving](https://mlsanity.com/paper/2202.07506/) (2022)
- [Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks](https://mlsanity.com/paper/2311.13843/) (2023)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Grid-SiPhyR: An end-to-end learning to optimize framework for combinatorial problems in power systems](https://mlsanity.com/paper/2206.06789/) (2022)
- [Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling](https://mlsanity.com/paper/2211.14492/) (2022)
- [Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs](https://mlsanity.com/paper/2308.00327/) (2023)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [Learning to Condition: A Neural Heuristic for Scalable MPE Inference](https://mlsanity.com/paper/2509.25217/) (2025)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)
- [Improvement of Optimization using Learning Based Models in Mixed Integer Linear Programming Tasks](https://mlsanity.com/paper/2506.06291/) (2025)

## Abstract (arXiv)

This paper proposes a novel primal heuristic for Mixed Integer Programs, by employing machine learning techniques. Mixed Integer Programming is a general technique for formulating combinatorial optimization problems. Inside a solver, primal heuristics play a critical role in finding good feasible solutions that enable one to tighten the duality gap from the outset of the Branch-and-Bound algorithm (B&B), greatly improving its performance by pruning the B&B tree aggressively. In this paper, we investigate whether effective primal heuristics can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Convolutional Network on solved problem instances with known optimal solutions. This in turn can predict the values of decision variables in the optimal solution for an unseen problem instance of a similar type. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search (PB-DFS) approach, aiming to find (near-)optimal solutions quickly. The experimental results show that this new heuristic can find better primal solutions at a much earlier stage of the solving process, compared to other state-of-the-art primal heuristics.