Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming
This addresses computational bottlenecks in MILP solving for optimization practitioners, though it is incremental as it builds on existing predict-and-search methods.
The paper tackles the problem of limited solution diversity and computational overhead in predict-and-search methods for mixed-integer linear programming (MILP) by proposing SRG, a generative framework that produces diverse, high-quality solution candidates. The result is consistent outperformance of existing machine learning baselines in solution quality across benchmarks, with strong zero-shot transferability achieving competitive optimality with state-of-the-art exact solvers while significantly reducing computational overhead.
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 \textbf{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.