Learning Early-to-Final Solution Consistency for MILP Acceleration

Mixed-Integer Linear Programming (MILP) problems are notoriously difficult to solve due to their NP-hardness, and modern solvers often struggle to find high-quality solutions within practical time limits. While existing learning-based approaches attempt to accelerate solving by directly predicting solutions from static instance-level features like bipartite graphs, this task is extremely difficult because it approaches the complexity of solving the original MILP from scratch. This paper investigates whether leveraging information revealed during the solver's early search stage can make solution prediction significantly easier and more effective.

The authors observe that solutions produced during the early search stage of MILP solvers are computationally cheap to obtain and structurally very close to full-budget solutions, with discrepancies concentrating on a small subset of variables. Motivated by this insight, they propose a solver-informed paradigm called EnCore that shifts the learning target. Instead of predicting full solutions from scratch, the model estimates the early-to-final consistency: whether each variable's early-stage assignment should persist in the final, full-budget solution.

The framework combines a graph neural network with the early solution by augmenting variable nodes with their early assignments as input features. The model is trained using binary cross-entropy on consistency labels collected at the transition from fast descent to long exploration in the solver. At inference time, the method uses inference-time augmentation by ensembling predictions across the last few improving solutions to improve robustness. The resulting consistency scores are then used to rank variables, and top-ranked variables are fixed to their early-stage values to guide downstream search.