🤖 AI

Learning Early-to-Final Solution Consistency for MILP Acceleration

This paper proposes a novel solver-informed learning paradigm for MILP acceleration that predicts the consistency between early-stage and final solutions to guide search processes, significantly reducing primal gaps across diverse benchmarks and demonstrating strong zero-shot transferability between solvers like Gurobi and SCIP.

Original authors: Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of industrial planning and logistics, there is a class of problems that acts as the ultimate test of efficiency. These are complex puzzles where a computer must decide how to allocate limited resources—like trucks, workers, or electricity—while obeying a strict set of rules. The goal is always the same: find the single best arrangement among billions of possibilities. For decades, the most powerful tools for solving these puzzles have been mathematical engines that systematically explore every option, cutting away dead ends until the optimal answer emerges. While these engines are incredibly sophisticated, they face a fundamental wall: the time it takes to find the perfect answer can grow so fast that even the fastest supercomputers cannot finish the job within a practical timeframe. This limitation forces businesses to settle for "good enough" solutions, leaving money and efficiency on the table.

A team of researchers at Nanjing University and Nari Technology has proposed a new way to help these engines work faster, not by making the computer think harder, but by teaching it to trust its own early instincts. Their work, published in a recent study, introduces a method called EnCore. Instead of asking an artificial intelligence to predict the final, perfect answer from scratch—a task that is nearly as difficult as solving the problem itself—the researchers taught the system to look at the first few solutions the engine finds and decide which parts of those early guesses are likely to stay the same until the very end. By identifying these stable parts and locking them in place, the system can skip over vast sections of the search space, allowing the solver to focus its energy only on the variables that are still uncertain.

The core of this discovery lies in a simple observation about how these mathematical solvers behave. When a solver starts working on a difficult problem, it often finds a decent solution very quickly. As time goes on, the quality of the solution improves, but the changes become smaller and smaller. The researchers found that the variables in these early solutions are often already correct. In one specific type of problem involving auction bids, the early solution agreed with the final, perfect solution on more than 95 percent of the binary choices. The remaining differences were not scattered randomly across the entire problem; instead, they were concentrated on a small, specific set of variables that the solver was still struggling to resolve. This pattern suggested that the early solution was not just a random guess, but a highly informative map of the final answer.

To exploit this pattern, the researchers shifted the goal of their machine learning model. Traditional approaches try to predict the value of every single variable in the final solution based solely on the static description of the problem. The new approach, however, asks a different question: given the early solution the solver has already produced, which of those choices are likely to persist? The model is trained to look at the problem structure and the early solution together, then assign a confidence score to each variable. If the model is confident that a variable's value in the early solution will not change, that value is fixed. This creates a smaller, easier version of the original problem for the solver to finish. Because the fixed values come from a solution that the solver itself found to be valid, the new, smaller problem is guaranteed to be solvable, avoiding the risk of creating an impossible scenario.

The researchers tested this method on four different types of real-world optimization problems, ranging from combinatorial auctions to workload distribution. They integrated their model into existing search frameworks and compared the results against standard solvers running for the same amount of time. The results were significant. When paired with the Gurobi solver, the new method reduced the gap between the found solution and the best possible known solution by an average of 56.9 percent. In the case of combinatorial auctions, the method was so effective that it completely closed the gap, finding the best possible solution every time within the time limit. Perhaps most surprisingly, the model trained on data from one solver could be applied directly to a completely different solver without any retraining. When transferred to the SCIP solver, it still managed to reduce the error gap by an average of 36.4 percent, demonstrating that the insight about early-to-final consistency is a fundamental property of these problems, not just a quirk of a specific algorithm.

The study also explored how much time should be spent gathering these early solutions before the model takes over. The researchers found that a very short period was sufficient. Spending too much time waiting for the early solution to improve actually hurt performance, because it left less time for the solver to finish the job. The sweet spot was a brief initial phase where the solver ran for just a fraction of the total time, enough to produce a stable early solution but not so long that it wasted the budget. This balance allowed the system to leverage the speed of the early search while still benefiting from the precision of the final search.

By reframing the learning task from "predicting the answer" to "predicting what stays the same," the researchers have shown that machine learning can accelerate complex optimization by working in harmony with traditional solvers rather than trying to replace them. The method does not require the computer to understand the entire problem at once; instead, it guides the computer to trust the parts of the solution that have already proven stable. This approach offers a practical path forward for industries that rely on these calculations, potentially turning problems that once took hours to solve into tasks that can be completed in minutes, all while finding better, more efficient answers.

Technical Summary: Learning Early-to-Final Solution Consistency for MILP Acceleration

Problem Statement

Mixed-Integer Linear Programming (MILP) is a fundamental class of problems in operations research, yet modern solvers often struggle to find high-quality solutions for challenging instances within practical time limits due to inherent NP-hardness. While recent learning-based approaches attempt to accelerate solving by directly predicting high-quality solutions from static instance-level features (e.g., variable-constraint bipartite graphs), these methods face significant hurdles:

Complexity: Predicting a complete solution from static features alone approaches the complexity of solving the original MILP.
Information Loss: These methods largely overlook the rich information revealed during the solver's own search process.
Feasibility Risks: Directly predicting variable assignments often fails to guarantee feasibility, requiring complex trust-region strategies to mitigate errors.

The authors observe that solutions produced in the early stages of a solver's search (computationally cheap to obtain) are often structurally close to the final, full-budget solutions. However, existing paradigms do not effectively leverage this "early incumbent" information to guide the search.

Methodology: EnCore

The paper proposes EnCore, a solver-informed paradigm that shifts the learning target from variable assignment prediction to early-to-final solution consistency estimation.

Core Paradigm Shift

Instead of learning $P(X^* | G)$ (predicting the final solution $X^*$ from the graph $G$ ), EnCore learns $P(x^*_i = x^{ES}_i | G, X^{ES})$ .

Input: The MILP graph $G$ and an early-stage solution $X^{ES}$ collected during the solver's "fast descent" phase.
Target: For each integer variable $i$ , predict the probability that its assignment in the early solution ( $x^{ES}_i$ ) persists in the final full-budget solution ( $x^*_i$ ).
Label: A binary consistency label $y_i = \mathbb{1}[x^*_i = x^{ES}_i]$ .

Model Architecture

Graph Representation: The MILP is encoded as a bipartite graph with variable and constraint nodes.
Feature Fusion: The early solution assignments $X^{ES}$ are injected as additional features into the variable nodes.
Network: A bipartite Graph Neural Network (GNN) with half-convolutions processes the graph. It aggregates messages between variables and constraints to assess whether an early assignment is stable given the instance structure and neighboring assignments.
Output: A consistency probability $\hat{p}_i$ for each variable.

Inference and Search Integration

Ensemble Augmentation: To mitigate sensitivity to the specific early solution collected, the model processes the last $K$ improving solutions found during the collection phase. The predictions are aligned to a common reference ( $X^{ES}$ ) and averaged to produce a robust consistency score $\bar{p}_i$ .
Downstream Search: The consistency scores guide existing prediction-based search frameworks (e.g., Neural Diving, Predict-and-Search). Variables with high consistency scores are fixed to their early values.
- Feasibility Guarantee: Since fixed values are drawn from a feasible early solution, the resulting reduced MILP remains feasible.
- Search Focus: The solver focuses its remaining budget on variables deemed "unstable" by the model.

Early Solution Collection

The early solution $X^{ES}$ is collected by monitoring the solver's progress. The collection terminates when the local dual-gap decay rate falls below a threshold, indicating the transition from the "fast descent" stage to the "long exploration" stage.

Theoretical Contributions

The paper provides theoretical justification for the consistency paradigm:

Information Gain (Theorem 1): Under a "posterior-crossing" condition (where different early assignments compatible with the same instance structure favor different final values), conditioning on the early solution strictly increases the best achievable prediction accuracy compared to using instance features alone.
Finite-Sample Guarantee (Theorem 2): The authors prove that this accuracy gain persists even when the predictor is selected from finite training data. The sample complexity is reduced because the model only needs to learn a "sparse correction" (identifying the small subset of unstable variables) rather than reconstructing the entire solution.

Experimental Results

The method was evaluated on four MILP benchmarks (Combinatorial Auctions, Set Covering, Workload Apportionment, Item Placement) using Gurobi and SCIP.

Performance with Gurobi

Gap Reduction: EnCore reduced the primal gap by an average of 56.9% across diverse downstream pipelines (Neural Diving, Predict-and-Search, Apollo).
Combinatorial Auctions (CA): EnCore-PS completely closed the gap to the Best Known Solution (BKS) within a 1,000-second budget, outperforming a 3,600-second Gurobi run.
Other Benchmarks: Significant gap reductions were observed on Set Covering (43.5%), Workload Apportionment (47.8%), and Item Placement (60.0%).
Efficiency: EnCore variants catch up to and surpass baseline methods early in the runtime (e.g., within 71 seconds on CA) and maintain the lead.

Zero-Shot Transfer

Cross-Solver: A model trained on Gurobi data was applied directly to SCIP without retraining. It achieved a gap reduction of 53.6% on Combinatorial Auctions, 22.0% on Set Covering, 33.1% on Workload Apportionment, and 50.7% on Item Placement, demonstrating solver-agnostic transferability.
Cross-Family: When transferred to the unseen MIPLIB IIS benchmark, EnCore significantly improved feasibility (finding solutions on all 11 instances vs. 3 for the baseline) and objective quality, showing robustness to distribution shifts.

Ablation Studies

Target vs. Features: Reformulating the learning target to consistency prediction contributed more to performance gains than simply adding early solution values as input features.
Ensembling: Ensembling predictions across multiple early solutions provided additional robustness, particularly on Combinatorial Auctions.

Significance and Claims

The paper claims that EnCore offers a new, effective paradigm for MILP acceleration by:

Redefining the Learning Task: Moving from the difficult task of "predicting a solution from scratch" to the more tractable task of "assessing the stability of an existing solution."
Ensuring Feasibility: By fixing variables based on a feasible early solution, the method avoids the feasibility violations common in direct prediction methods.
Solver Agnosticism: The learned consistency representation captures structural patterns that transfer effectively across different solvers (Gurobi to SCIP) and problem families.
Theoretical Grounding: Providing formal proofs that conditioning on early solutions yields a strict information gain, justifying the shift in learning objectives.

The authors conclude that EnCore effectively accelerates prediction-guided search and generalizes well, suggesting future work could explore jointly learning consistency prediction and downstream search policies.