Pith. sign in

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 →

arxiv 2411.18321 v1 pith:TB3NUXL5 submitted 2024-11-27 math.OC cs.AIcs.LGcs.MS

classification math.OCcs.AIcs.LGcs.MS MSC 90C1190C1068T05
keywords mixedintegerlinearprogrammingbranch-and-boundgraphneuralnetworkoptimalobjectivevaluepredictionphasetransitiondynamicsolverfeaturesregressionandclassificationcombinatorialoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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)
  1. [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).
  2. [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.
  3. [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)
  1. [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).
  2. [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.
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 4 free parameters · 3 assumptions · 0 invented entities

The paper's central claim depends on standard ML training (learned weights, tuned epsilon) and on the domain assumptions listed. No new physical or mathematical entities are introduced.

free parameters (4)
  • GNN weights = learned during training (values not listed)
    The graph neural network's trainable weights W(11), W(12), W(21), W(22) are fit to training instances; they are the core model parameters.
  • Epsilon (epsilon*) for C_GNN = not reported in text; tuned on validation set over [-0.02, 0.02]
    The classifier's confidence margin is chosen by grid search on the validation set.
  • Window size h for open-node trend = not specified
    The trend of open nodes depends on an unstated window size h; this affects the dynamic features.
  • Sampling probability and node threshold = 0.02, 100
    Data collection design choices that affect the training distribution and evaluation.
assumptions (3)
  • domain assumption Instances are feasible.
    Stated in Section 2: 'For the purpose of our study we assume that the instances are feasible.' This excludes infeasible MILPs from the evaluation.
  • domain assumption The Gasse et al. bipartite graph representation and features are suitable inputs for learning optimal values.
    The GNN operates on this representation without justification that it captures all information relevant to z-star; this comes from prior work.
  • ad hoc to paper The three benchmark families are representative of real-life MILPs.
    The paper tests only synthetic benchmarks from standard generators; the generalization to other MILP classes is assumed.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2411.18321 by the authors.

Figure 1
Figure 1. Optimal objective value prediction task. The MILP representation is computed after the root node has been [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Phase analysis of three instance types. We divide the solution process into (1) Feasibility, in dark yellow, [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Prediction accuracy of the different classifier models. We show the fraction of correctly classified samples [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Feature importance of the dynamic models trained to predict phase transition for each of the benchmarks. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

  1. [1]

    Balas and A

    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

  2. [2]

    Berthold, G

    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

  3. [3]

    Bestuzheva, M

    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, ...

  4. [4]

    Chmiela, E

    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

  5. [5]

    Colombi, R

    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

  6. [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

  7. [7]

    Efthymiou and N

    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

  8. [8]

    Fischetti, A

    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

Show all 21 references
  1. [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

  2. [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 ,

  3. [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

  4. [12]

    E. B. Khalil, C. Morris, and A. Lodi. MIP-GNN: A data-driven framework for guiding combinatorial solvers. AAAI, 2022

  5. [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

  6. [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

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [2023]

    URL https://api.semanticscholar.org/CorpusID:256827203

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.