Supplementary Materials to Graph Convolutional Branch and Bound

Andrea Cesare Grosso; Cristina Zucca; Laura Sacerdote; Lorenzo Sciandra; Roberto Esposito

arxiv: 2406.03099 · v4 · submitted 2024-06-05 · 💻 cs.LG · math.OC

Supplementary Materials to Graph Convolutional Branch and Bound

Lorenzo Sciandra , Roberto Esposito , Andrea Cesare Grosso , Laura Sacerdote , Cristina Zucca This is my paper

Pith reviewed 2026-05-24 00:01 UTC · model grok-4.3

classification 💻 cs.LG math.OC

keywords graph convolutional networksbranch and boundtraveling salesman problemcombinatorial optimizationunsupervised learningheuristic learningexact solvers

0 comments

The pith

A graph convolutional network learns optimality scores to speed branch-and-bound search on the traveling salesman problem.

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

The paper integrates deep learning into exact combinatorial solvers by training a graph convolutional neural network to estimate how close partial solutions are to optimality. This score replaces or augments heuristic rules inside a branch-and-bound tree for the traveling salesman problem, guiding which nodes to explore next. The network is trained without labeled data through an unsupervised strategy that lets it handle graphs of different sizes. When added to the Concorde solver, the hybrid method explores fewer nodes and finishes faster on test instances. Results on the 1-tree relaxation appear in the supplementary materials.

Core claim

The authors claim that an unsupervised graph convolutional network can produce an optimality score usable inside branch-and-bound, yielding a hybrid solver that traverses fewer nodes and requires less total time than the unaugmented Concorde solver on the traveling salesman problem.

What carries the argument

Graph Convolutional Branch and Bound (GCBB), which inserts a graph convolutional neural network that outputs an optimality score to rank and prune nodes in the branch-and-bound tree.

If this is right

Fewer nodes are explored in the branch-and-bound tree for TSP instances.
Overall wall-clock time for exact TSP solutions decreases.
The same unsupervised training procedure applies to TSP graphs whose sizes differ from the training graphs.
The 1-tree relaxation results remain available for separate inspection in the supplementary materials.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Learned node scores could replace hand-designed branching rules in other exact solvers for NP-hard graph problems.
If the same architecture works on different combinatorial problems cast as graphs, the method could generalize beyond TSP.
The approach opens the possibility of training once on moderate-sized instances and deploying on larger ones without retraining.

Load-bearing premise

The score produced by the network reliably indicates how close a partial tour is to the global optimum even though the network sees no labeled optimal solutions during training.

What would settle it

On standard TSP benchmark instances, run the hybrid solver and the baseline Concorde solver side by side and check whether the number of explored nodes and total runtime show no reduction.

Figures

Figures reproduced from arXiv: 2406.03099 by Andrea Cesare Grosso, Cristina Zucca, Laura Sacerdote, Lorenzo Sciandra, Roberto Esposito.

**Figure 2.** Figure 2: Performances achieved by the GCBB and BB solver grouped in two distinct performance profiles for each graph size where an exact model exists. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** Figure 3: Performances of the GCBB and BB solver grouped in distinct performance profiles for each graph size where an exact model does not exist. In panels 3a and 3b, the dummy cities technique is employed to increase the graph size, while clustering is used in 3c. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

read the original abstract

This article explores the integration of deep learning models into combinatorial optimization pipelines, specifically targeting NP-hard problems. Traditional exact algorithms for such problems often rely on heuristic criteria to guide the exploration of feasible solutions. In this work, we propose using neural networks to learn informative heuristics, most notably, an optimality score that estimates a solution's proximity to the optimum. This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient traversal of the solution space. Focusing on the Traveling Salesman Problem, we introduce Concorde, a state-of-the-art solver, and present a hybrid approach called Graph Convolutional Branch and Bound, which augments it with a graph convolutional neural network trained with a novel unsupervised training strategy that facilitates generalization to graphs of varying sizes without requiring labeled data. Empirical results demonstrate the effectiveness of the proposed method, showing a significant reduction in the number of explored branch-and-bound nodes and overall computational time. Some of the results concerning the use of the 1-tree relaxation are in the supplementary materials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This supplementary note on 1-tree relaxations adds little new; the GCN-Concorde hybrid's node reductions hinge on an unverified unsupervised optimality score that the visible text does not validate.

read the letter

This is supplementary material on 1-tree relaxation results for the Graph Convolutional Branch and Bound method on TSP. The referenced main paper combines Concorde with a GCN that produces an optimality score through unsupervised training, aiming to guide branch-and-bound node selection and handle graphs of different sizes without labels. The unsupervised training approach is the clearest practical addition here, as it sidesteps the need for optimal solutions during learning, which is a common bottleneck in this area. If the reported drops in explored nodes and runtime hold up in the full experiments, that would be a useful engineering improvement for exact TSP solvers. The abstract's claim of significant reductions is the main point of interest for operations research readers already working with Concorde or similar solvers. The soft spot is exactly the one flagged in the stress-test note: there is no visible check that the learned scores track actual optimality gaps or 1-tree bounds rather than producing arbitrary rankings. Without equations, loss details, or independent validation in this document, the central empirical claim cannot be assessed. The text is labeled as supplementary and states that the core method and claims are in the main paper, so this piece does not introduce a new result on its own. This is for specialists already following learning-to-optimize work on routing problems who want to see the 1-tree specifics. A reader would not bring this supplement alone to a reading group. It does not merit peer review as a standalone submission.

Referee Report

1 major / 1 minor

Summary. The manuscript presents supplementary materials for a hybrid Graph Convolutional Branch and Bound approach that augments the Concorde TSP solver with a graph convolutional network. The GCN learns an optimality score via a novel unsupervised training strategy that enables generalization across graph sizes without labeled data. This score is used to guide node selection inside branch-and-bound, with the central empirical claim being a significant reduction in the number of explored nodes and overall runtime relative to the Concorde baseline. Some results involving the 1-tree relaxation are deferred to the supplementary materials.

Significance. If the unsupervised optimality score can be shown to correlate with true optimality gaps and to improve node selection over Concorde defaults, the work would demonstrate a practical way to inject learned heuristics into exact solvers while preserving size generalization. The unsupervised training approach, if validated, would be a useful technical contribution for combinatorial optimization pipelines that lack labeled optima.

major comments (1)

[Abstract / method description] The central claim of reduced B&B node count and runtime (abstract) rests on the assumption that the GCN-derived optimality score meaningfully improves node selection. No independent check—such as a reported correlation between the learned scores and true optimality gaps, or an ablation against the 1-tree bound—is described that would confirm the unsupervised loss produces informative rankings rather than arbitrary orderings. Without this link, the reported reductions cannot be attributed to the proposed method.

minor comments (1)

[Abstract] The abstract states that 1-tree relaxation results appear in the supplementary materials, but it is unclear whether these results are used to validate the optimality score or serve another purpose.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the detailed review. We appreciate the feedback on strengthening the validation of our method. Below we address the major comment.

read point-by-point responses

Referee: [Abstract / method description] The central claim of reduced B&B node count and runtime (abstract) rests on the assumption that the GCN-derived optimality score meaningfully improves node selection. No independent check—such as a reported correlation between the learned scores and true optimality gaps, or an ablation against the 1-tree bound—is described that would confirm the unsupervised loss produces informative rankings rather than arbitrary orderings. Without this link, the reported reductions cannot be attributed to the proposed method.

Authors: We agree that explicitly demonstrating the correlation between the GCN optimality scores and true optimality gaps would strengthen the attribution of the observed improvements to the proposed method. In the revised version of the supplementary materials, we will add a new subsection reporting the correlation coefficients (e.g., Spearman rank correlation) between the learned scores and the actual gaps on a set of test instances. Additionally, we will include an ablation comparing the GCN-guided node selection against using only the 1-tree bound for prioritization, to directly address the concern about informative rankings versus arbitrary orderings. These additions will be placed in the supplementary materials alongside the existing 1-tree relaxation results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical claims rest on external benchmarks

full rationale

The provided text contains no equations, derivation steps, or load-bearing self-citations. The core contribution is an empirical hybrid solver whose performance is measured by observable reductions in B&B nodes and runtime against Concorde baselines. The unsupervised training strategy is presented as enabling generalization, but the paper does not define the optimality score in terms of itself or rename fitted quantities as predictions. No uniqueness theorems or ansatzes are invoked via self-citation. The derivation chain is therefore self-contained against the reported experimental outcomes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no equations, no fitted constants, and no new postulated entities; ledger is therefore empty.

pith-pipeline@v0.9.0 · 5710 in / 942 out tokens · 18934 ms · 2026-05-24T00:01:28.279477+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227, 2019

[BLP21] YoshuaBengio,AndreaLodi,andAntoineProuvost.“Machine learningforcombinatorialoptimization:Amethodologicaltour d’horizon”. In:European Journal of Operational Research290.2 (2021), pp. 405–421.issn: 0377-2217. doi: 10 . 1016 / j . ejor . 2020.07.063. [JLB19] Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. “An EfficientGraphConvolutionalNetwor...

work page arXiv 2021
[2]

Learning to Branch in Mixed Integer Pro- gramming

[Kha+16] Elias Khalil et al. “Learning to Branch in Mixed Integer Pro- gramming”.en.In:ProceedingsoftheAAAIConferenceonArtificial Intelligence30.1(Feb.2016).Number:1. issn:2374-3468. doi:

work page 2016
[3]

Neu- ralMachineTranslationbyJointlyLearningtoAlignandTrans- late

1609/aaai.v30i1.10080. url: https://ojs.aaai.org/index. php/AAAI/article/view/10080(visited on 05/27/2024). [BCB15] DzmitryBahdanau,KyunghyunCho,andYoshuaBengio.“Neu- ralMachineTranslationbyJointlyLearningtoAlignandTrans- late”. In:3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proc...

work page 2024
[4]

Deeplearn- ing

[LBH15] YannLeCun,YoshuaBengio,andGeoffreyHinton.“Deeplearn- ing”. In:Nature 521.7553 (May 2015), pp. 436–444.issn: 1476-

work page 2015
[5]

Deep learning,

doi: 10.1038/nature14539. [VFJ15] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. “Pointer networks”. In:Advances in neural information processing systems 28 (2015). [Ben+10] Pascal Benchimol et al. “Improving the Held and Karp Ap- proach with Constraint Programming”. In:Integration of AI and OR Techniques in Constraint Programming for Combinatorial O...

work page doi:10.1038/nature14539 2015

[1] [1]

An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227, 2019

[BLP21] YoshuaBengio,AndreaLodi,andAntoineProuvost.“Machine learningforcombinatorialoptimization:Amethodologicaltour d’horizon”. In:European Journal of Operational Research290.2 (2021), pp. 405–421.issn: 0377-2217. doi: 10 . 1016 / j . ejor . 2020.07.063. [JLB19] Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. “An EfficientGraphConvolutionalNetwor...

work page arXiv 2021

[2] [2]

Learning to Branch in Mixed Integer Pro- gramming

[Kha+16] Elias Khalil et al. “Learning to Branch in Mixed Integer Pro- gramming”.en.In:ProceedingsoftheAAAIConferenceonArtificial Intelligence30.1(Feb.2016).Number:1. issn:2374-3468. doi:

work page 2016

[3] [3]

Neu- ralMachineTranslationbyJointlyLearningtoAlignandTrans- late

1609/aaai.v30i1.10080. url: https://ojs.aaai.org/index. php/AAAI/article/view/10080(visited on 05/27/2024). [BCB15] DzmitryBahdanau,KyunghyunCho,andYoshuaBengio.“Neu- ralMachineTranslationbyJointlyLearningtoAlignandTrans- late”. In:3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proc...

work page 2024

[4] [4]

Deeplearn- ing

[LBH15] YannLeCun,YoshuaBengio,andGeoffreyHinton.“Deeplearn- ing”. In:Nature 521.7553 (May 2015), pp. 436–444.issn: 1476-

work page 2015

[5] [5]

Deep learning,

doi: 10.1038/nature14539. [VFJ15] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. “Pointer networks”. In:Advances in neural information processing systems 28 (2015). [Ben+10] Pascal Benchimol et al. “Improving the Held and Karp Ap- proach with Constraint Programming”. In:Integration of AI and OR Techniques in Constraint Programming for Combinatorial O...

work page doi:10.1038/nature14539 2015