Paper deep dive
Learning Early-to-Final Solution Consistency for MILP Acceleration
Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang, Ke Xue, Jixiang Lu, Weiyong Yang, Chao Qian
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/21/2026, 3:57:15 AM
Summary
The paper proposes EnCore, a solver-informed paradigm for accelerating Mixed-Integer Linear Programming (MILP) solving. Instead of predicting full solutions from static instance features, EnCore predicts 'early-to-final consistency'—the probability that an assignment from an early, cheap-to-obtain solver stage persists in the final solution. This approach leverages the observation that early solutions are structurally close to final ones. The method integrates with downstream search pipelines (like Predict-and-Search) to fix consistent variables, reducing the search space. Experiments show significant primal gap reductions (56.9% average with Gurobi) and successful zero-shot transfer to SCIP.
Entities (8)
Relation Signals (6)
ENCORE → evaluatedwith → Gurobi
confidence 95% · We evaluate our method on multiple MILP benchmarks with Gurobi (13) as the target solver
ENCORE → solves → MILP
confidence 95% · we propose a new solver-informed paradigm... for MILP Acceleration
ENCORE → uses → Early-to-Final Consistency
confidence 95% · we propose an Early-to-final solution Consistency prediction paradigm, termed EnCore.
Guanlin Li → authored → ENCORE
confidence 90% · Learning Early-to-Final Solution Consistency for MILP Acceleration Guanlin Li
ENCORE → improves → Predict-and-Search
confidence 90% · it reduces the primal gap of Predict-and-Search (14) by 56.9% on average
ENCORE → transferredto → SCIP
confidence 90% · we transferred the Gurobi-trained model zero-shot to SCIP without adaptation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.19953v1
- Canonical: https://arxiv.org/abs/2608.19953v1
Trouble viewing inline? Open PDF directly →
Full Text
89,413 characters extracted from source content.
Expand or collapse full text
Learning Early-to-Final Solution Consistency for MILP Acceleration Guanlin Li Chengrui Gao Chenguang Wang Haopu Shang Zherong Zhang Ke Xue Jixiang Lu Weiyong Yang Chao Qian Thanks: Corresponding author. Email: qianc@lamda.nju.edu.cn. 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. Code is available at: https://github.com/lamda-bbo/EnCore. 1 Introduction Mixed-Integer Linear Programming (MILP) is a fundamental modeling language for combinatorial optimization and decision making, with broad applications in scheduling (8), routing (20), network design (5) and production planning (27). Prevailing MILP solvers employ branch-and-bound (19) frameworks to systematically explore the combinatorial search space while guaranteeing optimality. Built upon this, the MILP community has developed a variety of sophisticated techniques (28; 1) over the past decades, including presolve, cutting planes, primal heuristics, and branching strategies, which further reduce the search space and accelerate the solving process. However, solving MILP remains computationally expensive for modern solvers due to their inherent NP-hardness (17). In real-world applications, most MILP instances are derived from similar problem classes with varying parameters, exhibiting shared structural patterns that can be naturally exploited by machine learning methods. As investigated by 3, learning models can capture these patterns from instance characteristics and historical solving experiences, and infer effective optimization strategies. Such learned knowledge can be integrated into MILP solvers to accelerate the optimization process (10; 23; 26). Existing learning-based methods for MILP can be broadly classified into three types: (1) learning solver decisions, where machine learning models are employed to guide individual solver component, such as branching, node selection, and cutting plane selection (18; 10; 12; 7; 32; 24; 31); (2) learning solver configurations, where models automatically tune algorithmic parameters or select suitable configurations for different instances (15; 23); and (3) learning solution predictions, where models directly predict complete or partial solutions to provide high-quality initial solutions or reduce the search space (26). Among the solution prediction methods, recent advances have focused on two directions: improving learning-guided search mechanisms and enhancing prediction capacity. On the search side, early studies such as neural diving (26) fixed high-confidence variable assignments predicted by neural models, producing reduced MILP instances for efficient downstream optimization. Building upon this idea, 14 replaced hard variable fixing with a trust-region search strategy, reducing the risk of being trapped by inaccurate assignment. More recently, 25 proposed to alternate prediction with trust-region correction, further improving robustness against prediction errors. On the prediction side, 34 represented MILPs as geometric feature sequences and used multi-scale attention to overcome expressiveness limitations of graph-based models. Meanwhile, 22 introduced a flow-matching generator that jointly models integer and continuous variables to enhance solution generation quality, while 29 exploited variable interactions through inter-variable contrastive learning and an intra-constraint competitive graph network. However, these methods still follow the conventional paradigm of predicting a complete solution directly from the MILP formulation. Under this paradigm, the model is required to determine all variable assignments, leading to a prediction task that approaches the complexity of solving the original MILP. In this paper, we begin by analyzing how primal solutions evolve during the search of modern MILP solvers. Across all evaluated benchmarks, we observe that the solution quality improves rapidly in the early stage of the search and then progresses much more slowly with only local corrections, indicating that early incumbents are highly informative about the final, full-budget assignments. On workload apportionment, for instance, an early incumbent already agrees with the final solution on 95.63%95.63\% of the binary variables (as shown in Figure 2). Given such an informative starting point, the optimal solution need not be reconstructed from scratch. Conditioned on what the solver has already produced, the learning task reduces to deciding which of its assignments to trust. Based on this insight, we propose a new solver-informed paradigm that reformulates solution prediction as an early-to-final consistency estimation problem. Given an MILP graph G, an early solution XESX^ES, and a reference solution X∗X^* obtained from a full-budget run, conventional solution prediction learns P(X∗∣G)P(X^* G) and thus requires the model to infer all variable assignments from static instance features alone. In contrast, we estimate P(xi∗=xiES∣G,XES),P(x_i^*=x_i^ES G,X^ES), namely the probability that each early assignment persists in the final solution. This target can substantially ease the learning task. Conditioned on the rich anchor XESX^ES, the model only needs to identify a relatively small fraction of assignments that have yet to stabilize. Theoretically, we prove that conditioning on the early solution can strictly increases the best achievable accuracy of predicting the full-budget solution, under a mild posterior-crossing condition, and that this information gain provably persists under finite-sample model selection. Moreover, since the predicted consistent assignments are drawn from a feasible early solution, fixing them preserves feasibility and concentrates the subsequent search on assignments that the solver has left unresolved. We evaluate our method on multiple MILP benchmarks with Gurobi (13) as the target solver and integrate it into existing prediction-based search frameworks. Experimental results show that our proposed refiner consistently reduces the primal gap in most evaluated settings. Specifically, it reduces the primal gap of Predict-and-Search (14) by 56.9% on average and closes the gap on combinatorial auction instances. Furthermore, without retraining, the model trained with Gurobi-generated data can be directly transferred to SCIP (1). These results demonstrate that the proposed early-to-final consistency prediction paradigm is clearly effective and showcases transferability across different solvers. 2 Preliminaries Mixed Integer Linear Programming A mixed-integer linear program (MILP) is an optimization problem with a linear objective and linear constraints, where a subset of decision variables is restricted to integer values. We formulate a MILP instance as minx∈n _x ^n ⊤ c x (1) s.t. .t. ≤, x≤ b, ≤, l≤ x≤ u, xi∈∀i∈ℐ, x_i \;∀ i , where =(x1,…,xn) x=(x_1,…,x_n) is the vector of decision variables, ∈n c ^n is the objective coefficient vector, ∈m×nA ^m× n is the constraint matrix, and ∈m b ^m is the right-hand-side vector. The bounds ,∈(∪±∞)n l, u∈(R∪\±∞\)^n defines the variable domains, and ℐ⊆1,…,nI \1,…,n\ is the index set of variables required to take integer values. An important special case is that of binary variables, for which xi∈0,1x_i∈\0,1\. General integer variables can be transformed into binary variables using standard preprocessing techniques. Graph Representations for MILP Learning-based MILP methods commonly encode an instance as a bipartite graph (30; 10). For the MILP formulated in Eq. (1), the associated graph is defined as G=(,,ℰ)G=(V,C,E), where =v1,…,vnV=\v_1,…,v_n\ and =q1,…,qmC=\q_1,…,q_m\ denote the sets of variable nodes and constraint nodes, corresponding to decision variables and constraints, respectively. An edge (vi,qj)∈ℰ(v_i,q_j) is introduced when the coefficient jiA_ji is non-zero. Each node is initialized with features describing its role in the MILP (14). A variable node viv_i contains the objective coefficient cic_i, the lower and upper bounds lil_i and uiu_i, and an indicator of whether xix_i is continuous or integer. A constraint node qjq_j contains the right-hand-side value bjb_j and an encoding of its constraint sense, such as ≤, ==, or ≥. In addition, each edge carries the matrix coefficient AjiA_ji as its edge feature. Collectively, these node and edge attributes provide a description of the local algebraic structure of the MILP instance, which serves as the input representation for graph neural networks (GNN). Solution Predictions for MILP Solution prediction methods learn a mapping from an MILP instance to variable assignments, which can be exploited to reduce the search space for acceleration. Most existing predictors take the static bipartite graph G as input and employ a graph convolutional network (GCN) or a related message-passing GNN to compute variable embeddings, from which the final predictions are decoded. Let hi(ℓ)h_i^( ) be the embedding of variable node viv_i at layer ℓ , and let gj(ℓ)g_j^( ) be the embedding of constraint node qjq_j. A common bipartite message-passing layer first aggregates messages from variables to constraints and then sends messages back to variables: gj(ℓ+1)=ϕC(ℓ)(gj(ℓ),∑i:(vi,qj)∈ℰψC(ℓ)(hi(ℓ),Aji)),hi(ℓ+1)=ϕV(ℓ)(hi(ℓ),∑j:(vi,qj)∈ℰψV(ℓ)(gj(ℓ+1),Aji)), array[]rclg_j^( +1)&=& _C^( ) (g_j^( ), _i:(v_i,q_j) _C^( )(h_i^( ),A_ji) ),\\[5.69054pt] h_i^( +1)&=& _V^( ) (h_i^( ), _j:(v_i,q_j) _V^( )(g_j^( +1),A_ji) ), array where ψC(ℓ) _C^( ) and ψV(ℓ) _V^( ) are message functions, and ϕC(ℓ) _C^( ) and ϕV(ℓ) _V^( ) are node-update functions. These functions are usually implemented as multilayer perceptrons with nonlinear activations. Each update depends on both neighboring node embeddings and the corresponding edge weight AjiA_ji. After L message-passing layers, the predictor applies a variable-level readout to each final variable embedding. For binary integer variables, a common formulation trains a predictor fθf_θ on the graph G to estimate a target solution X∗X^*: p^i=σ(rθ(hi(L)))=fθ(G)i≈P(xi∗=1∣G), p_i=σ\! (r_θ(h_i^(L)) )=f_θ(G)_i≈ P(x_i^*=1 G), where rθr_θ is a learnable readout function and σ is the sigmoid function. The output p^i p_i is the predicted probability that variable i takes value one in the reference solution. The predictions can then be used to construct a partial assignment, define a neighborhood around a candidate solution, or fix variables before invoking the solver on a reduced MILP. 3 Method Motivation We begin with an observation about the dynamics of modern MILP solvers: the primal and dual gaps typically decrease sharply at the beginning of the solve, after which progress becomes much slower and is spread over a long period of search. Figure 1 illustrates this behavior with the evolution of the primal gap on example instances; the same qualitative pattern holds across solvers and problem classes (App. A). This behavior suggests a two-stage view of MILP solving. In the fast descent stage, the solver rapidly discovers useful early solutions and tightens bounds through presolve, heuristics, cutting planes, and early branch-and-bound decisions. In the long exploration stage, the solver spends most of its time searching for further improvements, proving bounds, and resolving difficult variables. This two-stage view motivates a new prediction target for learning-based MILP solving. In contrast to the prevailing paradigm, which constructs a full solution directly from the static MILP graph, we propose an Early-to-final solution Consistency prediction paradigm, termed EnCore. Specifically, given an early solution XESX^ES collected after the fast-descent stage, we estimate the probability that the early assignment of each variable persists in the full-budget solution X∗X^*. This target distinguishes assignments that have likely stabilized from those that merit further exploration, thereby directing both learning and search effort toward the decisions that remain open after the fast descent. The proposed paradigm rests on the premise that the early solution is informative of the final one. We now examine this premise empirically. Figure 2 compares each early solution XESX^ES with the full-budget solution X∗X^* by counting the flipped integer variables. Across benchmark classes, the early solutions exhibit agreement with the final ones, and the discrepancies tend to concentrate on a limited subset of variables rather than spreading arbitrarily across the instance. These observations indicate that the early solution carries rich information about the final solution, making it a valuable reference worth exploiting. (a) Gurobi Results (b) SCIP Results Figure 1: Evolution of the primal gap over the solving process with Gurobi (left) and SCIP (right) on set covering instances. The time axis is scaled to highlight the early phase −200s0\!-\!200\,s. Results on other problem classes are provided in App. A. (a) Gurobi on CA (b) Gurobi on WA (c) SCIP on CA (d) SCIP on WA Figure 2: Distributions of flipped integer variables between early and full-budget solutions. ‘CA’ and ‘WA’ stand for combinatorial auction and workload apportionment, respectively. Consistency Prediction Given the MILP graph G and the collected early solution XESX^ES, we design a consistency predictor that estimates, for each integer variable, the probability that its early assignment agrees with the full-budget solution X∗X^*. The predictor must fuse two heterogeneous sources of information: the structural description of the instance, encoded in the bipartite variable–constraint graph, and the variable assignments in the early solution. We achieve this fusion at the input level, where each integer-variable node is augmented with its early assignment xiESx_i^ES as an additional feature. Through rounds of variable-to-constraint and constraint-to-variable message passing, the network can thus assess each assignment jointly with the constraints it appears in and the assignments of neighboring variables, which provides the evidence needed to judge whether the assignment will persist. The backbone is a bipartite graph neural network with half-convolutions, a standard architecture for MILP representation learning (14; 25). A variable-level readout then produces the consistency probability p^i p_i for each integer variable. Architectural details are provided in Appendix B. To train the predictor, we fundamentally reshape the learning target, rather than imitating the complete solutions X∗X^*. Since the early solution already encodes substantial information about the final one, the remaining task is not to predict every variable value from scratch, but to assess which early assignments are likely to persist in the final solution. We therefore define the binary consistency label yi=[xi∗=xiES]y_i=1[x_i^*=x_i^ES] for each integer variable i, and train the predictor fθf_θ so that p^i=fθ(G,XES)i≈P(xi∗=xiES∣G,XES). p_i=f_θ(G,X^ES)_i≈ P(x_i^*=x_i^ES G,X^ES). For each training instance G, we collect an early solution XESX^ES and pair it with the full-budget solution X∗X^*. The collection procedure is described later in this section. The predictor is then trained on the early-to-final consistency labels with the binary cross-entropy loss, ℒ(θ)=−∑i∈ℐ[yilogp^i+(1−yi)log(1−p^i)].L(θ)=- _i [y_i p_i+(1-y_i) (1- p_i) ]. This consistency target reshapes the learning task: rather than constructing the full solution from the static graph alone, the model refines an informative reference solution by assessing the stability of each assignment, which is a more focused and better-conditioned problem. Moreover, the conditioning solution XESX^ES provides a rich source of instance-specific information that purely graph-based predictors cannot access. Early Solution Collection. We collect early solutions at the transition from fast descent to long exploration. During the solving process, we monitor feasible-solution improvement events and estimate the local dual-gap decay rate over a sliding window, i.e., the gap reduction within the window divided by the elapsed time. The run is terminated once this rate first falls below a threshold, indicating that rapid bound improvement has mostly ended, and the last explored solution is taken as the early solution XESX^ES. In practice, we additionally impose a minimum probing time to avoid stopping before a meaningful dual bound, and a maximum time to restrict the runtime cost. Details are included in App. C. Inference-Time Augmentation. The early solution available for conditioning is not unique. Depending on when the collection run terminates, the solver may return slightly different solutions, and a variable predicted stable under one of them may still be predicted fluctuating under another. To mitigate this sensitivity, we employ the last few improving solutions for inference-time augmentation. Let X1,…,XK\X_1,…,X_K\ denote the last K improving solutions found during the collection run, with XK=XESX_K=X^ES. The trained predictor processes each XkX_k as the conditioning solution. Since a consistency score is always expressed relative to the value taken in its own conditioning solution, the resulting predictions must be aligned to the common reference XESX^ES. To this end, we flip the sign of each logit whose corresponding variable takes a different value in XkX_k than in XESX^ES, as a high consistency score for such a variable argues against the reference value. The aligned logits are then averaged, p¯i=σ(1K∑k=1Kτk,ip^k,i), p_i=σ\! ( 1K _k=1^K _k,i p_k,i ), where τk,i=+1 _k,i=+1 if xk,i=xiESx_k,i=x^ES_i and −1-1 otherwise. The ensembled probability p¯i p_i replaces p^i p_i as the consistency score of xiESx^ES_i used by the downstream search methods. Combine EnCore with Search Methods Our consistency predictor is independent of the downstream search strategy. In most learning-based MILP accelerators, the method must select a subset of variables whose predicted values are trusted, and the search space is then reduced accordingly. The central question is therefore which assignments can be trusted. Existing methods trust an assignment when the model is confident in its own prediction, so both the value and its evidence come from the model alone. In contrast, our early-to-final consistency design trusts values that the solver has already realized in a feasible early solution, and scores them by predicting whether they persist after the full solving process. Specifically, we rank variables by their consistency score p¯i p_i and select the top-ranked ones. Each selected variable i is constrained to its early value xiESx_i^ES, while the remaining variables are left to the downstream search mechanism. This consistency-based design offers two main advantages: (1) Feasibility. The fixed values are drawn from a feasible solution, so fixing them never destroys feasibility, which model-generated assignments cannot guarantee. (2) Alignment with the search process. The consistency signals originate from the solver’s own search trajectory, and thus naturally guide the model toward the variables that the solver has yet to resolve. 4 Theoretical Analysis Our method depends on the premise that conditioning on the early solution XESX^ES makes predicting the full-budget solution X∗X^* fundamentally easier than predicting from the instance graph alone. In this section, we formalize it by answering two questions: (1) Can the early solution improve the best achievable prediction accuracy, and under what condition is the gain strict (Theorem 1)? (2) Does this gain survive when the predictor must be selected from finite training instances (Theorem 2)? Complete proofs are in Appendix F. Let D be the distribution over triples (G,XES,X∗)(G,X^ES,X^*), and let J be a uniformly weighted variable index within an instance, so that Pr(x^J=xJ∗) ( x_J=x^*_J) is the expected per-instance variable accuracy, i.e., the population variable-level evaluation criterion used in our analysis. A message-passing predictor at variable J considers only the instance features in its receptive MILP graph ℛJR_J, while EnCore additionally attaches early assignments XℛJESX^ES_R_J to construct the augmented input J=(ℛJ,XℛJES)U_J=(R_J,X^ES_R_J). A solution predictor h maps ℛJR_J to a prediction of xJ∗x^*_J, matching the conventional paradigm. A consistency predictor a observes JU_J and decides whether to retain the early value, inducing ha(J)=xJES,a(J)=1,1−xJES,a(J)=0.h_a(U_J)= casesx^ES_J,&a(U_J)=1,\\ 1-x^ES_J,&a(U_J)=0. cases Given xJESx^ES_J, consistency decisions and final assignments determine each other (see Appendix F), so the two paradigms can be compared as predictors of xJ∗x^*_J. Information gain of the early solution. Define the best population accuracies attainable from each input, Asol∗ A^*_sol :=suphPr(h(ℛJ)=xJ∗), := _h (h(R_J)=x^*_J ), Acon∗ A^*_con :=supaPr(ha(J)=xJ∗). := _a (h_a(U_J)=x^*_J ). If D were known, these would be achieved by the Bayes-optimal rules on each input (6). Their comparison isolates the informational value of the early solution from any modeling concern. Theorem 1. For any fixed early-solution collection procedure, Acon∗≥Asol∗A^*_con≥ A^*_sol. Let ηJ:=Pr(xJ∗=1∣J) _J:= (x^*_J=1 _J). The inequality is strict if Pr(Pr(ηJ<12∣ℛJ)>0and Pr(ηJ>12∣ℛJ)>0)>0. \! ( aligned & ( _J< 12 _J)>0\\ &and ( _J> 12 _J)>0 aligned )>0. Proof sketch. Every solution predictor h defines ah(J)=h(ℛJ)=xJESa_h(U_J)=1\h(R_J)=x^ES_J\, for which hah(J)=h(ℛJ)h_a_h(U_J)=h(R_J). Hence the augmented input can reproduce every solution predictor. For strictness, conditional Jensen’s inequality (16) shows that refining the input strictly increases Bayes accuracy under the stated condition. ∎ The inequality itself is unsurprising since additional input can never hurt a Bayes-optimal predictor. The substantive content is about the strictness condition, which we call posterior crossing: for a non-negligible set of instance inputs, different early assignments compatible with the same instance structure favor different final values. In this regime, no predictor on instance features alone, however expressive, can resolve the ambiguity, while the early solution can. Figure 2 provides complementary empirical motivation by showing that early-to-final discrepancies are often concentrated on a small fraction of variables. A sparse-correction reading of the gain. Let a∗a^* be the Bayes rule on the augmented input, p=Pr(xJES≠xJ∗)p= (x^ES_J≠ x^*_J) represents the early-solution error rate, ρ=Pr(a∗(J)=0)ρ= (a^*(U_J)=0) denotes its flipping rate, and q is the precision on flipped variables, where q>1/2q>1/2 due to the Bayes optimality. Then we have 1−Acon∗ 1-A^*_con =p−ρ(2q−1), =p-ρ(2q-1), Acon∗−Asol∗ A^*_con-A^*_sol =1−Asol∗−p+ρ(2q−1). =1-A^*_sol-p+ρ(2q-1). The gain is positive exactly when p<1−Asol∗+ρ(2q−1)p<1-A^*_sol+ρ(2q-1). This identity captures the residual nature of EnCore: corrections with q>1/2q>1/2 remove more errors than they introduce, and when early-to-final discrepancies are sparse, learning can focus on a targeted subset of unstable assignments. The condition can also hold when 1−p<Asol∗1-p<A^*_sol (see Appendix F), showing that the early solution is valuable not only as a feasible candidate but also as an informative conditioning signal. Finite-sample guarantee. Theorem 1 optimizes over all rules and thus characterizes only the information available in principle. However, the predictor is selected from finite data in practice, and one may worry whether the population gain can survive estimation errors. Following the standard finite-class empirical-risk-minimization analysis based on Bernstein’s inequality and a union bound (4), we fix a finite class =a1,…,aNA=\a_1,…,a_N\ of consistency rules before observing m independent training instances, and let a a minimize the average proportion of variable errors; only instances need be independent, matching how MILP training data are collected. The class advantage decomposes as Δ=ΔB−α _A= _B- _A, where ΔB:=Acon∗−Asol∗ _B:=A^*_con-A^*_sol is the gain from Theorem 1 and α:=Acon∗−maxa∈Acc(ha) _A:=A^*_con- _a Acc(h_a) is the approximation gap, with Acc(h)=Pr(hJ=xJ∗)Acc(h)= (h_J=x^*_J). Motivated by the sparse discrepancies in Figure 2, we assume the expected per-instance flip rate satisfies maxa∈[sa]≤s¯ _a E[s_a]≤ s. Theorem 2. Let h^ES=ha h_ES=h_ a, and let h^sol h_sol be any possibly data-dependent solution predictor. For every δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, Acc(h^ES)−Acc(h^sol)≥ΔB−α−εm(δ) ( h_ES)-Acc( h_sol)≥ _B- _A- _m(δ) , εm(δ)=22s¯mln2Nδ+83mln2Nδ _m(δ)=2 2 sm 2Nδ+ 83m 2Nδ . Proof sketch. Use the rule that always keeps the early solution as a common reference. A candidate differs from it only on variables it flips, so its instance-level loss difference has variance at most s¯ s. Bernstein’s inequality with a union bound over the N rules (4) then controls all empirical loss differences simultaneously. Empirical risk minimization converts this into the penalty εm(δ) _m(δ), while Bayes optimality lower-bounds the risk of every instance-input solution predictor. ∎ Thus the learned consistency predictor provably outperforms any solution predictor, even one trained with unlimited data, whenever ΔB>α+εm(δ) _B> _A+ _m(δ). The dominant term of εm(δ) _m(δ) scales as s¯/m s/m rather than 1/m 1/m: sparse correction rules are cheaper to select reliably. A numerical illustration in Appendix F shows that under representative parameters, fewer than 200200 training instances suffice, which is similar to the typical sizes of training datasets. In summary, Theorem 1 establishes that the early solution provides a strict population-level information gain under a stated posterior-crossing condition, and the sparse-correction identity explains where the gain comes from: repairing a small, better-than-chance set of unstable assignments. Theorem 2 shows that this gain persists under finite-sample model selection, with a sample cost discounted by the very sparsity that motivates our design. Together, they justify shifting the learning target from full solution prediction to early-to-final consistency estimation. 5 Experiments Experimental Setup CA ↑ (BKS 98627.99) SC ↓ (BKS 123.37) WA ↓ (BKS 706.86) IP ↓ (BKS 11.72) Method Obj Gap Obj Gap Obj Gap Obj Gap Gurobi (3600s) 98448.84 179.15 123.37 0.00 706.86 0.00 11.72 0.00 Gurobi (1000s) 97311.69 1316.30 123.64 0.27 707.36 0.50 13.77 2.05 ND 94340.63 4287.36 123.62 0.25 707.10 0.24 14.15 2.43 PS 97906.20 721.79 123.60 0.23 707.09 0.23 12.08 0.36 Apollo 98083.79 544.20 123.56 0.19 707.06 0.20 11.97 0.25 EnCore-ND 97847.92 780.70 123.58 0.21 707.03 0.17 13.47 1.75 EnCore-PS 98627.99 0.00 123.50 0.13 706.98 0.12 11.95 0.23 EnCore-Apollo 98491.40 136.59 123.57 0.20 707.03 0.17 11.82 0.10 Best Gap Reduction 721.79 100.0% 0.10 43.5% 0.11 47.8% 0.15 60.0% Table 1: Main results with Gurobi. Obj is the final feasible objective and Gap is the absolute gap to the in-study BKS. Arrows indicate the preferred objective direction; bold marks the best learning-based result or a positive gap reduction. Figure 3: Average primal gap to the BKS versus time under a 1,000-second time limit. EnCore starts after the early solution collection. Each curve is shown only after all test instances have obtained a feasible solution. Benchmarks. Following 25, we evaluate EnCore on Combinatorial Auctions (CA) (21), Set Covering (SC) (2), Workload Apportionment (WA), and Item Placement (IP) (9). These benchmarks cover MILPs with diverse scales and structures. For zero-shot transfer, we additionally evaluate on the eleven-instance MIPLIB IIS benchmark considered by 25, following the IIS setting introduced by 33. The benchmark is a structurally related subset of MIPLIB centered on binary set-covering formulations, while exhibiting substantial variation in problem size, constraint structure, and sparsity. Dataset sources and instance statistics are reported in App. D. Baselines and variants. We compare against the native MILP solver and three prediction-guided search pipelines: Neural Diving (ND) (26), Predict-and-Search (PS) (14), and Apollo-MILP (Apollo) (25). For each learning-based pipeline, we replace its original solution predictor with our consistency predictor while keeping other configurations; the resulting methods are denoted as EnCore-ND, EnCore-PS, and EnCore-Apollo. This design isolates the contribution of the proposed consistency prediction mechanism from downstream solver policies. Evaluation protocol. All methods use a 1,000-second end-to-end budget that includes early-solution collection, inference, and downstream solving. For a fair comparison, EnCore does not use the collected early solutions to warm-start the final search. For EnCore-Apollo, early solutions are collected once and reused across correction rounds. We report the final feasible objective, its absolute gap to the best-known solution (BKS), and the gap reduction relative to the corresponding solution predictor baseline. The BKS is the best mean final objective among all evaluated methods, including the 3,600-second Gurobi reference. Main Results Table 1 reports the final objectives under Gurobi. Substituting EnCore for the original solution predictor reduces the final gap in 11 of the 12 settings (4 benchmarks × 3 search mechanisms), by 38.7%, 56.9%, and 36.2% on average for ND, PS, and Apollo, respectively. The sole exception is Apollo on SC, where the gap grows marginally from 0.19 to 0.20. On CA, EnCore-PS finds the best solution among all compared methods, improving on the 3,600-second Gurobi incumbent by 179.15 within a 1,000-second budget, and EnCore-Apollo also exceeds this reference (+42.56). On SC, WA, and IP, where the baselines have already been close to the BKS, EnCore still removes 43.5%, 47.8%, and 60.0% of the best baseline gap. Remarkably, EnCore remains effective even under weak easy-to-final consistency. On CA, where 19% of the variables flip between the early and final solutions, the consistency predictor still captures the learnable patterns underlying these flips, allowing EnCore to achieve a 100% average gap reduction. Figure 3 traces the primal gap over time. Although the best EnCore variant on each benchmark begins prediction-guided search only after the 60-second collection stage, it catches up with its corresponding baseline at 71, 241, 164, and 93 seconds of end-to-end runtime on CA, SC, WA, and IP, respectively, and remains ahead thereafter. EnCore-PS overtakes all competitors early on CA and attains the lowest gap on SC and WA, with the late-stage separation shown in the insets. On IP, EnCore-Apollo exhibits the strongest late-stage anytime performance and widens its lead over time. Zero-shot cross-solver transfer to SCIP. We directly apply the Gurobi-trained checkpoint to SCIP-generated trajectories without retraining or model selection. As shown in Table 2, EnCore-ND consistently improves all four benchmarks, reducing the absolute gap by 53.6%, 22.0%, 33.1%, and 50.7% on CA, SC, WA, and IP, respectively. Moreover, EnCore-PS also improves performance on CA, WA, and IP. These results show that the learned consistency representation remains informative under a solver shift. Method CA ↑ SC ↓ WA ↓ IP ↓ SCIP(1000s) 94701.91 127.99 709.06 23.49 ND 94342.12 125.14 707.33 18.19 PS 97097.46 125.03 708.49 17.02 Apollo 97335.92 124.97 708.43 16.21 EnCore-ND 96641.43 124.75 707.24 14.91 EnCore-PS 97707.64 125.04 708.22 16.13 EnCore-Apollo 97293.51 125.38 707.91 17.39 Best Gap Reduction 53.6% 22.0% 33.1% 50.7% Table 2: Zero-shot transfer from Gurobi to SCIP under a 1,000-second total budget. Bold marks the best result. The BKS is presented in Table 1. Zero-shot cross-family transfer to MIPLIB IIS. We train our EnCore models on the mixed SC, CA, WA, and IP instances, and evaluate them on the eleven unseen MIPLIB instances used by 25 under the same 1,000-second budget. The clearest advantage of EnCore is about feasibility. With ND, the original predictor finds feasible solutions on only 3 of 11 instances, while EnCore-ND succeeds on all 11. With PS and Apollo, where the baselines already achieve full feasibility, EnCore still yields consistent improvements in mean objectives. These results demonstrate that our proposed EnCore exhibits greater reliability and robustness than existing methods when faced with substantial distribution shifts. Details are provided in Appendix D. Ablation Study Table 3 presents a cumulative ablation of the Predict-and-Search pipeline. Adding early solutions as input features alone improves most benchmarks. However, the consistency target contributes substantially larger gains than the extra features themselves, indicating that reformulating the prediction objective is empirically effective. Finally, introducing early-solution ensembling further improves CA, SC, and WA, delivering a smaller but complementary robustness benefit. Variant CA ↑ SC ↓ WA ↓ IP ↓ Predict-and-Search 97906.20 123.60 707.09 12.08 + early solution as feature 98318.22 123.55 707.04 12.17 + consistency prediction target 98616.65 123.53 706.99 11.90 + early-solution ensemble 98627.99 123.50 706.98 11.95 Table 3: Ablation study of key components under the Predict-and-Search pipeline. Average objective values are reported. Trade-off Analysis of Early-Solution Collection Figure 4 varies the collection budget TmaxT_ under the fixed 1,000-second total budget. Across all benchmarks, performance peaks at a small TmaxT_ : a short collection stage suffices to obtain informative early solutions, whereas larger TmaxT_ leads to diminishing improvements in early-solution quality while consuming more time budget for downstream search. Figure 4: Average final objective of EnCore-PS under different maximum early-solution collection times. 6 Conclusion In this paper, we presented EnCore, a solver-informed paradigm that accelerates MILP solving via early-to-final solution consistency prediction. Instead of constructing complete solutions from the static MILP formulation alone, EnCore conditions on feasible solutions collected during the early search stage and identifies the assignments likely to persist under a full solving budget. The resulting consistency scores integrate seamlessly with diverse prediction-guided search frameworks, and ensembling multiple early solutions further enhances robustness. Theoretically, we showed that conditioning on early solutions yields a strict gain in achievable prediction accuracy, and that this gain survives finite-sample model selection at a cost discounted by correction sparsity. Empirically, EnCore consistently improves prediction-guided solving across four benchmarks and generalizes zero-shot to unseen solvers and problem families. Future work will explore jointly learning consistency prediction and downstream search policies. References Achterberg (2009) T. Achterberg SCIP: solving constraint integer programs. Mathematical Programming Computation 1 (1), p. 1–41. External Links: Document Cited by: §1, §1. Balas and Ho (1980) E. Balas and A. Ho Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, Vol. 12, p. 37–60. Cited by: Appendix D, §5. Bengio et al. (2021) Y. Bengio, A. Lodi, and A. Prouvost Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research 290 (2), p. 405–421. External Links: Document Cited by: §1. Boucheron et al. (2013) S. Boucheron, G. Lugosi, and P. Massart Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press, Oxford. Cited by: Appendix F, Appendix F, §4, §4. Crainic (2000) T. G. Crainic Service network design in freight transportation. European Journal of Operational Research 122 (2), p. 272–288. Cited by: §1. Devroye et al. (1996) L. Devroye, L. Györfi, and G. Lugosi A probabilistic theory of pattern recognition. Stochastic Modelling and Applied Probability, Vol. 31, Springer, New York. External Links: Document Cited by: §4. Ferber et al. (2020) A. Ferber, B. Wilder, B. Dilkina, and M. Tambe MIPaaL: mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, New York, NY, USA, p. 1504–1511. External Links: Document Cited by: §1. Floudas and Lin (2005) C. A. Floudas and X. Lin Mixed integer linear programming in process scheduling: modeling, algorithms, and applications. Annals of Operations Research 139 (1), p. 131–162. Cited by: §1. Gasse et al. (2022) M. Gasse, S. Bowly, Q. Cappart, J. Charfreitag, L. Charlin, D. Chételat, A. Chmiela, J. Dumouchelle, A. M. Gleixner, A. M. Kazachkov, E. B. Khalil, P. Lichocki, A. Lodi, M. Lubin, C. J. Maddison, C. Morris, D. J. Papageorgiou, A. Parjadis, S. Pokutta, A. Prouvost, L. Scavuzzo, G. Zarpellon, et al. The machine learning for combinatorial optimization competition (ML4CO): results and insights. In Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, Proceedings of Machine Learning Research, Vol. 176, p. 220–231. Cited by: Appendix D, §5. Gasse et al. (2019) M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, Vol. 32, Vancouver, BC, Canada. Cited by: §1, §2. Gleixner et al. (2021) A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bastubbe, T. Berthold, P. M. Christophel, K. Jarck, T. Koch, J. Linderoth, M. Lübbecke, H. D. Mittelmann, D. Ozyurt, T. K. Ralphs, D. Salvagnin, and Y. Shinano MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation 13 (3), p. 443–490. External Links: Document, Link Cited by: Appendix D. Gupta et al. (2020) P. Gupta, M. Gasse, E. B. Khalil, P. Mudigonda, A. Lodi, and Y. Bengio Hybrid models for learning to branch. In Advances in Neural Information Processing Systems 33, Vol. 33, Virtual, p. 18087–18097. Cited by: §1. Gurobi Optimization, LLC (2026) Gurobi Optimization, LLC Gurobi Optimizer Reference Manual. External Links: Link Cited by: §1. Han et al. (2023) Q. Han, L. Yang, Q. Chen, X. Zhou, D. Zhang, A. Wang, R. Sun, and X. Luo A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming. In The 11th International Conference on Learning Representations, Kigali, Rwanda. Cited by: Appendix B, Appendix B, Appendix D, Appendix D, §1, §1, §2, §3, §5. Hutter et al. (2009) F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle ParamILS: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, p. 267–306. External Links: Document Cited by: §1. Kallenberg (2021) O. Kallenberg Foundations of modern probability. 3 edition, Springer, Cham. Cited by: §4. Karp (1972) R. M. Karp Reducibility among combinatorial problems. In Proceedings of the Symposium on the Complexity of Computer Computations, Yorktown Heights, New York, USA, p. 85–103. Cited by: §1. Khalil et al. (2016) E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina Learning to branch in mixed integer programming. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Vol. 30, Phoenix, AZ, USA, p. 724–731. External Links: Document Cited by: §1. Land and Doig (1960) A. H. Land and A. G. Doig An automatic method of solving discrete programming problems. Econometrica 28 (3), p. 497–520. Cited by: §1. Laporte (1992) G. Laporte The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research 59 (3), p. 345–358. External Links: ISSN 0377-2217 Cited by: §1. Leyton-Brown et al. (2000) K. Leyton-Brown, M. Pearson, and Y. Shoham Towards a universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM Conference on Electronic Commerce, Minneapolis, MN, USA, p. 66–76. Cited by: Appendix D, §5. Li et al. (2026) H. Li, H. Yuan, H. Zhang, J. Lin, D. Ge, M. Wang, and Y. Ye FMIP: joint continuous-integer flow for mixed-integer linear programming. In The 14th International Conference on Learning Representations, Rio de Janeiro, Brazil. Cited by: §1. Li et al. (2023) S. Li, W. Ouyang, M. B. Paulus, and C. Wu Learning to configure separators in branch-and-cut. In Advances in Neural Information Processing Systems, Vol. 36, New Orleans, LA, USA, p. 60021–60034. Cited by: §1. Ling et al. (2024) H. Ling, Z. Wang, and J. Wang Learning to stop cut generation for efficient mixed-integer linear programming. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, Vancouver, BC, Canada, p. 20759–20767. External Links: Document Cited by: §1. Liu et al. (2025) H. Liu, J. Wang, Z. Geng, X. Li, Y. Zong, F. Zhu, J. Hao, and F. Wu Apollo-MILP: an alternating prediction-correction neural solving framework for mixed-integer linear programming. In The 13th International Conference on Learning Representations, Singapore. Cited by: Appendix D, Appendix D, Appendix D, §1, §3, §5, §5, §5. Nair et al. (2020) V. Nair, S. Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraatmadja, P. Wang, R. Addanki, T. Hapuarachchi, T. Keck, J. Keeling, P. Kohli, I. Ktena, Y. Li, O. Vinyals, and Y. Zwols Solving mixed integer programs using neural networks. External Links: 2012.13349 Cited by: §1, §1, §5. Nam and Logendran (1992) S. Nam and R. Logendran Aggregate production planning — a survey of models and methodologies. European Journal of Operational Research 61 (3), p. 255–272. Cited by: §1. Padberg and Rinaldi (1991) M. Padberg and G. Rinaldi A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review 33 (1), p. 60–100. Cited by: §1. Pu et al. (2026) T. Pu, J. Li, Y. Gao, S. Liu, Z. Geng, H. Liu, C. Chen, and C. Fan CoCo-MILP: inter-variable contrastive and intra-constraint competitive MILP solution prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, Singapore, p. 24882–24890. Cited by: §1. Salvagnin (2016) D. Salvagnin Detecting semantic groups in mip models. In Integration of AI and OR Techniques in Constraint Programming, p. 329–341. Cited by: §2. Strang et al. (2026) P. Strang, Z. Alès, C. Bissuel, O. Juan, S. Kedad-Sidhoum, and E. Rachelson Planning in branch-and-bound: model-based reinforcement learning for exact combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 25627–25635. Cited by: §1. Tang et al. (2020) Y. Tang, S. Agrawal, and Y. Faenza Reinforcement learning for integer programming: learning to cut. In Proceedings of the 37th International Conference on Machine Learning, Vol. 119, Vienna, Austria, p. 9367–9376. Cited by: §1. Wang et al. (2024) H. P. Wang, J. Liu, X. Chen, X. Wang, P. Li, and W. Yin DIG-MILP: a deep instance generator for mixed-integer linear programming with feasibility guarantee. Transactions on Machine Learning Research. External Links: ISSN 2835-8856, Link Cited by: Appendix D, §5. Wang et al. (2026) R. Wang, X. Li, and M. Wang MILPnet: a multi-scale architecture with geometric feature sequence representations for advancing MILP problems. In The 14th International Conference on Learning Representations, Cited by: §1. Appendix A Solver Behavior Figures 5 and 7 show the primal gap versus solving time for Gurobi and SCIP on the four benchmarks. Figures 6 and 8 show the distributions of integer variables flipped between the early and full-budget solutions. Figure 9 reports the same analyses on MIPLIB. (a) CA (b) SC (c) WA (d) IP Figure 5: Primal gap versus solving time for Gurobi. (a) CA (b) SC (c) WA (d) IP Figure 6: Early-to-final flip distributions for Gurobi; red and green dashed lines denote the mean and median. (a) CA (b) SC (c) WA (d) IP Figure 7: Primal gap versus solving time for SCIP. (a) CA (b) SC (c) WA (d) IP Figure 8: Early-to-final flip distributions for SCIP; red and green dashed lines denote the mean and median. (a) Primal gap over time. (b) Aggregate flip distribution. (c) Per-instance flip percentages. Figure 9: Solver behavior on the MIPLIB IIS dataset with Gurobi. Appendix B Model Structure Graph Representation. We follow the MILP representation of 14, adding only one dimension to each variable node to encode its early-solution value. Detailed feature definitions are provided in Table 4. Index Feature Description Variable-node features 0 Objective Normalized objective coefficient. 1 Variable coefficient Average variable coefficient across all constraints. 2 Variable degree Degree of the variable node in the bipartite graph. 3 Maximum coefficient Maximum variable coefficient across all constraints. 4 Minimum coefficient Minimum variable coefficient across all constraints. 5 Variable type Indicator of whether the variable is integer. 6–17 Position embedding Binary encoding of the variable’s order among all variables. 18 Early-solution value Value of the variable in the early solution collected as described in Appendix C. Constraint-node features 0 Constraint coefficient Average of the nonzero coefficients in the constraint. 1 Constraint degree Degree of the constraint node in the bipartite graph. 2 Bias Normalized right-hand side of the constraint. 3 Sense Sense of the constraint. Edge features 0 Coefficient Coefficient connecting the constraint and variable nodes. Table 4: Graph features for input. Network architecture. We strictly follow the network architecture proposed by 14, modifying only the variable encoder to accommodate the additional early-solution feature. Each variable node is represented by 19 input features, consisting of the original 18 features and the early-solution value introduced by our method. Constraint nodes and edges have 4 and 1 input features, respectively. All node representations are embedded into a 64-dimensional latent space. For an input feature vector of dimension d, the node encoder is defined as Encd(x)=ReLU(W2ReLU(W1LN(x))),Enc_d(x)=ReLU\! (W_2\,ReLU\! (W_1LN(x) ) ), where W1:ℝd→ℝ64W_1 ^d ^64 and W2:ℝ64→ℝ64W_2 ^64 ^64. Accordingly, the variable and constraint encoders use Enc19Enc_19 and Enc4Enc_4, respectively, while the scalar edge feature is normalized by LayerNorm(1)LayerNorm(1). The model performs two rounds of bidirectional message passing between variable and constraint nodes: V→C→V→C→V.V→ C→ V→ C→ V. For a directed edge j→ij→ i, the message is computed as mij=WMReLU[LN(WLhi+WEeij+WRhj)],m_ij=W_M\,ReLU\! [LN\! (W_Lh_i+W_Ee_ij+W_Rh_j ) ], where hih_i and hjh_j denote the target and source node representations, and eije_ij is the encoded edge feature. Incoming messages are summed and normalized: m¯i=LN(∑j∈(i)mij). m_i=LN\! ( _j (i)m_ij ). The target node representation is then updated by hi′=WU,2ReLU(WU,1[hi∥m¯i]),h_i =W_U,2\,ReLU\! (W_U,1[h_i \| m_i] ), where ∥ \| denotes concatenation, WU,1:ℝ128→ℝ64W_U,1 ^128 ^64, and WU,2:ℝ64→ℝ64W_U,2 ^64 ^64. Finally, each variable representation is mapped to a scalar logit: ℓv=wout⊤ReLU(Wouthv), _v=w_out ReLU\! (W_outh_v ), where the final output layer has no bias. The predicted probability σ(ℓv)σ( _v) indicates whether the early-solution value of variable v is consistent with its value in the full-budget reference solution. Appendix C Early Solution Collection Details We first quantify the progress of the dual bound using the average dual-gap decay rate, and then describe the early-solution collection procedure in Algorithm 1. Specifically, for the k-th monitoring interval, the decay rate is defined as rk=|Dka−Dkb|tkb−tka,r_k= |D_k_a-D_k_b |t_k_b-t_k_a, (2) where kak_a and kbk_b denote the observations at the beginning and end of the interval, respectively; DkaD_k_a and DkbD_k_b are the corresponding dual gaps; and tkat_k_a and tkbt_k_b are their wall-clock times. Thus, rkr_k measures the average absolute reduction in the dual gap per unit time during the k-th monitoring interval. Algorithm 1 Early Solution Collection 0: MILP instance G, minimum probing time TminT_ , maximum probing time TmaxT_ , window size w, decay threshold ϵε 0: Early solution XESX^ES and probing time tprobet_probe 1: Initialize an empty callback record list ℛR. 2: Start a probing solver run on G. 3: while the solver is running do 4: if a MIPSOL callback occurs at time tkt_k then 5: Record the explored solution XkX_k and relative dual gap DkD_k. 6: Append (tk,Xk,Dk)(t_k,X_k,D_k) to ℛR. 7: if |ℛ|≥w|R|≥ w then 8: Let kak_a and kbk_b be the first and last records in the latest w-record window. 9: Compute rkr_k by Eq. (2). 10: if tk≥Tmint_k≥ T_ and rk<ϵr_k<ε then 11: Stop the probing run. 12: end if 13: end if 14: end if 15: if the elapsed probing time reaches TmaxT_ then 16: Stop the probing run. 17: end if 18: end while 19: Set XESX^ES to the last explored solution during probing. 20: Set tprobet_probe to the elapsed probing time. 21: return XESX^ES and tprobet_probe. Appendix D Experimental Details Benchmark Details We evaluate on the four benchmark families used by Apollo-MILP (25). Combinatorial Auctions (CA) instances follow the CATS generator (21), Set Covering (SC) follows the classical construction of 2, and Workload Apportionment (WA) and Item Placement (IP) come from ML4CO (9). CA is a maximization problem, whereas SC, WA, and IP are minimization problems. Table 5 reports average instance sizes. We use 240 training, 60 validation, and 100 testing instances, following the settings in 14 and 25. We train all models with 500 epochs and a learning rate of 0.001. CA SC IP WA Constraint Number 2590.33 3000 195 64306 Variable Number 1500 5000 1083 61000 Binary Variables Number 1500 5000 1050 1000 Continuous Variables Number 0 0 33 60000 Integer Variables Number 0 0 0 0 Table 5: Statistical information of the benchmark instances. Protocols for Combining EnCore with Downstream Search Methods This section details how EnCore is integrated with the three downstream methods evaluated in Section 5. Following the evaluation protocol proposed by 14 and 25, every run is given a total wall-clock budget of 10001000s, and all overhead introduced by EnCore—including the time spent collecting the early solution—is counted against this budget. Let tESt_ES denote the time used to obtain the early solution xESx^ES on a given instance. Predict-and-Search and Neural Diving. Both methods consume the predictor output once, before the final solve, so the integration requires no change to their search procedures. Given an instance, we run the solver on the original MILP for tESt_ES seconds and record the early solution xESx^ES together with the associated solving-process features. The consistency predictor then assigns each binary variable a score p¯i p_i, the estimated probability that xiESx_i^ES agrees with the reference solution. Since both methods specify their fixing budgets separately for the two binary values, selection is value-conditioned: we rank the variables with xiES=0x_i^ES=0 by p¯i p_i and retain the top k0k_0, and independently retain the top k1k_1 among those with xiES=1x_i^ES=1. On CA under Predict-and-Search, for example, the setting (k0,k1,Δ)=(600,0,20)(k_0,k_1, )=(600,0,20) selects the 600600 zero-valued variables with the highest consistency scores and no one-valued ones, and the resulting partial assignment xi=0\x_i=0\ defines the center of a search neighborhood of radius Δ=20 =20. Neural Diving consumes the selection in the same way except that the assignments are imposed as hard fixings and the reduced MILP is solved. In both cases the solver is restarted from scratch with a budget of 1000−tES1000-t_ES seconds, so that the end-to-end wall-clock time matches that of the baselines. Apollo-MILP. Apollo-MILP performs four prediction–correction rounds with per-round budgets of 100100s, 100100s, 200200s, and 600600s. Extending the protocol above directly would require collecting a fresh early solution at the start of every round, which is too costly: the collection phase alone would consume a non-negligible fraction of the 100100s rounds. We instead adopt the following assumption. Since Apollo-MILP realizes its fixing step by imposing bound constraints on the selected variables rather than by restructuring the problem, we assume that the early search behavior of the bounded problem stays close to that of the original instance, so that the early values realized on the original instance remain informative anchors throughout the iterative process. Under this assumption, we collect the early solution only once, on the original instance and in exactly the same way as above, and reuse xESx^ES and its consistency scores in the prediction step of every round. Each round applies the same value-conditioned selection, restricted to the variables not yet fixed in earlier rounds. To keep the total budget unchanged, the collection cost tESt_ES is charged to the final round, whose budget becomes 600−tES600-t_ES seconds, while the first three rounds are left untouched; the overall wall-clock time thus remains 10001000s. Evaluation Protocol Hardware. All experiments are conducted on a Linux server (Ubuntu 20.04.6 LTS) equipped with an Intel Xeon Platinum 8124M CPU (72 logical cores, 3.50GHz), 256GB of RAM, and an NVIDIA GeForce RTX 3090 GPU (24GB). Neural network training and inference run on the GPU, while all solver calls run on the CPU. The solver configuration (e.g., thread count) is kept identical across all methods on each benchmark. Metrics. We report the final feasible objective and its absolute primal gap gapabs=|z−zBKS|,gap_abs=|z-z_BKS|, (3) where z is the mean final objective of a method and zBKSz_BKS is the best-known solution (BKS) on the corresponding benchmark. The BKS is defined as the best mean final objective observed among all evaluated methods, including a 3,600-second Gurobi run: Gurobi provides this reference on SC, WA, and IP, while EnCore-PS provides it on CA. The BKS is thus an in-study best-observed reference rather than an independently certified optimum. To quantify the benefit of our method over a downstream baseline, we additionally report the relative gap reduction Improvement=gapbase−gapoursgapbase×100%.Improvement= gap_base-gap_oursgap_base× 100\%. (4) Zero-Shot MIPLIB IIS Transfer Protocol The IIS setting traces to 33, which formed a two-instance dataset from MIPLIB: iis-glass-cov was used for training and iis-hc-cov for testing. Apollo-MILP later expanded this setting into an eleven-instance subset of MIPLIB 2017 (11; 25). Specifically, it selected instances according to similarities measured with 100 human-designed structural features, then discarded instances whose presolving exceeded 300 seconds or whose inference exceeded GPU memory. Apollo-MILP used eight of the resulting instances for training and three—ramos3, scpj4scip, and scpl4—for testing. In contrast, we use all eleven instances exclusively as a zero-shot test set. The instances range from 214 to 200,000 variables and from 32,805 to 2,000,000 nonzero coefficients. In this experiment, both predictors are trained on the union of the CA, SC, WA, and IP training sets. They are validated on the union of the corresponding validation sets, and checkpoint selection uses only this combined validation set. The selected checkpoints are frozen before evaluation on IIS. No MIPLIB instance is used for training, validation, fine-tuning, or checkpoint selection. Table 6 gives the overall performance while Table 7 gives the instance-level results. The PS improvement is mainly attributable to ramos3 and ex1010-pi, partially offset by scpk4. Apollo+Ours improves ex1010-pi, degrades on ramos3, and ties on the remaining instances. Predictor Downstream Mean Obj ↓ Feas. Origin Neural Diving 243.00† 3/11 EnCore Neural Diving 173.45 11/11 Origin Predict-and-Search 172.00 11/11 EnCore Predict-and-Search 171.73 11/11 Origin Apollo-MILP 172.91 11/11 EnCore Apollo-MILP 172.82 11/11 Table 6: Zero-shot cross-family transfer to the MIPLIB IIS subset. Mean Obj is the mean of the per-instance final objectives. Feas. reports the number of instances with a finite feasible objective. † means computed only over its three feasible instances. ND PS Apollo-MILP Instance GCN Ours GCN Ours GCN Ours ex1010-pi – 242.00 237.00 236.00 241.00 238.00 fast0507 – 174.00 174.00 174.00 174.00 174.00 glass-sc – 23.00 23.00 23.00 23.00 23.00 iis-glass-cov – 21.00 21.00 21.00 21.00 21.00 iis-hc-cov – 17.00 17.00 17.00 17.00 17.00 ramos3 – 235.00 229.00 226.00 231.00 233.00 scpj4scip 132.00 132.00 132.00 132.00 132.00 132.00 scpk4 328.00 330.00 326.00 327.00 330.00 330.00 scpl4 269.00 269.00 269.00 269.00 269.00 269.00 seymour – 423.00 423.00 423.00 423.00 423.00 v150d30-2hopcds – 42.00 41.00 41.00 41.00 41.00 Table 7: Final objectives on the eleven MIPLIB IIS instances. All instances are minimization problems. Bold marks the lowest objective in each row; a dash indicates that no finite feasible solution was found. Appendix E Hyperparameter Settings Early Solution Collection For early-solution collection, we set the sliding-window size to w=5w=5, the dual-gap decay threshold to ϵ=0.01%ε=0.01\%/s, the minimum probing time to Tmin=20T_ =20 seconds, and the maximum probing time to Tmax=60T_ =60 seconds. We use an ensemble size of K=3K=3 for SC, CA and WA and use K=2K=2 for IP. Neighborhood Search Parameters We report the hyper-parameters we used in our study. EnCore and baselines use the same hyper-parameters. Table 8 shows the hyperparameters of Predict-and-Search and EnCore-PS, and the Neural Diving and EnCore-ND uses the same (k0,k1)(k_0,k_1). Table 9 shows the Apollo hyperparameters for baseline Apollo-MILP and EnCore-apollo. Benchmark CA SC IP WA PS+Gurobi (600,0,20)(600,0,20) (2000,0,100)(2000,0,100) (400,5,10)(400,5,10) (0,500,10)(0,500,10) PS+SCIP (400,0,20)(400,0,20) (2000,0,100)(2000,0,100) (400,5,1)(400,5,1) (0,600,5)(0,600,5) Table 8: The partial solution size parameters (k0,k1)(k_0,k_1) and neighborhood parameter Δ . CA SC IP WA Iteration 1 (400,0,60)(400,0,60) (1000,0,200)(1000,0,200) (100,20,50)(100,20,50) (20,200,100)(20,200,100) Iteration 2 (200,0,30)(200,0,30) (500,0,100)(500,0,100) (40,15,20)(40,15,20) (10,100,50)(10,100,50) Iteration 3 (100,0,15)(100,0,15) (250,0,50)(250,0,50) (20,15,10)(20,15,10) (10,5,5)(10,5,5) Iteration 4 (50,0,10)(50,0,10) (10,0,5)(10,0,5) (5,50,30)(5,50,30) (1,10,5)(1,10,5) Table 9: Hyperparameters (k0(i),k1(i),Δ(i))(k_0^(i),k_1^(i), ^(i)) for Apollo-MILP. Appendix F Details and Proofs for the Theoretical Analysis Population Setting and Notation Let D be the probability distribution over all triples consisting of an MILP graph, the early solution produced by the fixed collection procedure, and the full-budget solution. Draw Z=(G,XES,X∗)∼.Z=(G,X^ES,X^*) . Let ℬ(G)B(G) be the set of binary-variable indices in G. Assume |ℬ(G)|≥1|B(G)|≥ 1 almost surely. To represent the per-instance variable average compactly, conditional on Z, choose J from ℬ(G)B(G), giving every index probability 1/|ℬ(G)|1/|B(G)|. We use J for this random index in population quantities and r for a deterministic summation index. Fix the message-passing depth L. For r∈ℬ(G)r (G), let ℛrR_r denote the part of the static graph and its features within L message-passing steps of variable r, and let XℛrESX^ES_R_r denote the early assignments attached to the variable nodes in this local input. For any assignment predictor h, define ℓh(Z) _h(Z) :=1|ℬ(G)|∑r∈ℬ(G)hr≠xr∗, := 1|B(G)| _r (G)1\h_r≠ x_r^*\, R(h) R(h) :=E[ℓh(Z)]=Pr(hJ≠xJ∗), :=E[ _h(Z)]= (h_J≠ x_J^*), Acc(h) (h) :=1−R(h). :=1-R(h). Here a direct prediction hrh_r is a function of ℛrR_r, whereas an induced consistency prediction may also use XℛrESX^ES_R_r. The corresponding posteriors are ηG _G :=Pr(xJ∗=1∣ℛJ), := (x_J^*=1 _J), ηES _ES :=Pr(xJ∗=1∣ℛJ,XℛJES). := (x_J^*=1 _J,X^ES_R_J). Their Bayes errors are bG b_G :=E[minηG,1−ηG], :=E[ \ _G,1- _G\], bES b_ES :=E[minηES,1−ηES]. :=E[ \ _ES,1- _ES\]. Thus Asol∗=1−bGA_sol^*=1-b_G is the best population accuracy attainable from the static local input, and 1−bES1-b_ES is the best assignment accuracy attainable when the early assignments are also observed. Consistency–Assignment Equivalence Lemma 1 (label–assignment equivalence). For r∈ℬ(G)r (G), let yr=xrES=xr∗y_r=1\x_r^ES=x_r^*\. Given a binary consistency prediction y^r y_r, retain xrESx_r^ES when y^r=1 y_r=1 and use its binary complement otherwise. The induced assignment x^r x_r satisfies x^r≠xr∗=y^r≠yr.1\ x_r≠ x_r^*\=1\ y_r≠ y_r\. Equivalently, for a consistency rule a, define ha(G,XES)r:=xrES⊕(1−a(G,XES)r).h_a(G,X^ES)_r:=x_r^ES (1-a(G,X^ES)_r). Then ℓha(Z)=1|ℬ(G)|∑r∈ℬ(G)a(G,XES)r≠yr. _h_a(Z)= 1|B(G)| _r (G)1\a(G,X^ES)_r≠ y_r\. (5) Proof. For binary values, xr∗=xrES⊕(1−yr)x_r^*=x_r^ES (1-y_r). XOR by the same value preserves equality, so ha(G,XES)r≠xr∗h_a(G,X^ES)_r≠ x_r^* exactly when a(G,XES)r≠yra(G,X^ES)_r≠ y_r. Averaging over ℬ(G)B(G) proves Eq. (5). □ The induced assignment hah_a is used only to compare variable-level prediction errors. In the downstream search method, assignments predicted inconsistent are left free rather than forcibly complemented, so these identities characterize the variable-level prediction task, while the downstream objective and runtime effects are evaluated empirically. Conversely, every direct solution predictor h defines a consistency rule ah(G,XES)r:=h(ℛr)=xrES.a_h(G,X^ES)_r:=1\h(R_r)=x_r^ES\. The induced predictor satisfies hah(G,XES)r=h(ℛr)h_a_h(G,X^ES)_r=h(R_r). Thus consistency prediction with the augmented input can reproduce every direct predictor based on the static local input. Let YJ=xJES=xJ∗Y_J=1\x_J^ES=x_J^*\ and ξJ:=Pr(YJ=1∣ℛJ,XℛJES). _J:= (Y_J=1 _J,X^ES_R_J). For a fixed variable r, ξr _r denotes the corresponding conditional posterior evaluated at r. Since xJESx_J^ES is observed in the augmented local input, ξJ=xJESηES+(1−xJES)(1−ηES). _J=x_J^ES _ES+(1-x_J^ES)(1- _ES). Consequently, minξJ,1−ξJ=minηES,1−ηES, \ _J,1- _J\= \ _ES,1- _ES\, so the Bayes consistency error equals bESb_ES. Under variable-level 00–11 prediction loss, the optimal rule predicts 11 when ξJ≥1/2 _J≥ 1/2 and 00 otherwise. By Lemma 1, its induced assignment accuracy is Acon∗=1−bESA_con^*=1-b_ES. Because the label transformation is bijective after xJESx_J^ES is observed, this is also the Bayes accuracy of a direct assignment predictor using the same augmented input. Theorem 1 therefore compares the information in the augmented input with that in the static input, rather than attributing a Bayes advantage to the consistency relabeling itself. Proof of Theorem 1 The population accuracy difference can be written as Acon∗−Asol∗=bG−bES≥0.A_con^*-A_sol^*=b_G-b_ES≥ 0. (6) The inequality is strict if there exists an event ℰ∈σ(ℛJ)E∈σ(R_J) with Pr(ℰ)>0 (E)>0 such that, almost surely on ℰE, Pr(ηES<12∣ℛJ) ( _ES< 12 _J) >0, >0, Pr(ηES>12∣ℛJ) ( _ES> 12 _J) >0. >0. In words, the same static local input can be paired with early assignments that make either final value more likely. Proof of Theorem 1. The tower property gives ηG=E[ηES∣ℛJ]. _G=E[ _ES _J]. (7) Using mint,1−t=12−|t−12| \t,1-t\= 12-|t- 12|, the Bayes accuracy gap is Acon∗−Asol∗ A_con^*-A_sol^* =E[|ηES−12|] =E[| _ES- 12|] −E[|ηG−12|]. -E[| _G- 12|]. Conditional Jensen’s inequality and Eq. (7) imply E[|ηES−12|∣ℛJ]≥|ηG−12|.E[| _ES- 12| _J]≥| _G- 12|. Taking expectations proves Eq. (6). If the refined posterior lies on both sides of 1/21/2 with positive conditional probability, the conditional absolute-value inequality is strict. The stated positive-probability condition therefore gives Acon∗>Asol∗A_con^*>A_sol^*. □ Scope of the comparison. The two optima compared in Theorem 1 range over functions of the same receptive field: Asol∗A_sol^* is the Bayes accuracy given the static local input ℛJR_J, and Acon∗A_con^* is the Bayes accuracy given the augmented local input (ℛJ,XℛJES)(R_J,X^ES_R_J), at the same fixed depth L. Statements in the main text about “any solution predictor”, or about what “no predictor on instance features alone” can achieve, therefore quantify over predictors whose decision at a variable is a measurable function of its static local input, however large that function class is; they do not compare against predictors with a strictly larger input scope. In particular, if X∗X^* were almost surely determined by the full graph G—for example, a unique optimal solution returned by a deterministic solver—then the whole-graph posterior would be 0,1\0,1\-valued, posterior crossing could not occur at the whole-graph level, and a whole-graph predictor would attain perfect accuracy in principle, leaving no information-theoretic gain for the early solution. The strict-gain content of Theorem 1 is thus per locality level: for every fixed message-passing depth, augmenting the local input strictly improves the best achievable accuracy whenever posterior crossing occurs at that depth. This is the operative comparison for the models considered in this line of work, including ours and the baselines, which are all message-passing GNNs whose receptive field is fixed by the architecture and is typically far smaller than the benchmark graphs. Moreover, on practical benchmarks X∗X^* retains genuine randomness given G: instances frequently admit multiple optimal or near-optimal solutions, and the incumbent returned under a time budget depends on tie-breaking, thread timing, and budget truncation rather than on G alone. Under such residual randomness the whole-graph posterior is not 0,1\0,1\-valued either, so posterior crossing—and hence a strict gain from the early solution—can occur at any input scope, including the full graph. Sparse-Correction Identity The Bayes consistency rule is a∗(G,XES)r:=ξr≥12.a^*(G,X^ES)_r:=1\ _r≥ 12\. Define the event ∗:=ξJ<12=a∗(G,XES)J=0,C^*:=\ _J< 12\=\a^*(G,X^ES)_J=0\, and define p:=Pr(YJ=0),ρ:=Pr(∗).p:= (Y_J=0), ρ:= (C^*). If ρ>0ρ>0, also define q:=Pr(YJ=0∣∗).q:= (Y_J=0 ^*). Then q>1/2q>1/2, and a∗a^* satisfies bES=R(ha∗) b_ES=R(h_a^*) =p−ρ(2q−1), =p-ρ(2q-1), (8) ΔB:=Acon∗−Asol∗ _B:=A_con^*-A_sol^* =bG−p+ρ(2q−1). =b_G-p+ρ(2q-1). Thus ΔB>0 _B>0 exactly when p<bG+ρ(2q−1).p<b_G+ρ(2q-1). (9) For p≥bGp≥ b_G and ρ>0ρ>0, this is equivalent to q>12+p−bG2ρ.q> 12+ p-b_G2ρ. If ρ=0ρ=0, then bES=pb_ES=p and ΔB=bG−p _B=b_G-p. Derivation. For any consistency rule a, retaining an assignment has error 1−YJ1-Y_J, whereas using its binary complement has error YJY_J. Hence R(ha)=p+E[(2YJ−1)(1−a(G,XES)J)].R(h_a)=p+E[(2Y_J-1)(1-a(G,X^ES)_J)]. (10) On ∗C^*, the conditional probability of YJ=0Y_J=0 is q. Substituting a∗a^* into Eq. (10) gives R(ha∗)=p+ρ(1−q)−ρq=p−ρ(2q−1).R(h_a^*)=p+ρ(1-q)-ρ q=p-ρ(2q-1). Moreover, q=1−E[ξJ∣∗]>12.q=1-E[ _J ^*]> 12. The rule a∗a^* is the pointwise Bayes classifier for YJY_J, so Lemma 1 gives R(ha∗)=bESR(h_a^*)=b_ES. Subtracting this risk from bGb_G proves Eq. (8); the remaining statements follow by rearrangement. If ρ=0ρ=0, a∗a^* retains the early solution almost surely, and its error is p. □ Finite-Sample Analysis The population result ranges over all possible rules. For the finite-sample result, fix before observing the training instances a finite class A of N:=||≥1N:=|A|≥ 1 consistency rules whose variable-level decisions use the augmented local inputs defined above. Let Z1,…,ZmZ_1,…,Z_m be i.i.d. training instances from D. Suppose training and test instances follow D. Define A∗ A_A^* :=maxa∈Acc(ha), := _a Acc(h_a), Δ _A :=A∗−Asol∗=bG−mina∈R(ha). :=A_A^*-A_sol^*=b_G- _a R(h_a). Recall ΔB:=Acon∗−Asol∗ _B:=A_con^*-A_sol^*, and define the finite-class approximation gap α:=Acon∗−A∗. _A:=A_con^*-A_A^*. Then Δ=ΔB−α _A= _B- _A, separating the population information gain from the approximation cost of the finite class. For an instance Z, let sa(Z)s_a(Z) be the proportion of binary variables that rule a would flip. Assume every candidate flips at most a proportion s¯∈[0,1] s∈[0,1] on average: sa(Z) s_a(Z) :=1|ℬ(G)|∑r∈ℬ(G)(1−a(G,XES)r), := 1|B(G)| _r (G)(1-a(G,X^ES)_r), maxa∈E[sa(Z)] _a E[s_a(Z)] ≤s¯. ≤ s. Thus Δ _A is the population accuracy difference between the best rule available in A and the best predictor based only on the static local input. It can be nonpositive if the finite class does not contain a sufficiently accurate consistency rule. For a predictor that depends on the realized training sample and any training randomness, R(h)R(h) and Acc(h)Acc(h) below denote conditional population quantities evaluated on a fresh test triple independent of that training information. Let akeep(G,XES)r≡1a_keep(G,X^ES)_r≡ 1. Then hakeep(G,XES)=XESh_a_keep(G,X^ES)=X^ES and R(hakeep)=pR(h_a_keep)=p. Define the loss change relative to this baseline by Da(Z) D_a(Z) :=ℓha(Z)−ℓhakeep(Z), := _h_a(Z)- _h_a_keep(Z), D^a D_a :=1m∑k=1mDa(Zk). := 1m _k=1^mD_a(Z_k). Lemma 2 (uniform concentration). Following the finite-class Bernstein–union-bound argument (4), we apply concentration to instance-level loss differences relative to the always-retain rule. For every δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, supa∈|D^a−E[Da]| _a | D_a-E[D_a]| ≤βES, ≤ _ES, βES _ES :=2s¯mln2Nδ+43mln2Nδ. := 2 sm 2Nδ+ 43m 2Nδ. Proof. A rule differs from the always-retain baseline only on assignments that it marks inconsistent, so |Da(Z)| |D_a(Z)| ≤sa(Z)≤1, ≤ s_a(Z)≤ 1, Var(Da(Z)) (D_a(Z)) ≤E[Da(Z)2]≤E[sa(Z)]≤s¯. [D_a(Z)^2] [s_a(Z)]≤ s. Thus, when candidate corrections modify only a small proportion of early assignments, their loss differences have lower variance; this is the finite-class sparse-correction effect captured by s¯ s. Also, |Da(Z)−E[Da]|≤2|D_a(Z)-E[D_a]|≤ 2. (The sharper bound |Da(Z)−E[Da]|≤sa(Z)+s¯≤1+s¯|D_a(Z)-E[D_a]|≤ s_a(Z)+ s≤ 1+ s is available, since |Da(Z)|≤sa(Z)|D_a(Z)|≤ s_a(Z) and |E[Da]|≤s¯|E[D_a]|≤ s; we retain the simpler constant 22, which only inflates the second-order term and keeps the penalty identical to the main-text statement.) To make the additive constant explicit, start from the two-sided Bernstein inequality in exponential form (4, Theorem 2.10): for a variance proxy σ2σ^2 and centered range c, Pr(|D^a−E[Da]|≥ϵ)≤2exp(−mϵ22σ2+2cϵ/3). \! (| D_a-E[D_a]|≥ε )≤ 2 \! (- mε^22σ^2+2cε/3 ). Bounding the right-hand side by 2e−t2e^-t gives the quadratic condition mϵ2≥2σ2t+2ctϵ/3mε^2≥ 2σ^2t+2ctε/3, whose positive root satisfies ϵ=ct3m+2σ2tm+c2t29m2≤2σ2tm+2ct3m,ε= ct3m+ 2σ^2tm+ c^2t^29m^2≤ 2σ^2tm+ 2ct3m, where the inequality uses a+b≤a+b a+b≤ a+ b. Substituting the variance proxy σ2=s¯σ^2= s and the range c=2c=2 shows that the deviation 2s¯t/m+4t/(3m) 2 st/m+4t/(3m) is sufficient; the additive form is conservative relative to the exponential form because of this square-root relaxation. That is, for every fixed a and t>0t>0, Pr(|D^a−E[Da]|>2s¯tm+4t3m)≤2e−t. (| D_a-E[D_a]|> 2 stm+ 4t3m )≤ 2e^-t. Setting t=ln(2N/δ)t= (2N/δ) and applying a union bound over A proves the claim. □ Theorem 2 (restated). Let a a minimize the empirical 00–11 risk over A, and write h^ES:=ha h_ES:=h_ a. Let h^sol h_sol be any possibly data-dependent direct predictor determined without access to the fresh test triple and whose test-time decisions use only the static local inputs. Define εm(δ):=22s¯mln2Nδ+83mln2Nδ. _m(δ):=2 2 sm 2Nδ+ 83m 2Nδ. With probability at least 1−δ1-δ, Acc(h^ES)−Acc(h^sol)≥Δ−εm(δ)=ΔB−α−εm(δ).Acc( h_ES)-Acc( h_sol)≥ _A- _m(δ)= _B- _A- _m(δ). On the same event, R(h^ES)−mina∈R(ha)≤εm(δ).R( h_ES)- _a R(h_a)≤ _m(δ). Proof. Subtracting the same empirical loss of akeepa_keep from every candidate preserves the empirical minimizer. On the event in Lemma 2, choose a∗∈argmina∈R(ha).a_A^*∈ *arg\,min_a R(h_a). Then E[Da^] [D_ a] ≤D^a^+βES≤D^a∗+βES ≤ D_ a+ _ES≤ D_a_A^*+ _ES ≤E[Da∗]+2βES. [D_a_A^*]+2 _ES. Because R(ha)=p+E[Da]R(h_a)=p+E[D_a], it follows that R(h^ES) R( h_ES) ≤R(ha∗)+2βES ≤ R(h_a_A^*)+2 _ES (11) =1−A∗+2βES =1-A_A^*+2 _ES =bG−Δ+2βES. =b_G- _A+2 _ES. Condition on the realized training sample. Any resulting direct predictor whose test decision uses only the static local input has, by Bayes optimality, R(h^sol)≥bG.R( h_sol)≥ b_G. (12) Combining Eqs. (11) and (12) gives Acc(h^ES)−Acc(h^sol) ( h_ES)-Acc( h_sol) =R(h^sol)−R(h^ES) =R( h_sol)-R( h_ES) ≥Δ−2βES. ≥ _A-2 _ES. Since εm(δ)=2βES _m(δ)=2 _ES, the theorem follows. □ A sufficient sample size. If Δ>0 _A>0 and m>max32s¯ln(2N/δ)Δ2,16ln(2N/δ)3Δ,m> \ 32 s (2N/δ) _A^2, 16 (2N/δ)3 _A \, (13) then εm(δ)<Δ _m(δ)< _A. Consequently, with probability at least 1−δ1-δ, Acc(h^ES)>Acc(h^sol)Acc( h_ES)>Acc( h_sol). Proof. Let Λ:=ln(2N/δ) := (2N/δ). The two bounds in Eq. (13) imply 22s¯Λm<Δ2,8Λ3m<Δ2.2 2 s m< _A2, 8 3m< _A2. Adding the inequalities gives εm(δ)<Δ _m(δ)< _A; Theorem 2 then yields the claim. □ Illustrative Calculations Population gain. The sparse-correction condition can hold even when the early solution itself is less accurate than direct prediction. For example, take p=0.21,Asol∗=0.82,ρ=0.12,q=0.70.p=0.21, A_sol^*=0.82, ρ=0.12, q=0.70. These numerical values are purely illustrative. The right-hand side of Eq. (9) is 1−Asol∗+ρ(2q−1)=0.18+0.12(0.40)=0.228.1-A_sol^*+ρ(2q-1)=0.18+0.12(0.40)=0.228. Thus p=0.21<0.228p=0.21<0.228. The early solution alone has accuracy 0.790.79, which is below the direct-prediction accuracy 0.820.82, whereas identifying the inconsistent assignments gives Acon∗=1−[0.21−0.12(0.40)]=0.838.A_con^*=1- [0.21-0.12(0.40) ]=0.838. The early-solution input therefore raises the accuracy from 0.820.82 to 0.8380.838, an improvement of 1.81.8 percentage points. Finite-sample bound. For a numerical evaluation of the bound, consider a fixed class of N=4N=4 correction rules constructed to satisfy E[sa]≤0.0180E[s_a]≤ 0.0180. The value s¯=0.0180 s=0.0180 uses the 1.80%1.80\% median WA early-to-final difference in Figure 2 as an illustrative correction-budget scale, with E[sa]≤s¯E[s_a]≤ s retained as the stated rule-class assumption. Set the confidence level to 1−δ=0.91-δ=0.9 and take a deliberately conservative illustrative class advantage Δ=0.12 _A=0.12. Here ln2Nδ=ln80≈4.382. 2Nδ= 80≈ 4.382. The two terms on the right-hand side of Eq. (13) are 32s¯ln(2N/δ)Δ2 32 s (2N/δ) _A^2 ≈175.3, ≈ 175.3, 16ln(2N/δ)3Δ 16 (2N/δ)3 _A ≈194.8. ≈ 194.8. Thus the convenient sufficient condition in Eq. (13) would require m=195m=195. It is conservative because it separately bounds each of the two terms in εm _m by Δ/2 _A/2. Directly solving εm(0.1)<0.12 _m(0.1)<0.12, namely 22(0.0180)mln80+83mln80<0.12, 2 2(0.0180)m 80+ 83m 80<0.12, gives m>188.19m>188.19, so the smallest integer sample size satisfying the exact inequality is m=189m=189. Consistency requirement on the parameters. The illustrative values above are not jointly free. A rule that flips a proportion sa(Z)s_a(Z) of assignments changes the induced assignment on at most that fraction of variables, so its accuracy exceeds the always-retain accuracy by at most the expected flip rate: Acc(ha)≤(1−p)+E[sa]≤(1−p)+s¯Acc(h_a)≤(1-p)+E[s_a]≤(1-p)+ s. Consequently, Δ=A∗−Asol∗≤bG−p+s¯, _A=A_A^*-A_sol^*≤ b_G-p+ s, and the choice s¯=0.0180 s=0.0180, Δ=0.12 _A=0.12 implicitly requires bG−p≥0.102b_G-p≥ 0.102: the Bayes error of static local prediction must exceed the early-solution error rate by roughly ten percentage points or more. On WA, where the 1.80%1.80\% median early-to-final difference suggests p≈0.018p≈ 0.018, this amounts to bG≳0.12b_G 0.12; that is, even the best predictor using only the static local input must mislabel at least about 12%12\% of the binary variables. This is a substantive assumption about the difficulty of static prediction on the benchmark, not a consequence of the theorems, and we state it so that the example is read as a self-consistent operating point rather than a measured one. Smaller, still positive class advantages remain valid and simply rescale the sufficient sample size, which grows like Δ−2 _A^-2 in Eq. (13). Each MILP instance is one independent observation, so labels within an instance may be arbitrarily dependent. Accordingly, the penalty depends on m, the number of instances, rather than the total number of variable labels. The result assumes a fixed finite rule class selected by empirical variable-level 00–11 prediction loss. Its formal scope is finite-rule model selection, providing an abstraction that isolates instance-level estimation and the sparse-correction variance effect. In practice the predictor is a GNN trained by stochastic optimization with validation-based checkpoint selection, a procedure better described as comparing a small, data-dependent set of candidates—the checkpoints and configurations actually evaluated—than as exact empirical risk minimization over a class fixed in advance. Theorem 2 should therefore be read as an idealized account of that selection stage: it isolates the instance-level estimation cost and explains why sparse correction classes are cheap to select among, but it is not a uniform-convergence guarantee for the full GNN function class. Statements in the main text about the gain persisting under finite-sample model selection refer to this abstraction layer. Relation to the deployed algorithm. Two design choices of the deployed system fall outside the formal statements above and are worth flagging explicitly. First, the analysis scores rules by variable-level 00–11 accuracy—equivalently, thresholding the posterior at 1/21/2 over all binary variables—whereas the deployed method ranks variables by the predicted consistency probability and fixes only the top-ranked ones under a budget chosen by the downstream method. The theorems thus quantify the information available in the scores; how the scores are consumed by a ranking-based fixing rule is evaluated empirically. Second, the posteriors in this appendix condition on a single early solution, whereas at inference time the system averages, per variable, the logits computed from the last K improving solutions after aligning them to the reference solution XESX^ES. Because conditioning on the tuple of the last K solutions only enlarges the input, Theorem 1 applies verbatim to the ensembled variant, while the specific alignment-and-averaging estimator is a practical variance-reduction heuristic whose effect is evaluated empirically.