# Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2019.

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

- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [Generative deep learning for decision making in gas networks](https://mlsanity.com/paper/2102.02125/) (2021)

## Abstract (arXiv)

Mixed Integer Programming (MIP) is one of the most widely used modeling techniques for combinatorial optimization problems. In many applications, a similar MIP model is solved on a regular basis, maintaining remarkable similarities in model structures and solution appearances but differing in formulation coefficients. This offers the opportunity for machine learning methods to explore the correlations between model structures and the resulting solution values. To address this issue, we propose to represent an MIP instance using a tripartite graph, based on which a Graph Convolutional Network (GCN) is constructed to predict solution values for binary variables. The predicted solutions are used to generate a local branching type cut which can be either treated as a global (invalid) inequality in the formulation resulting in a heuristic approach to solve the MIP, or as a root branching rule resulting in an exact approach. Computational evaluations on 8 distinct types of MIP problems show that the proposed framework improves the primal solution finding performance significantly on a state-of-the-art open-source MIP solver.