AI Research

Learning Early-to-Final Solution Consistency for MI... | AI Research

Key Takeaways

Learning Early-to-Final Solution Consistency for MILP Acceleration introduces a method to improve the performance of Mixed-Integer Linear Programming (MILP)...
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.

Paper AbstractExpand

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.

Learning Early-to-Final Solution Consistency for MILP Acceleration introduces a method to improve the performance of Mixed-Integer Linear Programming (MILP) solvers by predicting which variable assignments from an early search stage will persist in the final, optimal solution. Instead of attempting to predict a complete solution from scratch, this approach uses the solver’s own early-stage output as a foundation, focusing the learning task on identifying stable assignments.

A New Paradigm for Solution Prediction

Traditional learning-based MILP methods typically attempt to predict a full solution directly from static instance features, such as variable-constraint bipartite graphs. The authors argue that this is a difficult task because it requires the model to solve the complexity of the original MILP. By observing that modern solvers make rapid progress in the early stages of a search, the researchers identified that early solutions are often structurally close to final solutions. Their method, EnCore, shifts the learning target to "early-to-final consistency," where the model estimates the probability that each variable's early assignment will remain unchanged in the final, full-budget solution.

How the Method Works

The EnCore approach integrates into existing solver pipelines by augmenting the bipartite graph representation of an MILP instance with the variable assignments from an early search stage. A graph neural network processes this combined input to produce a consistency score for each integer variable. During inference, the system can ensemble consistency predictions across multiple early solutions to improve robustness. These scores are then used to guide downstream search by fixing variables deemed highly consistent. Because these fixed values originate from a feasible early solution, this process preserves feasibility while allowing the solver to focus its computational resources on the remaining, unresolved variables.

Experimental Performance

The researchers evaluated their method using Gurobi and SCIP across four MILP benchmarks. When integrated with existing prediction-guided search frameworks, the method reduced the primal gap by an average of 56.9% using Gurobi. On combinatorial auction instances, the method closed the primal gap completely. Furthermore, the authors demonstrated the model's transferability; a model trained on Gurobi-generated data was applied to the SCIP solver without any additional training or adaptation, resulting in a 36.4% average reduction in the primal gap.

Theoretical Foundation

The authors provide a theoretical analysis to support the effectiveness of their approach. They prove that conditioning on an early solution can strictly increase the best achievable prediction accuracy compared to predicting from instance features alone. This gain is attributed to the information provided by the early solution, which reduces the uncertainty of the final variable assignments. The researchers conclude that this information gain persists even when the model is selected based on a finite number of training instances.

Comments (0)

No comments yet

Be the first to share your thoughts!