acceptodds
Under review as a conference paper at ICLR 2027

Learning Early-to-Final Solution Consistency for MILP Acceleration

Abstract

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.

Primary area:
optimization
Keywords:
Mixed-Integer Linear Programming, Learning to Optimize, Early-to-Final Consistency Prediction, Solver-Informed Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PqVdOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes EnCore, which predicts whether assignments in an early feasible MILP solution will persist in a full-budget reference solution. It augments a standard GNN with early-solution values, trains on consistency labels, and ensembles predictions to guide existing search frameworks. Experiments cover four benchmark families, cross-solver transfer, and a small MIPLIB subset.

Critical strengths
  • The motivation is practical: early feasible solutions provide useful information, and fixing assignments drawn from a common feasible solution preserves a feasible completion.
  • EnCore integrates with three downstream frameworks and improves 11 of 12 settings under Gurobi. Early-solution collection and inference are included in the total runtime budget.
  • The paper includes useful ablations separating early-solution features from consistency labels, together with cross-solver and cross-family evaluations.
Critical weaknesses
  • Limited demonstrated novelty. The method retains an existing GNN architecture and downstream search procedures, primarily adding early-solution features, consistency labels, and prediction ensembling. These changes may be useful, but their distinctive contribution needs stronger evidence and clearer positioning relative to incumbent-based neighborhood search.

  • Missing controls for the proposed mechanism. The experiments do not compare against random variable selection or empirical assignment-stability scores using the same early solutions, fixing budgets, and runtime. These controls would distinguish the value of learned consistency scoring from simply using feasible early assignments. Similarly, the MIPLIB feasibility improvement does not independently establish the quality of learned ranking: any subset fixed from a common feasible solution preserves a feasible completion.

  • Limited explanatory scope of the theory. Theorem 1 establishes the benefit of additional conditioning information. As Appendix F acknowledges, consistency and direct assignment prediction have the same Bayes accuracy under identical augmented inputs. Theorem 2 concerns a fixed finite rule class and empirical 0–1 risk minimization, rather than the actual GNN training and ranking-based fixing procedure. Neither result directly establishes improved downstream optimization performance.

  • Mixed robustness and insufficient uncertainty reporting. EnCore-Apollo improves only one of four benchmarks when transferred to SCIP. On MIPLIB, PS improves two instances and worsens one, while Apollo improves one and worsens one; the remaining cases tie. Repeated-run uncertainty and paired per-instance analysis would help assess small reported gains. Also, the in-study best mean objective used as the reference means that “100% gap reduction” should not be interpreted as certified optimality.

Questions for authors
  • Does the “+ES feature” ablation score and retain the same early assignments as EnCore, with identical selection rules? A direct predictor can score retention using p_i for an early value of one and 1 − p_i for zero. This matched comparison would better isolate the consistency target.
  • How does EnCore compare with random selection and empirical stability-based selection under the same early-solution pool, fixing budgets, and total runtime?
  • Can the authors provide uncertainty estimates and explain the degradation of EnCore-Apollo on three SCIP benchmarks?
6 comments

We thank you for the constructive comments and for recognizing the practical motivation of EnCore, its integration with multiple downstream frameworks, and the inclusion of collection and inference costs in our evaluation. We address the four weaknesses and three questions below.

Response to W1: Limited demonstrated novelty

Thank you for raising this important concern about novelty. We want to clarify that the novelty of EnCore comes from our study and exploitation of MILP solver behavior, rather than from any single specially designed component. We observe that solvers improve rapidly in the early stage and much more slowly afterwards, while early solutions already agree with full-budget solutions on most variables (e.g., 95.63% of binary variables on WA). We convert this observation into a practical design: early-solution-conditioned consistency prediction, which predicts which early assignments will agree with the full-budget solution rather than constructing a complete solution from scratch. To achieve this design, we use a sliding-window dual-gap decay criterion to identify the end of fast descent and collect an early solution; augment the GNN input with this solution so that the model is explicitly aware of the early-solution information; train with an early-to-final consistency target to focus learning on assignments that differ between early and full-budget solutions; align and ensemble predictions over recent early solutions to reduce sensitivity to fluctuations in any single solution; and retain high-consistency early assignments within ND, PS, or Apollo for downstream search. In this way, we leverage our observation in a simple yet effective manner.

Besides, we want to clarify the distinction from LNS methods based on iterative incumbent improvement, taking two typical LNS methods, Neural LNS [1] and SLNS [2], as examples. Neural LNS does not exploit solver-generated early solutions. SLNS uses fixed-duration probing without identifying the end of fast descent, which can spend unnecessary time on early-solution collection. Moreover, it still predicts the complete target solution without explicitly assessing consistency, and its use of these absolute-assignment predictions as sampling weights allows low-quality assignments to repeatedly influence subsequent LNS iterations. In contrast, EnCore collects early solutions adaptively according to solver progress and directly retains only their high-consistency assignments to guide downstream search. The experiments below demonstrate these advantages.

We added Neural LNS and SLNS as direct learned-LNS baselines under the same 1,000-second end-to-end budget. The table reports primal gaps; lower is better.

SolverBenchmarkNeural LNSSLNSBest EnCore (downstream)
GurobiCA1164.66150.690.00 (PS)
GurobiSC1.820.790.13 (PS)
GurobiWA0.591.050.12 (PS)
GurobiIP1.53†0.180.10 (Apollo)
SCIPCA940.681270.11920.35 (PS)
SCIPSC3.031.691.38 (ND)
SCIPWA3.0517.750.38 (ND)
SCIPIP4.11†6.583.19 (ND)

†For IP, 25 instances have no Neural LNS results due to infeasible constructed sub-MIPs; the averages cover the remaining 75. We therefore do not count these as like-for-like wins. Across the other six settings, the best EnCore integration achieves lower gaps than Neural LNS, and it achieves lower gaps than SLNS in all eight settings.

We have updated Section 1, Sections 5.1–5.2, Tables 1 and 2, and the appendix “Reproduction Details for Neural LNS and SLNS” to include these related works, direct comparisons, and reproduction details.

Response to W2 and Q2: Controls for the proposed mechanism and selection baselines

We appreciate your careful suggestions regarding both the selection controls and the MIPLIB evaluation. We address the two parts of this concern by conducting the requested random-selection and empirical assignment-stability experiments, and by expanding the MIPLIB evaluation from 11 instances to all 240 instances in the official MIPLIB 2017 benchmark set. The two controls test the value of learned consistency scoring against simple selection rules under matched early solutions, fixing budgets, and runtime, while the broader MIPLIB evaluation validates the proposed mechanism beyond its feasibility guarantee. Random selection performs poorly in most settings, empirical agreement yields inconsistent gains, and EnCore achieves higher feasibility, more per-instance wins, and lower paired gaps on MIPLIB. Together, these results show that the learned ranking provides benefits beyond merely using feasible early assignments.

Both controls are evaluated under ND and PS with Gurobi. Random-ND and Random-PS randomly select k0k_0 zero-valued and k1k_1 one-valued variables from the early solution and fix them to their early values. The consensus heuristic fixes variables whose values remain unchanged across the early-solution pool. For all methods, k0k_0, k1k_1, Δ\Delta, and the total time budget are kept unchanged from the original paper.

MethodCA Obj ↑CA Gap ↓SC Obj ↓SC Gap ↓WA Obj ↓WA Gap ↓IP Obj ↓IP Gap ↓
ND94340.634287.36123.620.25707.100.2414.152.43
Random-ND97425.511202.48127.674.30715.328.4613.141.42
Heuristic-ND97431.621196.37127.173.80713.656.7912.690.97
EnCore-ND97847.92780.07123.580.21707.030.1713.471.75
PS97906.20721.79123.600.23707.090.2312.080.36
Random-PS97951.10676.89123.680.31712.876.0112.370.65
Heuristic-PS98018.18609.81123.640.27711.124.2612.400.68
EnCore-PS98627.990.00123.500.13706.980.1211.950.23

Random selection generally performs poorly, indicating that merely fixing early-solution assignments brings little benefit. Compared with the original ND and PS predictors, the consensus heuristic improves only on CA under both pipelines and on IP under ND, and performs worse in the other five settings. EnCore outperforms the corresponding heuristic in seven of the eight settings, again with IP under ND as the sole exception. Together, these controls demonstrate that neither arbitrary selection nor simple agreement is sufficient; a neural consistency predictor is necessary to fully exploit early-solution information and achieve consistently strong performance.

Following your constructive guidance on the MIPLIB evaluation, we would like to emphasize that feasibility preservation is an intrinsic advantage of our mechanism. Fixing a subset of variables to their values in a feasible early solution never excludes that solution, so the restricted MILP remains feasible by construction; arbitrary predicted assignments do not have this guarantee. We further expanded our evaluation to all 240 instances in the official MIPLIB 2017 benchmark collection and now report feasibility, per-instance wins, and primal gaps, further demonstrating the superiority of EnCore beyond this guarantee. Feasibility and win/tie/loss statistics cover the 233 instances remaining after excluding seven officially infeasible instances. For paired primal gaps, we exclude both infeasible and open instances, together with those without a finite, nonzero official reference objective; the paired sample sizes are shown in parentheses.

DownstreamEnCore feasibleGCN feasibleBetter / tie / worse (both feasible)Paired mean primal gap: EnCore vs. GCN
PS226/233 (97.00%)203/233 (87.12%)28 / 161 / 1452.39% vs. 83.07% (199)
ND226/233 (97.00%)69/233 (29.61%)56 / 12 / 1962.09% vs. 19,602.45% (67)
Apollo228/233 (97.85%)222/233 (95.28%)28 / 172 / 2248.48% vs. 76.81% (217)

EnCore achieves higher feasibility in all three pipelines and finds feasible solutions on 23, 157, and 6 additional instances under PS, ND, and Apollo, respectively. It also records more wins than losses and lower paired mean primal gaps in all three pipelines. Together, the higher feasibility, per-instance wins, and lower paired gaps directly demonstrate the advantage of EnCore's learned ranking on MIPLIB.

We have updated Sections 5.1–5.2, Table 1, and the MIPLIB results table to include the random-selection and consensus controls and the full 240-instance MIPLIB evaluation.

Response to W3: Limited explanatory scope of the theory

We thank you for this careful assessment and appreciate the opportunity to clarify the scope and value of our theoretical analysis.

Within our idealized setting, Theorem 1 identifies when early-solution information yields a strict improvement in the best achievable prediction accuracy, through the posterior-crossing condition. This makes precise when the additional information provides a genuine predictive advantage over predictors without early-solution information. Under identical augmented inputs, consistency and direct assignment prediction have the same Bayes accuracy; the strict improvement established here comes from adding early-solution information to static predictors.

Theorem 2 shows that this advantage can persist with finite training data. When the information gain exceeds approximation and estimation errors, the learned consistency predictor can outperform any predictor using the same static receptive field without early-solution information, even one trained with unlimited data. Appendix F works out a concrete example with four candidate rules, where corrections occur on at most 1.8% of variables and the early-solution information improves class separation by 12%. In this example, 195 independent training instances are enough to certify the advantage with 90% confidence. This illustrative calculation shows the guarantee is practically meaningful and the required sample size stays modest, as long as the assumptions hold.

We are sorry that it is nearly impossible to establish a sound theoretical guarantee for downstream optimization performance in the practical setting. The GNN is trained by nonconvex stochastic optimization with validation-based checkpoint selection; top-(k0,k1)(k_0,k_1) selection depends jointly on other variables' scores and separate early-value budgets; and the downstream branch-and-bound process is discrete and adaptive. Modern solvers also deploy numerous primal heuristics whose highly complex triggering conditions and interacting mechanisms make their effects on the search trajectory difficult to characterize. Commercial solvers such as Gurobi are additionally closed-source, preventing direct analysis of their convergence behavior and convergence rates. These factors make a meaningful end-to-end analysis nearly impossible. To our knowledge, no existing work rigorously proves that learned solution predictions accelerate the full MILP solving process. Even the relevant analyses in Predict-and-Search and Apollo-MILP are limited to auxiliary subproblems, conditional prediction precision, or feasibility, leaving end-to-end acceleration theory largely open. Our analysis offers valuable theoretical insight into this open problem.

Thanks to your comment, we have revised Appendix F to add more explanations of the illustrative example and make the theoretical results clearer. In future work, we will explore end-to-end theoretical analyses that connect learned consistency predictions to downstream MILP solving performance.

Response to W4: Mixed robustness and insufficient uncertainty reporting

We appreciate your careful attention to robustness and uncertainty. We first clarify that our proposed method is EnCore, rather than EnCore-PS or any other specific variant. Its robustness is supported by improvements in 19 of the 24 matched benchmark–solver–downstream settings, including 11 of 12 settings under Gurobi and 8 of 12 under SCIP. We further evaluate robustness on all 240 MIPLIB 2017 instances. All three integrations achieve higher feasibility and lower paired mean gaps, while the per-instance win/tie/loss results provide a more detailed assessment than mean objectives alone.

A possible explanation for EnCore-Apollo's degradation under SCIP is that early-solution collection reduces Apollo's final correction round from 600 to 540 seconds; this limited exploration budget is particularly restrictive under SCIP because its solution-space exploration is much weaker than Gurobi's on these benchmarks. Following your suggestion, we have added this analysis to the appendix “Analysis of EnCore-Apollo under SCIP”.

For CA under Gurobi, we thank you for pointing out this potentially misleading expression. To avoid this misunderstanding, we have now revised Section 5.1 (Evaluation Protocol) of the main paper to explicitly define the BKS as the in-study best mean final objective among all evaluated methods, including the 3,600-second Gurobi reference.

Reviewer_jmbQOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes EnCore, a learning-based framework for accelerating Mixed-Integer Linear Programming (MILP) by predicting early-to-final solution consistency. Motivated by the observation that early feasible solutions often share most of their variable assignments with full-budget solutions, the authors reformulate the conventional solution prediction task into predicting whether each variable's early assignment will remain unchanged in the final solution.

Specifically, EnCore first collects an early feasible solution from a MILP solver and then uses a graph neural network (GNN) to predict the consistency of each integer variable's assignment. The predictions are used to guide downstream search by fixing high-confidence assignments or restricting the search neighborhood. The authors also introduce an inference-time ensemble mechanism that combines predictions from multiple early solutions to improve robustness.

The paper provides theoretical analyses of the informational advantage of conditioning on early solutions and a finite-sample guarantee for consistency prediction under certain assumptions. Experiments on four MILP benchmark families demonstrate improvements over existing prediction-guided search methods, including Neural Diving, Predict-and-Search, and Apollo-MILP. The authors further evaluate zero-shot transfer from Gurobi to SCIP and across problem families using MIPLIB instances, demonstrating the potential generalizability of the proposed approach.

Critical strengths
  1. Interesting idea: This paper proposes an interesting idea of predicting early-to-final solution consistency instead of directly predicting the final solution. This is simple but meaningful, as early solutions already contain useful information. I believe predict consistency of feasible solution can generate many insteresting applications of trained model.

  2. Good experiments: The authors test the method on four MILP benchmarks and three learning-based search methods. The results show good improvements, and the zero-shot experiments also demonstrate its potential generalizability.

Critical weaknesses
  1. Limited theoretical contribution: Theorem 1 mainly shows that adding early-solution information can improve prediction accuracy, which is quite intuitive. Theorem 2 considers a finite hypothesis class, which is different from the GNN used in practice. Thus, the theoretical results are not very strong.

  2. Missing simple heuristic baseline: Since the main idea is based on the stability of early solutions, it would be useful to compare with a simple heuristic that fixes variables whose values remain unchanged across several early solutions. This could better show the benefit of the proposed learning method.

Questions for authors

Have the authors considered updating the consistency predictions during the solving process? For example, after solving for some time, the model could use the new incumbent to predict consistency again and update the fixed variables. It would be interesting to test whether this iterative prediction-and-solving strategy can further improve performance compared with making predictions only once.

3 comments

We thank the reviewer for the positive assessment of EnCore and for the constructive comments. We address the two weaknesses and the question below.

Response to W1

We agree that the non-strict benefit of additional conditioning in Theorem 1 is intuitive and that the finite hypothesis class in Theorem 2 is an idealization of the GNN used in practice. To our knowledge, general guarantees connecting practical GNN training to the solution quality or runtime of a complete MILP solver remain largely open. Such an analysis must jointly account for nonconvex learning, discrete prediction-guided decisions, and adaptive branch-and-bound with interacting solver heuristics. This broader theoretical challenge motivates our use of a tractable setting to isolate the informational and statistical value of early solutions.

Within this setting, Theorem 1 identifies when early-solution information yields a strict improvement in the best achievable prediction accuracy, through the posterior-crossing condition. This makes precise when the additional information provides a genuine predictive advantage.

Theorem 2 shows that this advantage can persist with finite training data. When the information gain exceeds approximation and estimation errors, the learned consistency predictor can outperform any predictor using the same static receptive field without early-solution information, even one trained with unlimited data. Appendix F works out a concrete example with four candidate rules, where corrections occur on at most 1.8% of variables and the early-solution information improves class separation by 12%. In this example, 195 independent training instances are enough to certify the advantage with 90% confidence. This illustrative calculation shows the guarantee is practically meaningful and the required sample size stays modest, as long as the assumptions hold.

To our knowledge, no existing work rigorously proves that learned solution predictions accelerate the full MILP solving process. Even the relevant analyses in Predict-and-Search and Apollo-MILP are limited to auxiliary subproblems, conditional prediction precision, or feasibility, leaving end-to-end acceleration theory largely open. Our analysis offers valuable theoretical insight into this open problem.

Thanks to your comment, we have revised Appendix F to add more explanations of the illustrative example and make the theoretical results clearer.

Response to W2

Following your valuable suggestion, we added a model-free early-pool consensus heuristic and evaluated it with ND and PS under Gurobi. The heuristic fixes variables whose values remain unchanged across the early-solution pool, while k0k_0, k1k_1, Δ\Delta, and the total time budget were kept unchanged from the original paper. The table reports objectives and absolute gaps to the BKS.

MethodCA Obj ↑CA Gap ↓SC Obj ↓SC Gap ↓WA Obj ↓WA Gap ↓IP Obj ↓IP Gap ↓
ND94340.634287.36123.620.25707.100.2414.152.43
Heuristic-ND97431.621196.37127.173.80713.656.7912.690.97
EnCore-ND97847.92780.07123.580.21707.030.1713.471.75
PS97906.20721.79123.600.23707.090.2312.080.36
Heuristic-PS98018.18609.81123.640.27711.124.2612.400.68
EnCore-PS98627.990.00123.500.13706.980.1211.950.23

Compared with the original ND and PS predictors, the heuristic achieves better objectives only on CA under both pipelines and on IP under ND, while performing worse in the other five settings. Thus, simple early-solution agreement provides no consistent advantage over the original predictors. EnCore, by contrast, outperforms the corresponding heuristic in seven of the eight settings, with IP under ND as the sole exception. These results show that simple agreement alone is insufficient for reliable improvements, and that a neural consistency predictor is necessary to fully exploit early-solution information and achieve consistently strong performance across benchmarks and downstream pipelines.

We have updated Sections 5.1–5.2 and Table 1 to include this early-pool consensus control.

Response to Q1

We thank the reviewer for this very interesting suggestion. Following this idea, we conducted an iterative-refresh experiment under Apollo with Gurobi. At each correction round, the current incumbent is used as the new early-solution input to the network, and the consistency scores are recomputed for the next round. The results are reported below.

MethodCA ↑SC ↓WA ↓IP ↓
EnCore-Apollo98491.40123.57707.0311.82
EnCore-Apollo + iterative incumbent98435.52123.60707.0912.10

As shown, the iterative variant underperforms the original EnCore on all four metrics. We conjecture that this arises from the generalization gap incurred by applying a predictor trained on early-stage solutions to later intermediate incumbents. To bridge this gap, it may be helpful to design specialized data augmentation that represents intermediate solver states or to train separate networks for different solving stages. It may also be interesting to formulate when and how to refresh predictions as a sequential decision-making problem and explore reinforcement learning for learning such a policy. We view these as open directions for further investigation rather than conclusions established by the current experiments.

We have added this experiment to Section 5.3 and the appendix “Exploration of Dynamic Incumbent-Based Score Updates”.


We hope our response has addressed your concerns. If we have missed anything, please let us know.

Thank you for clarifying. I decide to keep my positive score.

Reviewer_RxsWOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2(+1)
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes EnCore, a solver-informed prediction framework for accelerating MILP search. Instead of directly predicting a target assignment from the static MILP graph, EnCore first obtains an early feasible solution and predicts, for each binary variable, whether its early assignment will remain unchanged in a full-budget solution. The resulting consistency scores are used to guide Neural Diving, Predict-and-Search, and Apollo-MILP. Experiments on four benchmark families show improved solution quality under Gurobi and useful transfer to SCIP and an eleven-instance MIPLIB subset.

Critical strengths
  1. The motivation is intuitive and well presented: an early solver incumbent already contains substantial information, so predicting whether its assignments will persist can be easier than reconstructing a high-quality solution from scratch.

  2. The evaluation is relatively thorough. The reported results consistently show that the proposed consistency prediction is effective across the main benchmarks and under solver transfer.

Critical weaknesses
  1. The novelty relative to learned large-neighborhood search is not sufficiently established. Prior work already conditions on an incumbent and learns which integer variables should be retained or released before solving a sub-MIP. In particular, Sonnerat et al. [1] learn a neighborhood-selection policy that predicts which variables to unassign from the current solution, while La Rocca et al. [2] use supervised predictions of a high-quality target solution to guide variable fixing relative to the current incumbent. These methods are conceptually close to EnCore's incumbent-conditioned consistency prediction, but they are not discussed or compared experimentally. The paper should clarify the distinction and include learned-LNS baselines under a comparable budget.

  2. The main empirical study covers only four benchmark families. More diverse and larger-scale MILP families should be included to demonstrate that the proposed prediction target remains effective beyond these relatively structured settings.

  3. The cross-family MIPLIB study contains only eleven unseen MIPLIB instances, and most of them are set-covering-like instances. This provides limited evidence for the claimed broad out-of-distribution generalization across MILP families.

  4. The paper reports the final top-(k0, k1) fixing budgets for each benchmark, but does not clearly explain how these values were selected. Since the fixing budget can materially affect downstream performance, the paper should report the tuning protocol and provide a sensitivity analysis over (k0, k1) (and, if applicable, the neighborhood radius).

[1] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. “Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs.” arXiv preprint arXiv:2107.10201, 2021.

[2] Charly Robinson La Rocca, Jean-François Cordeau, and Emma Frejinger. “Supervised Large Neighbourhood Search for MIPs.” arXiv preprint arXiv:2501.10778, 2025.

Questions for authors
  1. How does EnCore differ conceptually from incumbent-conditioned learned-LNS methods such as Sonnerat et al. [1] and Supervised LNS [2]? Can the authors provide direct comparisons under the same early incumbent, fixing budget, and solver budget?

  2. How were the top-(k0, k1) values selected for each benchmark and solver? Were they tuned only on validation instances? How sensitive are the results to these choices?

  3. Can the authors provide results on a broader and more heterogeneous set of large-scale MILPs, including a larger MIPLIB sample, to support the generalization claim?

3 comments

We thank the reviewer for the constructive comments and for pointing us to two interesting and closely related works. We would discuss the conceptual distinctions, present direct comparisons, and address the evaluation and parameter concerns below.

1. Distinction from learned LNS and direct comparisons (W1 & Q1)

We would like to clarify that the main contribution of EnCore is solver-informed early-to-final consistency prediction. Specifically, we obtain a high-quality early feasible solution from the solver at the end of its fast-descent phase, learn to predict which variable assignments will remain consistent with a full-budget reference solution, and selectively retain only the highly consistent assignments to guide subsequent search. This fundamentally distinguishes EnCore from Neural LNS [1], which relies on graph-only predictions without any early-solution involvement, and from SLNS [2], which differs from EnCore in both the acquisition and the usage of early solutions. We elaborate below.

Comparison with Neural LNS [1]. Neural LNS aims to improve the efficiency of LNS on large-scale MIPs by learning both the initial assignment and the neighborhood-selection decisions. It introduces Neural Diving into the initialization stage to rapidly obtain an initial feasible solution. To improve neighborhood search efficiency, it trains a neural network to imitate a local-branching expert, aiming to retain the quality of expert neighborhood selection at a lower computational cost. However, its initialization is constructed from Neural Diving style assignments predicted solely from the static MILP graph, without exploiting any early-solution information provided by the solver. Such graph-only predictions may yield partial assignments that are difficult to extend to feasible solutions, or that lead to low-quality initial solutions. In contrast, EnCore fixes variables using a partial assignment drawn directly from a feasible, high-quality early solution produced by the solver. As shown in Tables S1 and S2, EnCore outperforms Neural LNS on CA, SC, and WA under both Gurobi and SCIP, while on IP Neural LNS additionally fails to obtain a feasible initialization on 25 of the 100 instances.

Comparison with SLNS [2]. SLNS[2] is more closely related to EnCore, as both methods leverage early solutions to improve the prediction of target assignments. However, the two differ substantially in both the acquisition and the usage of early solutions.

Regarding acquisition, SLNS applies a fixed-budget collection procedure uniformly across all instances. In contrast, EnCore adopts an adaptive, solver-informed collection strategy that monitors the descent trend of the early solving process, thereby achieving a better trade-off between the time spent on early-solution collection and that reserved for subsequent search.

Regarding usage, EnCore selectively retains only high-confidence assignments for variable fixing or neighborhood constraints, with their values taken directly from a high-quality early solution that has already been improved during the fast-descent phase, so that every retained partial assignment is of high quality and guaranteed to be feasible. In contrast, SLNS uses its full predicted assignment to determine sampling weights without any confidence-based filtering, allowing low-confidence predictions to influence the search alongside reliable ones. Moreover, SLNS reuses the same predictions across all iterations, so the errors induced by incorrect predictions accumulate over the search. Tecnically, the variable-sampling distribution that SLNS adopts in its experiments is relatively flat and remains close to uniform random sampling. This choice places little trust in the network's predictions and instead falls back on random exploration. Consistent with this analysis, both our experiments and the original paper's MIPLIB evaluation (§5.5 of [2]) show that SLNS's prediction-based guidance offers limited and inconsistent gains. As shown in Tables S1 and S2, EnCore outperforms SLNS on every benchmark under both solvers, demonstrating that our adaptive acquisition and selective usage of early solutions constitute a more effective paradigm.

Implementation and evaluation. Following your constructive suggestion, we have added experiments to compare our EnCore with Neural LNS [1] and SLNS [2]. We used the official Neural LNS code and followed SLNS's published configuration to reproduce their implementations. Both methods are evaluated under the same 1,000-second end-to-end budget as EnCore, including early-solution collection, network inference, and subsequent solver search. For SLNS, this extends the default 600-second total budget to 1,000 seconds while retaining its 120-second probing phase. The tables report objectives and absolute primal gaps to the BKS (lower gaps are better).

We have updated Section 1, Sections 5.1–5.2, Tables 1 and 2, and the appendix “Reproduction Details for Neural LNS and SLNS” to include these related works, direct comparisons, and reproduction details.

Table S1. Gurobi results (1,000-second budget). Bold marks the best result.

MethodCA Obj ↑CA Gap ↓SC Obj ↓SC Gap ↓WA Obj ↓WA Gap ↓IP Obj ↓IP Gap ↓
ND94340.634287.36123.620.25707.100.2414.152.43
PS97906.20721.79123.600.23707.090.2312.080.36
Apollo98083.79544.20123.560.19707.060.2011.970.25
Neural LNS97463.341164.66125.191.82707.450.5913.20†1.53†
Supervised LNS98477.30150.69124.160.79707.911.0511.900.18
EnCore-ND97847.92780.07123.580.21707.030.1713.471.75
EnCore-PS98627.990.00123.500.13706.980.1211.950.23
EnCore-Apollo98491.40136.59123.570.20707.030.1711.820.10

Table S2. SCIP results (1,000-second budget). Bold marks the best result.

MethodCA Obj ↑CA Gap ↓SC Obj ↓SC Gap ↓WA Obj ↓WA Gap ↓IP Obj ↓IP Gap ↓
SCIP (1000s)94701.913926.08127.994.62709.062.2023.4911.77
ND94342.124285.87125.141.77707.330.4718.196.47
PS97097.461530.53125.031.66708.491.6317.025.30
Apollo97335.921292.07124.971.60708.431.5716.214.49
Neural LNS97687.31940.68126.403.03709.913.0515.79†4.11†
Supervised LNS97357.881270.11125.061.69724.6117.7518.306.58
EnCore-ND96641.431986.56124.751.38707.240.3814.913.19
EnCore-PS97707.64920.35125.041.67708.221.3616.134.41
EnCore-Apollo97293.511334.48125.382.01707.911.0517.395.67

†^{\dagger}For IP, Neural LNS results are averaged over the 75 instances with feasible Neural Diving initialization; the other methods cover all 100 instances.

We further conducted the experiment requested in Q1 by adapting Neural LNS and SLNS to use the same early incumbent, fixing budget, and solver budget as EnCore. The results are as follows.

BenchmarkNeural LNSSLNS
CA ↑97,418.73012198,455.6429
SC ↓131.56128.57
WA ↓720.60708.60
IP ↓16.37912084811.5335

Notably, replacing their original collection and search configurations with our early incumbent, fixing budget, and solver budget degrades Neural LNS and SLNS relative to their original versions in seven of the eight comparisons, with SLNS on IP as the only exception. This further demonstrates the advantage of our coordinated early-solution acquisition and utilization design, in which the acquisition strategy and the consistency-based retention mechanism are tailored to work together.

2. Larger and more diverse evaluation on MIPLIB (W2, W3 & Q3)

Following your constructive suggestions, we expanded the MIPLIB evaluation from 11 instances to all 240 instances in the official MIPLIB 2017 benchmark set, using the same MIPLIB evaluation budget as in the main paper. Feasibility and win/tie/loss statistics cover the 233 instances remaining after excluding seven officially infeasible instances. Each pipeline compares EnCore with its original GCN predictor.

DownstreamEnCore feasibleGCN feasibleOnly EnCore feasibleBetter / tie / worse (both feasible)Paired mean primal gap: EnCore vs. GCN
PS226/233 (97.00%)203/233 (87.12%)2328 / 161 / 1452.39% vs. 83.07% (199)
ND226/233 (97.00%)69/233 (29.61%)15756 / 12 / 1962.09% vs. 19,602.45% (67)
Apollo228/233 (97.85%)222/233 (95.28%)628 / 172 / 2248.48% vs. 76.81% (217)

For these minimization instances, the primal gap is (f(x)−fofficial⋆)/∣fofficial⋆∣×100%\bigl(f(x)-f^\star_{\mathrm{official}}\bigr)/\lvert f^\star_{\mathrm{official}}\rvert\times100\%, where f(x)f(x) is the returned objective value and fofficial⋆f^\star_{\mathrm{official}} is the official reference optimum. Paired mean gaps use only instances for which both methods find feasible solutions and a finite, nonzero official reference optimum is available; instances officially marked as open or infeasible are excluded from gap statistics. This leaves 199, 67, and 217 paired instances for PS, ND, and Apollo, respectively, as indicated in parentheses; the broader feasibility and win/tie/loss statistics do not require a reference optimum.

EnCore achieves higher feasibility and lower paired mean gaps in all three pipelines. It finds feasible solutions for 23, 157, and 6 additional instances under PS, ND, and Apollo, respectively, while covering every instance solved feasibly by the corresponding GCN baseline. Among instances where both methods find feasible solutions, EnCore records more wins than losses in each pipeline.

We have updated Section 5.2 (Zero-shot cross-family transfer to MIPLIB) and the appendix “Benchmark Details” with the full 240-instance evaluation.

3. Neighborhood parameters

We adopt the published (k0,k1)(k_0,k_1) configurations of Neural Diving, Predict-and-Search, and Apollo-MILP unchanged. Each EnCore variant uses the same fixing budgets as its corresponding baseline.

We further conducted a fixing-budget sensitivity analysis on CA and WA under PS and ND. The results are as follows; the original CA and WA results are included as references.

BenchmarkPipelineFixing ratioEnCore ObjGCN Obj
CA ↑PS30%98531.8298332.25
CA ↑PS (reference)40%98627.9997906.20
CA ↑PS50%98441.6595967.09
CA ↑PS70%97856.7783730.85
CA ↑ND30%98155.8296619.68
CA ↑ND (reference)40%97847.9294340.63
CA ↑ND50%97549.7890539.19
CA ↑ND70%97423.5573055.73
WA ↓PS30%707.04707.15
WA ↓PS (reference)50%706.98707.09
WA ↓PS70%711.39718.03
WA ↓ND30%707.16707.22
WA ↓ND (reference)50%707.03707.10
WA ↓ND70%714.16724.15

The new CA runs use 100 instances and a 940-second solving budget per instance, varying k0k_0 while keeping k1=0k_1=0. The reference rows use the original (k0,k1)=(600,0)(k_0,k_1)=(600,0) configuration for CA and (0,500)(0,500) for WA. EnCore maintains an advantage over GCN across all ten tested configurations on CA and WA.

We have added this fixing-budget sensitivity analysis to Section 5.3 and the appendix “Fixing-Budget Sensitivity”.

References

[1] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs. arXiv:2107.10201, 2021.

[2] Charly Robinson La Rocca, Jean-François Cordeau, and Emma Frejinger. Supervised Large Neighbourhood Search for MIPs. arXiv:2501.10778, 2025. Sections 4.1–4.2, 5.2, and 5.5–5.6.


We hope our response has addressed your concerns. If we have missed anything, please let us know.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

Dear Reviewers and Area Chair,

Thank you for your reviews. We summarize the added experiments and revisions below.

Distinction from learned LNS and direct comparisons (RxsW, PqVd). EnCore uses solver progress to collect early feasible solutions adaptively, predicts which assignments will persist in a full-budget reference solution, and selectively retains high-consistency early assignments to guide existing search pipelines. We clarified its distinction from Neural LNS and Supervised LNS (SLNS) and added both as direct baselines under the same 1,000-second end-to-end budget, including collection, inference, and downstream search. The best EnCore integration achieves lower reported gaps than both Neural LNS and SLNS in all eight benchmark–solver settings. (Section 1, Sections 5.1–5.2, Tables 1–2, Appendix D.2)

Value of learned selection (jmbQ, PqVd). We added random selection and a model-free early-pool consensus heuristic under ND and PS, matching early solutions, fixing budgets, and total runtime. EnCore outperforms each control in seven of eight benchmark–pipeline settings. Consensus also yields no consistent gains. These controls support the value of learned consistency scoring beyond simply retaining feasible early assignments or selecting variables by empirical agreement. (Sections 5.1–5.2, Table 1)

Matched direct-prediction ablation (PqVd). Following the reviewer's suggestion, we converted direct assignment probabilities into retention scores and used the same early assignments and selection rule as EnCore. Consistency supervision achieves better objectives on all four benchmarks, supporting its practical benefit under this matched comparison. (Section 5.3, Table 4)

Full MIPLIB evaluation (RxsW, PqVd). We expanded the cross-family study from 11 instances to all 240 instances in the official MIPLIB 2017 benchmark collection, with no MIPLIB training or validation and the same 3,600-second end-to-end budget for both predictors. Excluding seven officially infeasible instances, EnCore finds feasible solutions on 226, 226, and 228 of 233 instances under PS, ND, and Apollo, respectively, covering every instance solved feasibly by GCN and 23, 157, and 6 additional instances. It also records more wins than losses among jointly feasible instances and lower paired mean primal gaps in all three pipelines. (Section 5.2, Table 3, Appendix D.1)

Fixing-budget sensitivity (RxsW). Each EnCore integration adopts its baseline's published fixing budgets unchanged. We added ten fixing-budget configurations on CA and WA under ND and PS; EnCore outperforms GCN in every additional configuration, demonstrating gains across a range of fixing ratios. (Section 5.3, Appendix H)

Robustness and uncertainty (PqVd). We clarified that EnCore is a general consistency-prediction framework rather than a particular downstream variant, instantiated as EnCore-ND, EnCore-PS, and EnCore-Apollo. Its robustness is supported by improvements over the corresponding predictors in 19 of 24 benchmark–solver–pipeline settings. Six-seed experiments on CA under PS give higher mean objectives in all six seeds (mean paired improvement 736.27; seed-level 95% CI [710.14, 762.39]). A paired instance-cluster bootstrap also gives an interval entirely above zero. We added an analysis of EnCore-Apollo under SCIP, identifying the shortened final correction budget as a possible contributor to its performance. Section 5.1 now explicitly defines the BKS as the in-study best mean final objective among all evaluated methods, including the 3,600-second Gurobi reference. (Sections 5.1–5.3, Appendices I–J)

Theoretical analysis (jmbQ, PqVd). We further clarified the contributions of our theoretical analysis. Theorem 1 identifies the posterior-crossing condition under which early-solution information yields a strict improvement in the best achievable prediction accuracy over predictors using the same static receptive field. Theorem 2 establishes that this advantage persists with finite training data when the information gain exceeds approximation and estimation errors in the finite-rule setting. The expanded illustrative calculation gives a sufficient sample size of 195 independent instances at 90% confidence under its stated assumptions. (Section 4, Appendix F)

Dynamic incumbent-based updates (jmbQ). We further explored dynamic score updates, recomputing consistency scores from the current incumbent at each Apollo correction round. This variant underperforms frozen early-solution scores on all four benchmarks. We report this negative result and discuss a possible training–inference distribution mismatch, with stage-specific training and learned refresh policies as future directions. (Section 5.3, Appendix G)

We have provided detailed replies to all questions raised by the reviewers in our individual responses. Thank you again for your time and feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.