{"id":"f82dc713-dbda-4342-b49f-1d0812e827e7","arxiv_id":"2411.18321","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A graph neural network predicts MILP optimal objective values, and dynamic solver features improve detection of when the current incumbent is optimal.","lead":"This paper trains a graph neural network to predict the optimal objective value of mixed integer linear programs, then uses that prediction to detect when the solver has found the optimal solution. The method beats existing phase-transition criteria on some benchmarks, but the gains are small on set covering instances.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase-transition accuracy is measured on a filtered, time-weighted sample set; the claimed outperformance over Berthold et al. may not transfer to unfiltered solver operation.","rationale":"The paper's central comparative claim is the phase-transition detection: 'outperforming existing methods.' That claim rests entirely on Table 4, whose data-collection protocol introduces selection bias and sample-weighting that are not addressed in the manuscript. The Q1 regression is measured on an unfiltered held-out set, so the data-collection filter does not threaten that part directly, but the abstract bundles both tasks. The proposed test is cheap and directly checks generalization: if per-instance or unfiltered sampling preserves the ranking, the concern is resolved and conditional acceptance is justified; if not, the 'outperforming' claim is not established. The reader's verdict of CONDITIONAL remains appropriate, so I recommend no change.","tokens_in":9885,"tokens_out":10012,"duration_ms":91570,"concrete_test":"Re-run the phase-transition evaluation on the held-out test instances: (i) report the fraction of instances solved within 100 nodes; (ii) draw exactly one sample per instance at a fixed node count (e.g., 100) or uniformly over the phase-2/phase-3 boundary, and recompute accuracy for C_GNN_epsilon* and C_D versus the Berthold baselines. If the ranking changes or the margin over the majority class shrinks materially, the 0.02-after-100-nodes protocol is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.1 collects phase-transition samples only after 100 processed nodes and after an incumbent exists, with probability 0.02 per node. This has two inseparable effects on Table 4. First, instances solved within 100 nodes are excluded, so the test pool is conditioned on non-easy instances; the reported accuracy is not the accuracy on the instance distribution. Second, because each processed node is sampled independently, long runs—and especially the long proving phase—contribute many more samples than short runs. Table 4 pools all samples, so accuracy is weighted by node count, not by instance or decision point. The majority-class baseline (0.89 on set covering) already reflects this class imbalance, but the comparison among classifiers, and the paper's 'outperforming' claim, is only established under this particular filtered, time-weighted distribution. The paper does not report the fraction of instances solved within 100 nodes or per-instance accuracy, so a deployed solver that asks 'is the incumbent optimal?' early, or on easy instances, has no evidence that these accuracy numbers hold.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a machine-learning methodology for two related MILP tasks: (Q1) regression of the optimal objective value z* from a bipartite graph representation of the instance, using the root LP bound as contextual target (Θ1, Θ2, Θ3); and (Q2) classification of whether the current incumbent is optimal during branch-and-bound, using either the GNN prediction with a tunable tolerance epsilon (C_GNN^epsilon) or a logistic-regression classifier over dynamic solver features (C_D). The method is evaluated on set covering, combinatorial auctions, GISP, and a mixed benchmark. The reported results indicate that the GNN achieves small relative errors (0.54--3.32) and that the proposed phase-transition classifiers, especially C_D, outperform the best-estimate and rank-1 criteria of Berthold et al. The paper concludes that the approach could be integrated into MILP solvers for smarter decisions.","tokens_in":10115,"tokens_out":4733,"duration_ms":44306,"significance":"The task is well motivated: knowing z* (or whether the incumbent is optimal) can improve pruning, heuristics, and node selection in branch-and-bound, and it is arguably easier than full solution prediction. The paper is clearly written, the methodology is reproducible (code is available), and the treatment of the three benchmarks provides useful evidence that the approach works in different solver regimes. The regression targets Θ2 and Θ3 sensibly leverage the LP relaxation, and the dynamic feature set includes several carefully chosen metrics. However, the significance of the results as stated depends on the validity of the experimental comparisons; as detailed below, the data collection procedure and the lack of baselines/uncertainty measures weaken the central claim that the proposed methods 'outperform existing approaches.' If those issues are addressed, the paper would make a solid contribution to the growing literature on ML-augmented MILP solving.","major_comments":[{"comment":"The phase-transition evaluation is carried out on a filtered, time-weighted sample set. Samples are collected only after 100 processed nodes, only after an incumbent exists, and with probability 0.02 per processed node. This has two inseparable effects: (a) instances solved within the first 100 nodes are excluded, so the test pool is conditioned on 'non-easy' instances; and (b) because every processed node is an independent sampling opportunity, long runs (particularly the long proving phase) contribute far more samples than short runs. Table 4 pools all samples, so the reported accuracy is a node-weighted average, not an instance-level or decision-point-level accuracy. The paper does not report the fraction of instances excluded nor per-instance accuracy, so the claim in Section 5.2 that the proposed classifiers 'outperform existing approaches' is only established under this particular filtered, time-weighted distribution. For a deployment that queries the classifier early or on easy instances, the reported numbers give no evidence of transfer. Please report instance-level accuracy, the excluded fraction, and results on an unfiltered sample set (or justify why the filtered distribution is the relevant one).","section":"Section 5.1, 'Data collection procedure'; Table 4"},{"comment":"The regression task (Q1) is evaluated only for the proposed GNN model. No comparison is made with simple, non-learned baselines such as predicting zLP, predicting a constant, or a linear regression on the graph features. Since the Θ2 and Θ3 targets explicitly incorporate the LP value, the reported relative errors (e.g., 0.54--0.80 for set covering) may largely reflect how close zLP is to z*, rather than the contribution of the GNN. Without such a baseline, the 'high accuracy' claim is not quantified relative to a null model. Additionally, the text in Section 5.2 states that the mixed model 'performs comparably' to specialized models, but this is not supported by all cells: for combinatorial auctions, the mixed model with Θ2 degrades to 1.17% error from 0.55% in the specialized model. Please add baseline comparisons and moderate the over-generalization.","section":"Section 5.2, Tables 2 and 3"},{"comment":"No measures of uncertainty are reported. The accuracy differences between classifiers are sometimes small (e.g., set covering: majority 0.89, C_GNN^epsilon 0.93, C_D 0.90), and the phase-analysis percentages in Figure 2 are averages over 300 samples with no variance or confidence intervals. Without standard errors, confidence intervals, or significance tests, the comparative claim that the proposed methods 'outperform existing approaches' is not statistically supported. Please add bootstrap confidence intervals or other uncertainty estimates for the key numbers.","section":"Tables 2--4 and Figure 2"}],"minor_comments":[{"comment":"The symbol epsilon is used both as the tolerance in Eq. (6) and as the small constant in the gap definition in Eq. (7). This is confusing; please use a different symbol (e.g., epsilon_0) in Eq. (7).","section":"Equation (7)"},{"comment":"The trend of open nodes tau(t) requires a window size h, but the choice of h is not reported in Section 5.1. Please specify the value used and whether it was tuned.","section":"Section 4.2, dynamic features"},{"comment":"The sampling probability of 0.02 is stated but not justified. A brief explanation of why this rate was chosen (e.g., trade-off between sample volume and independence) would be helpful.","section":"Section 5.1, 'Data collection procedure'"},{"comment":"Table 1 mentions 'SET2, A' for GISP without explaining the parameters in the table caption; please expand the caption or refer explicitly to the configuration in [5]. Figure 4 lacks axis labels and a description of how feature importance is computed (e.g., standardized logistic-regression coefficients); please clarify.","section":"Table 1 and Figure 4"},{"comment":"Minor typographical issues: 'intances' in the caption of Table 3, and 'Y orke-Smith' in the author block should be 'Yorke-Smith'. Please proofread.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is a reasonable fit for math.OC and the code availability is a plus. The stress-test concern is valid: the data collection filter in Section 5.1 directly conditions the phase-transition evaluation, and the paper does not quantify the impact. The regression task also lacks any baseline, making it impossible to assess the GNN's added value over the LP relaxation. I would encourage the authors to address these issues with additional experiments and a more measured interpretation of 'outperforming.' A major revision is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's genuinely new contribution is direct regression of the optimal objective value from a GNN over the MILP bipartite graph, plus a phase-transition classifier built on dynamic features. The regression part is clean: the LP-normalized targets make sense, the mixed-model generalization is a nice check, and the code is public. The dynamic features (median gap, open-node trend, ratio to GNN prediction) are new and the use of logistic regression for interpretability is sensible. Credit where it's due: this is a step beyond solution-prediction work and the experiments cover three structurally different benchmarks.\n\nThe soft spots are real but uneven. For Q1, the regression tables report only average relative error, with no error bars or significance tests, and there is no non-GNN baseline—a simple linear model on root LP gap or instance size would help. Still, this is a minor weakness because the task is per-instance and the error numbers look reasonable.\n\nThe bigger issue is Q2. Section 5.1 says samples are collected only after 100 processed nodes, only once an incumbent exists, and then with probability 0.02 per node. That filters out easy instances and makes long runs contribute far more samples. So Table 4's accuracy is for a node-weighted, filtered distribution, not the instance distribution. The stress-test note is correct on this. The claim of 'outperforming existing methods' is only established under this sampling scheme, and on set covering the gain over the majority class is tiny (0.93 vs 0.89). No per-instance accuracy or fraction of instances solved within 100 nodes is reported, so a practitioner cannot know whether these numbers transfer to early or easy solves. These are fixable with reruns and better reporting, but as it stands the phase-transition result should be treated cautiously.\n\nOverall, the paper is a solid empirical study of a sensible new task, written clearly and with honest discussion of the epsilon tradeoff. It deserves a serious referee, not a desk reject. I would send it to review and ask the authors to address the sampling bias and add basic statistical rigor. I would not cite the phase-transition numbers in my own work until that's done.","headline":"Interesting new task with a clean regression setup, but the phase-transition evaluation is biased by sampling only after 100 nodes, so treat the claimed outperformance with care.","tokens_in":10630,"tokens_out":1630,"would_cite":false,"duration_ms":20079,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C10","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph neural network predicts the optimal objective value of mixed-integer programs, and dynamic search metrics detect when the incumbent is optimal, beating standard phase-transition criteria.","keywords":["mixed integer linear programming","branch-and-bound","graph neural network","optimal objective value prediction","phase transition prediction","dynamic solver features","regression and classification","combinatorial optimization"],"falsifier":"Run the trained phase-transition classifier on instances that are solved within fewer than 100 nodes, or for which no incumbent exists yet, and compare its accuracy against the true phase labels recorded by the solver; if accuracy collapses on those easy instances, the reported performance is an artifact of the 100-node filter rather than a general property.","tokens_in":9705,"feed_emoji":"🎯","tokens_out":8743,"duration_ms":67106,"temperature":0.7,"pith_summary":"This paper asks whether a machine-learning model can learn the optimal objective value of a mixed-integer linear program (MILP) during the solution process, and whether that knowledge can tell the solver when its current best solution is already optimal. The authors build a graph neural network that reads the standard bipartite graph representation of a MILP, together with the optimal value of the LP relaxation, and predicts the optimal objective value under three alternative targets. They then combine this prediction with dynamic solver statistics through a logistic regression classifier to predict the transition from the improvement phase to the proving phase of branch-and-bound. On set covering, combinatorial auctions, generalized independent set problems, and a mixed benchmark, the reported accuracies exceed those of the best-estimate and rank-1 criteria from the literature. If the results hold, a solver could use such predictions to prune the search tree earlier, adjust its configuration by phase, and stop heuristics once optimality has effectively been reached.","feed_headline":"Graph neural net predicts optimal value in integer programming","feed_subtitle":"Knowing the optimum early lets branch-and-bound solvers prune harder and stop sooner; this paper shows it can be learned.","key_machinery":"The key machinery is a message-passing graph neural network over the bipartite graph whose nodes are constraints and variables, with two half-convolution layers (Equations 4--5) that update constraint embeddings from variable embeddings and then variable embeddings from the updated constraint embeddings, followed by average pooling. The regression targets $\\Theta_1 = z^*$, $\\Theta_2 = z^*/z^{LP}$, and $\\Theta_3 = z^* - z^{LP}$ are all converted back to an absolute prediction $\\tilde{z}^*$. The phase-transition classifiers are (i) a threshold rule $C^{\\mathrm{GNN}}_\\epsilon$ that declares the incumbent optimal when $\\bar{z} < \\tilde{z}^* + \\epsilon|\\tilde{z}^*|$, and (ii) a logistic regression $C^D$ over the SCIP gap, tree weight, median gap, trend of open nodes, and the ratio of $\\tilde{z}^*$ to the incumbent.","core_discovery":"The paper's central claim is that the optimal objective value of a MILP, and the moment when the current incumbent is optimal, can be predicted accurately from features available during the branch-and-bound search. A graph neural network reads the bipartite constraint-variable graph of the instance and the root LP value $z^{LP}$, and is trained against three targets: the optimal value $z^*$, the ratio $z^*/z^{LP}$, and the gap $z^* - z^{LP}$; the two targets that use $z^{LP}$ consistently give lower relative error. For the phase-transition task, combining the GNN's prediction with five dynamic solver metrics in a logistic regression yields the best accuracy on every benchmark, while the $\\epsilon$-tuned GNN classifier alone beats the best-estimate and rank-1 baselines. The authors further report that a model trained on a mixture of all three instance types generalizes well to each individual type.","pith_inferences":["A natural extension not explored in the paper is to close the loop by feeding the predicted value into a solver's branching, node-selection, or pruning rules and measuring end-to-end solve-time changes rather than classification accuracy alone.","The phase-transition classifier could be repurposed as a predictor of remaining prove time, since the transition to the proving phase marks the point after which the search only certifies optimality.","Because the LP-informed targets outperform direct prediction, accuracy likely depends on the quality of the LP relaxation; a testable check is to correlate per-instance LP-relaxation gap with prediction error across a wider benchmark family.","The 100-node filter and 0.02 sampling rate mean the reported numbers describe runs that have already passed presolving; applying the methodology to time-limit-bounded solving, where runs often terminate early, would require re-collecting data under those conditions."],"forward_implications":["A solver that trusts the predicted optimal value can prune any node whose LP lower bound already exceeds the prediction, and can terminate the search once the incumbent reaches it.","The $\\epsilon$ parameter provides a direct control knob for the false-positive/false-negative tradeoff in declaring optimality.","The logistic-regression classifier is interpretable, and its per-benchmark feature weights show that the relative importance of gap, tree weight, median gap, trend, and GNN ratio varies with instance type.","A single GNN trained on a mixture of instance types performs comparably to specialized models, so one predictor can serve a heterogeneous workload.","The literature baselines (best-estimate and rank-1) systematically declare the phase transition too early, whereas the tuned GNN and dynamic classifiers report higher accuracy with fewer false positives."],"supporting_citations":[{"why":"Introduces the bipartite constraint-variable graph representation of MILPs used as GNN input.","marker":"[9]"},{"why":"Defines the three solving phases and the best-estimate and rank-1 baseline classifiers.","marker":"[2]"},{"why":"Provides the solver and the formal gap definition used as a dynamic feature.","marker":"[3]"},{"why":"Introduces the tree-weight metric used as a dynamic feature.","marker":"[13]"},{"why":"Provides the related dynamic prediction task of estimating final branch-and-bound tree size.","marker":"[11]"},{"why":"Supplies the set-covering instance generator used in the benchmarks.","marker":"[1]"},{"why":"Supplies the combinatorial auction instance generator used in the benchmarks.","marker":"[14]"},{"why":"Supplies the generalized independent set problem instance generator used in the benchmarks.","marker":"[5]"}],"fun_headline_variants":["GNN predicts optimal MILP value for faster solver cuts","Predict MILP optimum with graph neural networks","Learning to foresee optimal integer programming values","Graph nets forecast MILP optimum to prune search","MILP optimum prediction via GNN speeds branch-and-bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the data collection protocol--recording samples only after the solver has processed 100 nodes and has an incumbent, at a sampling probability of 0.02--produces a training and evaluation distribution that represents the solving situations where the predictor will be used.","fun_headline_variants_meta":{"raw":{"variants":["GNN predicts optimal MILP value for faster solver cuts","Predict MILP optimum with graph neural networks","Learning to foresee optimal integer programming values","Graph nets forecast MILP optimum to prune search","MILP optimum prediction via GNN speeds branch-and-bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000351,"raw_usage":{"total_tokens":1870,"prompt_tokens":859,"completion_tokens":1011,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":938}},"tokens_in":475,"tokens_out":1011,"duration_ms":7359,"temperature":1.0,"reasoning_tokens":938,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:17:44.205462+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the trained phase-transition classifier on instances that are solved within fewer than 100 nodes, or for which no incumbent exists yet, and compare its accuracy against the true phase labels recorded by the solver; if accuracy collapses on those easy instances, the reported performance is an artifact of the 100-node filter rather than a general property.","supporting_citations":[{"cited_title":"Gasse, D","cited_arxiv_id":null,"evidence_quote":"Introduces the bipartite constraint-variable graph representation of MILPs used as GNN input."},{"cited_title":"Berthold, G","cited_arxiv_id":null,"evidence_quote":"Defines the three solving phases and the best-estimate and rank-1 baseline classifiers."},{"cited_title":"Bestuzheva, M","cited_arxiv_id":null,"evidence_quote":"Provides the solver and the formal gap definition used as a dynamic feature."},{"cited_title":"Kilby, J","cited_arxiv_id":null,"evidence_quote":"Introduces the tree-weight metric used as a dynamic feature."},{"cited_title":"Hendel, D","cited_arxiv_id":null,"evidence_quote":"Provides the related dynamic prediction task of estimating final branch-and-bound tree size."},{"cited_title":"Balas and A","cited_arxiv_id":null,"evidence_quote":"Supplies the set-covering instance generator used in the benchmarks."},{"cited_title":"Leyton-Brown, M","cited_arxiv_id":null,"evidence_quote":"Supplies the combinatorial auction instance generator used in the benchmarks."},{"cited_title":"Colombi, R","cited_arxiv_id":null,"evidence_quote":"Supplies the generalized independent set problem instance generator used in the benchmarks."}],"review_version":1}