# A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2023.

## Built on by (most cited first, 30 of 41)

- [A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability](https://mlsanity.com/paper/2310.02807/) (2023)
- [MILP-StuDio: MILP Instance Generation via Block Structure Decomposition](https://mlsanity.com/paper/2410.22806/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2401.10467/) (2024)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [PROPEL: Supervised and Reinforcement Learning for Large-Scale Supply Chain Planning](https://mlsanity.com/paper/2504.07383/) (2025)
- [When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach](https://mlsanity.com/paper/2501.14211/) (2025)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming](https://mlsanity.com/paper/2508.18742/) (2025)
- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [Enforcing convex constraints in Graph Neural Networks](https://mlsanity.com/paper/2510.11227/) (2025)
- [Graph Neural Networks for the Offline Nanosatellite Task Scheduling Problem](https://mlsanity.com/paper/2303.13773/) (2023)
- [Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching](https://mlsanity.com/paper/2305.12352/) (2023)
- [Network Interdiction Goes Neural](https://mlsanity.com/paper/2405.16409/) (2024)
- [Learning optimal objective values for MILP](https://mlsanity.com/paper/2411.18321/) (2024)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization](https://mlsanity.com/paper/2501.17377/) (2025)
- [Code Retrieval for MILP Instance Generation](https://mlsanity.com/paper/2505.11526/) (2025)
- [ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs](https://mlsanity.com/paper/2512.10211/) (2025)
- [A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention](https://mlsanity.com/paper/2601.04509/) (2026)
- [FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming](https://mlsanity.com/paper/2507.23390/) (2025)
- [HyP-ASO: A Hybrid Policy-based Adaptive Search Optimization Framework for Large-Scale Integer Linear Programs](https://mlsanity.com/paper/2509.15828/) (2025)
- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)
- [Machine Learning Guided Optimal Transmission Switching to Mitigate Wildfire Ignition Risk](https://mlsanity.com/paper/2510.25147/) (2025)
- [Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization](https://mlsanity.com/paper/2511.19573/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)

## Abstract (arXiv)

Mixed-integer linear programming (MILP) is widely employed for modeling combinatorial optimization problems. In practice, similar MILP instances with only coefficient variations are routinely solved, and machine learning (ML) algorithms are capable of capturing common patterns across these MILP instances. In this work, we combine ML with optimization and propose a novel predict-and-search framework for efficiently identifying high-quality feasible solutions. Specifically, we first utilize graph neural networks to predict the marginal probability of each variable, and then search for the best feasible solution within a properly defined ball around the predicted solution. We conduct extensive experiments on public datasets, and computational results demonstrate that our proposed framework achieves 51.1% and 9.9% performance improvements to MILP solvers SCIP and Gurobi on primal gaps, respectively.