Logo image
Back
Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming
Preprint   Open access

Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming

Ruobing Wang, Xin Li, Yujie Fang and Mingzhong Wang
arXiv, Vol.25 March 2026
Cornell University
2026
DOI: https://doi.org/10.48550/arxiv.2603.24033
pdf
2603.24033v111.45 MBDownloadView
Preprint Version Open Access CC BY V4.0

Abstract

Predict-and-search (PaS) methods have shown promise for accelerating mixed-integer linear programming (MILP) solving. However, existing approaches typically assume variable independence and rely on deterministic single-point predictions, which limits solution diversityand often necessitates extensive downstream search for high-quality solutions. In this paper, we propose SRG, a generative framework based on Lagrangian relaxation-guided stochastic differential equations (SDEs), with theoretical guarantees on solution quality. SRG leverages convolutional kernels to capture inter-variable dependencies while integrating Lagrangian relaxation to guide the sampling process toward feasible and near-optimal regions. Rather than producing a single estimate, SRG generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG consistently outperforms existing machine learning baselines in solution quality. Moreover, SRG demonstrates strong zero-shot transferability: on unseen cross-scale/problem instances, it achieves competitive optimality with state-of-the-art exact solvers while significantly reducing computational overhead through faster search and superior solution quality.

Details

Metrics

1 Record Views
Logo image