Unsupervised Neural Langevin Sampler for Mixed Integer Linear Programming

Existing neural combinatorial optimization (CO) solvers often rely heavily on expensive labeled data and additional post-processing to produce feasible solutions. Research into mixed integer linear programs (MILPs) is particularly limited due to the lack of effective heuristics for feasibility and the challenge of modeling mixed-type variables for neural solvers. To address these issues, we propose a novel unsupervised Langevin sampler for solving MILPs. Our framework learns only integer variables, while continuous variables are solved using an exact linear programming solver, thus isolating the combinatorial hardness of the problem and avoiding unnecessary modeling complexity. The sampler is based on Langevin dynamics and incorporates both objective optimization and constraint satisfaction into a unified energy function, enabling the model to jointly learn feasibility and optimality. Experiments demonstrate that our method achieves 100\% feasibility without expensive post-processing and matches or outperforms supervised solvers on benchmark datasets, highlighting its effectiveness and scalability. Our code can be found at https://github.com/CindyH1103/UNLS4MILP.

We propose a new unsupervised neural solver for solving mixed integer linear programs without labeled data or expensive post-processing. Our approach focuses on learning the difficult discrete decisions, while classical optimization solvers handle the continuous ones. The method is designed to simultaneously improve solution quality and satisfy constraints during the solving process. Experiments show that our approach consistently produces feasible solutions and can outperform existing supervised learning methods on benchmark optimization tasks.