REVIEW 3 major objections 5 minor 21 references
Learning optimal objective values for MILP
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 5.1, 'Data collection procedure'; Table 4] 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 5.2, Tables 2 and 3] 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.
- [Tables 2--4 and Figure 2] 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.
minor comments (5)
- [Equation (7)] 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 4.2, dynamic features] 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 5.1, 'Data collection procedure'] 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.
- [Table 1 and Figure 4] 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.
- [Throughout] Minor typographical issues: 'intances' in the caption of Table 3, and 'Y orke-Smith' in the author block should be 'Yorke-Smith'. Please proofread.
Circularity Check
No circularity identified: the GNN and dynamic classifiers are trained and evaluated on disjoint instance sets, so the claimed predictions are genuine out-of-sample results.
full rationale
The paper's prediction of optimal objective values (Q1) and its phase-transition classification (Q2) are not circular. The GNN is trained on separate training instances per benchmark and evaluated on held-out test instances, with error measured by Eq. (11) on those held-out sets. The phase-transition classifiers C_GNN_epsilon and C_D use the GNN output and dynamic features such as gap, tree weight, median gap, and trend, but the training labels indicate whether the current incumbent equals the solver-known optimum z*, and the train/test split remains instance-disjoint. The epsilon parameter is tuned only on the validation set, not on the test set. Although the data-collection procedure (Section 5.1) discards instances solved within the first 100 nodes and samples later nodes with probability 0.02, this affects distributional representativeness and transferability, not circularity: it does not make any predicted quantity equal to an input by construction, and the paper reports the majority-class baseline so the comparison is transparent. Self-citations such as [18] appear only as background literature and are not load-bearing for the experimental claims.
Assumptions & free parameters
free parameters (4)
- GNN weights =
learned during training (values not listed)
- Epsilon (epsilon*) for C_GNN =
not reported in text; tuned on validation set over [-0.02, 0.02]
- Window size h for open-node trend =
not specified
- Sampling probability and node threshold =
0.02, 100
assumptions (3)
- domain assumption Instances are feasible.
- domain assumption The Gasse et al. bipartite graph representation and features are suitable inputs for learning optimal values.
- ad hoc to paper The three benchmark families are representative of real-life MILPs.
Cite this review
Pith. "Pith review of Learning optimal objective values for MILP." pith.science (2026). https://pith.science/paper/TB3NUXL5
@misc{pith2026241118321,
author = {Pith},
title = {Pith review of: Learning optimal objective values for MILP},
year = {2026},
howpublished = {\url{https://pith.science/paper/TB3NUXL5}},
note = {Machine review of arXiv:2411.18321}
}
read the original abstract
Modern Mixed Integer Linear Programming (MILP) solvers use the Branch-and-Bound algorithm together with a plethora of auxiliary components that speed up the search. In recent years, there has been an explosive development in the use of machine learning for enhancing and supporting these algorithmic components. Within this line, we propose a methodology for predicting the optimal objective value, or, equivalently, predicting if the current incumbent is optimal. For this task, we introduce a predictor based on a graph neural network (GNN) architecture, together with a set of dynamic features. Experimental results on diverse benchmarks demonstrate the efficacy of our approach, achieving high accuracy in the prediction task and outperforming existing methods. These findings suggest new opportunities for integrating ML-driven predictions into MILP solvers, enabling smarter decision-making and improved performance.
Figures
Reference graph
Works this paper leans on
-
[1]
E. Balas and A. Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, pages 37–60. Springer, 1980
work page 1980
-
[2]
T. Berthold, G. Hendel, and T. Koch. From feasibility to improvement to proof: three phases of solving mixed- integer programs. Optimization Methods and Software, 33(3):499–517, 2018
work page 2018
-
[3]
K. Bestuzheva, M. Besanc ¸on, W.-K. Chen, A. Chmiela, T. Donkiewicz, J. van Doornmalen, L. Eifler, O. Gaul, G. Gamrath, A. Gleixner, L. Gottwald, C. Graczyk, K. Halbig, A. Hoen, C. Hojny, R. van der Hulst, T. Koch, M. L¨ubbecke, S. J. Maher, F. Matter, E. M¨uhmer, B. M¨uller, M. E. Pfetsch, D. Rehfeldt, S. Schlein, F. Schl¨osser, F. Serrano, Y . Shinano, ...
work page 2021
-
[4]
A. Chmiela, E. Khalil, A. Gleixner, A. Lodi, and S. Pokutta. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 34:24235–24246, 2021
work page 2021
-
[5]
M. Colombi, R. Mansini, and M. Savelsbergh. The generalized independent set problem: Polyhedral analysis and solution approaches. European Journal of Operational Research, 260(1):41–55, 2017
work page 2017
-
[6]
J.-Y . Ding, C. Zhang, L. Shen, S. Li, B. Wang, Y . Xu, and L. Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 1452–1459, 2020
work page 2020
-
[7]
N. Efthymiou and N. Yorke-Smith. Predicting the optimal period for cyclic hoist scheduling problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR) , volume 13884 of Lecture Notes in Computer Science, pages 238–253. Springer, 2023
work page 2023
-
[8]
M. Fischetti, A. Lodi, and G. Zarpellon. Learning MILP resolution outcomes before reaching time-limit. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), volume 16, pages 275–291. Springer, 2019
work page 2019
Show all 21 references
-
[9]
Gasse, D
M. Gasse, D. Ch ´etelat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convo- lutional neural networks. Advances in Neural Information Processing Systems, 32, 2019
2019
-
[10]
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 International Conference on Learning Representations ,
-
[11]
Hendel, D
G. Hendel, D. Anderson, P. Le Bodic, and M. E. Pfetsch. Estimating the size of branch-and-bound trees. IN- FORMS Journal on Computing, 34(2):934–952, 2022
2022
-
[12]
E. B. Khalil, C. Morris, and A. Lodi. MIP-GNN: A data-driven framework for guiding combinatorial solvers. AAAI, 2022
2022
-
[13]
Kilby, J
P. Kilby, J. Slaney, S. Thi ´ebaux, T. Walsh, et al. Estimating search tree size. In Proceedings of the AAAI Conference on Artificial Intelligence, 2006
2006
-
[14]
Leyton-Brown, M
K. Leyton-Brown, M. Pearson, and Y . Shoham. Towards a universal test suite for combinatorial auction algo- rithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pages 66–76, 2000
2000
-
[15]
V . Nair, S. Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraat- madja, P. Wang, et al. Solving mixed integer programs using neural networks.arXiv preprint arXiv:2012.13349, 2020
2012 arXiv
-
[16]
M. B. Paulus, G. Zarpellon, A. Krause, L. Charlin, and C. Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International Conference on Machine Learning, pages 17584–17600. PMLR, 2022
2022
-
[17]
Learning optimal objective values for MILP
L. Scavuzzo. Code for the paper “Learning optimal objective values for MILP”, 2024. https://github.com/ lascavana/ObjValPrediction
2024
-
[18]
Scavuzzo, K
L. Scavuzzo, K. Aardal, A. Lodi, and N. Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming, pages 1–44, 2024
2024
-
[19]
Y . Shen, Y . Sun, X. Li, A. C. Eberhard, and A. T. Ernst. Adaptive solution prediction for combinato- rial optimization. European Joural of Operational Research , 309:1392–1408, 2022. URL https://api. semanticscholar.org/CorpusID:256358882
2022
-
[20]
Sonnerat, P
N. Sonnerat, P. Wang, I. Ktena, S. Bartunov, and V . Nair. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201, 2021. 12
2021 arXiv
-
[2023]
URL https://api.semanticscholar.org/CorpusID:256827203
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.