# Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 18 Jun 2024.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [SegDiff: Image Segmentation with Diffusion Probabilistic Models](https://mlsanity.com/paper/2112.00390/) (2021)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Diffusion Models Beat GANs on Topology Optimization](https://mlsanity.com/paper/2208.09591/) (2022)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Enabling Research through the SCIP Optimization Suite 8.0](https://mlsanity.com/paper/2303.07101/) (2023)
- [Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation](https://mlsanity.com/paper/2308.06644/) (2023)

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

- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Are Your Generated Instances Truly Useful? GenBench-MILP: A Benchmark Suite for MILP Instance Generation](https://mlsanity.com/paper/2505.24779/) (2025)
- [Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming](https://mlsanity.com/paper/2508.18742/) (2025)
- [RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs](https://mlsanity.com/paper/2411.19517/) (2024)
- [FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming](https://mlsanity.com/paper/2507.23390/) (2025)
- [Constraints-Guided Diffusion Reasoner for Neuro-Symbolic Learning](https://mlsanity.com/paper/2508.16524/) (2025)
- [Solving Integer Linear Programming with Parallel Tempering](https://mlsanity.com/paper/2605.29366/) (2026)
- [SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2608.25282/) (2026)

## Abstract (arXiv)

Feasible solutions are crucial for Integer Programming (IP) since they can substantially speed up the solving process. In many applications, similar IP instances often exhibit similar structures and shared solution distributions, which can be potentially modeled by deep learning methods. Unfortunately, existing deep-learning-based algorithms, such as Neural Diving and Predict-and-search framework, are limited to generating only partial feasible solutions, and they must rely on solvers like SCIP and Gurobi to complete the solutions for a given IP problem. In this paper, we propose a novel framework that generates complete feasible solutions end-to-end. Our framework leverages contrastive learning to characterize the relationship between IP instances and solutions, and learns latent embeddings for both IP instances and their solutions. Further, the framework employs diffusion models to learn the distribution of solution embeddings conditioned on IP representations, with a dedicated guided sampling strategy that accounts for both constraints and objectives. We empirically evaluate our framework on four typical datasets of IP problems, and show that it effectively generates complete feasible solutions with a high probability (> 89.7 %) without the reliance of Solvers and the quality of solutions is comparable to the best heuristic solutions from Gurobi. Furthermore, by integrating our method's sampled partial solutions with the CompleteSol heuristic from SCIP, the resulting feasible solutions outperform those from state-of-the-art methods across all datasets, exhibiting a 3.7 to 33.7% improvement in the gap to optimal values, and maintaining a feasible ratio of over 99.7% for all datasets.