- 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
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 zero-valued and 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, , , , and the total time budget are kept unchanged from the original paper.
| Method | CA Obj ↑ | CA Gap ↓ | SC Obj ↓ | SC Gap ↓ | WA Obj ↓ | WA Gap ↓ | IP Obj ↓ | IP Gap ↓ |
|---|---|---|---|---|---|---|---|---|
| ND | 94340.63 | 4287.36 | 123.62 | 0.25 | 707.10 | 0.24 | 14.15 | 2.43 |
| Random-ND | 97425.51 | 1202.48 | 127.67 | 4.30 | 715.32 | 8.46 | 13.14 | 1.42 |
| Heuristic-ND | 97431.62 | 1196.37 | 127.17 | 3.80 | 713.65 | 6.79 | 12.69 | 0.97 |
| EnCore-ND | 97847.92 | 780.07 | 123.58 | 0.21 | 707.03 | 0.17 | 13.47 | 1.75 |
| PS | 97906.20 | 721.79 | 123.60 | 0.23 | 707.09 | 0.23 | 12.08 | 0.36 |
| Random-PS | 97951.10 | 676.89 | 123.68 | 0.31 | 712.87 | 6.01 | 12.37 | 0.65 |
| Heuristic-PS | 98018.18 | 609.81 | 123.64 | 0.27 | 711.12 | 4.26 | 12.40 | 0.68 |
| EnCore-PS | 98627.99 | 0.00 | 123.50 | 0.13 | 706.98 | 0.12 | 11.95 | 0.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.
| Downstream | EnCore feasible | GCN feasible | Better / tie / worse (both feasible) | Paired mean primal gap: EnCore vs. GCN |
|---|---|---|---|---|
| PS | 226/233 (97.00%) | 203/233 (87.12%) | 28 / 161 / 14 | 52.39% vs. 83.07% (199) |
| ND | 226/233 (97.00%) | 69/233 (29.61%) | 56 / 12 / 1 | 962.09% vs. 19,602.45% (67) |
| Apollo | 228/233 (97.85%) | 222/233 (95.28%) | 28 / 172 / 22 | 48.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- 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.
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.
†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.