Search papers, labs, and topics across Lattice.
This paper introduces a novel solver-informed paradigm for Mixed-Integer Linear Programming (MILP) that enhances solution prediction by focusing on early-to-final solution consistency. By predicting whether early-stage variable assignments should persist in full-budget solutions, the method effectively guides the search process and improves the quality of solutions found. Experimental results demonstrate a significant average reduction of 56.9% in the primal gap when using this approach with Gurobi, and a successful zero-shot transfer to SCIP achieving a 36.4% gap reduction across benchmarks.
Early-stage solutions can reliably inform final outcomes, leading to a 56.9% reduction in the primal gap for MILP problems.
Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.
