Learning to Select Nodes in Branch and Bound with Sufficient Tree Representation

Thanks for your valuable feedback and suggestions. We will address the issues pointed out in the weakness section in order.

Response to the weaknesses 1:

With the inclusion of leaf nodes, the tripartite graph has a complexity of O(|V|+|C|+|LN|+|E|+|V||LN|), compared to the bipartite graph's O(|V|+|C|+|E|). While this increases the space overhead, the tripartite representation is more space-efficient during node selection. For every candidate leaf node, the bipartite approach requires a complete graph representation, leading to a space complexity of O(∣LN∣(|V|+|C|+|E|)). In problems where the number of constraints is similar to or exceeds the number of variables, such as GISP and MaxSAT, the tripartite graph saves space by avoiding redundant representations of constraints and variables.

We conducted an ablation experiment on the bipartite graph approach and included the results in Appendix E.6 of the revised manuscript. In this study, we used the BestEstimate heuristic to pre-filter candidate nodes and then represented each candidate node with a bipartite graph within our reinforcement learning framework (BRGNN). The training times for the MaxSAT and GISP datasets are listed below. The results indicate that the computational overhead primarily arises from reinforcement learning rather than the tripartite graph itself. Moreover, the tripartite graph representation can save 29.37% and 20.16% of training time on MaxSAT and GISP, respectively.

Training time(s)

Response to the weaknesses 2:

We compared state-of-the-art GNN-based approaches for node selection. Results can be found in Tables 2 and 4. Compared to GNN policy, TRGNN demonstrates notable efficiency improvements across all tested problems, being 26.13% faster in FCMCNF, 5.71% in MaxSAT, 20.29% in GISP, 70.18% in MIK, 10.19% in CORLAT, and 61.06% in Anonymous.

Response to the weaknesses 3:

To address your concern, we have measured and reported the computational time for both graph construction and model inference separately, as these components account for the majority of the additional computational requirements introduced by our method. These times are included in the overall solving time, but we have listed them separately here to highlight the computational overhead of the TRGNN model:

Graph Construction Time(s)

Inference Time(s)

These results show that both the graph construction time and inference time are relatively small compared to the overall solving time, even for larger problem instances.

Response to the weaknesses 4:

To demonstrate the impact of the tripartite graph representation on solving efficiency compared to bipartite graphs, we conducted an ablation study. In this study, we used the BestEstimate heuristic to pre-filter candidate nodes and then represented each candidate node with a bipartite graph within our reinforcement learning framework (BRGNN).

We conducted tests on the GISP and MaxSAT datasets. Experiment shows that the BestEstimate method performs similarly to the default SCIP settings. Our tripartite graph approach (TRGNN) improves over SCIP and BestEstimate. Notably, the tripartite graph method outperforms the bipartite method, achieving improvements of 19.4% on the MaxSAT dataset and 2.5% on the GISP dataset.

The results are as follows:

MaxSAT($n\in[80,100]$)

GISP($n\in[60,70]$)

Thanks for your valuable feedback and suggestions. We will address the issues pointed out in the weakness section in order.

Response to the weaknesses 1:

Our work is indeed more suited to branch-and-bound algorithms rather than branch-and-cut. Based on your valuable suggestion, we tested SCIP with cutting planes and restarts disabled to better evaluate our node selection method within branch-and-bound. The results are included in Appendix E.9 of the revised manuscript.

MaxSAT($n\in[80,100]$)

GISP($n\in[60,70]$)

The results show further improvements for both the GNN and our TRGNN methods compared to SCIP. For example, on MaxSAT, the improvement in solving time for TRGNN over SCIP increases from 7.54% to 12.71%, and on GISP from 13.92% to 18.67%. Additionally, we find that although both BRGNN and TRGNN resulted in more nodes for the GISP problem, the solving time actually decreased. This further validates our observation that simply finding the optimal solution faster, thus excluding other nodes, is not enough to guide efficient node selection.

Response to the weaknesses 2 and question 1:

We acknowledge that for specialized problems, tailored heuristics can achieve superior performance. However, designing optimal heuristics for each class of optimization problems often requires domain-specific expertise and extensive exploration. Our work focuses on enhancing the node selection module within the general framework of MILP solvers, specifically optimizing its performance through learning-based methods.

We believe that comparing our method against SCIP is reasonable, as our work builds upon SCIP’s benchmark framework and demonstrates the potential of learning-based node selection approaches to surpass SCIP in specific problem domains. Nonetheless, we fully agree with your suggestion to evaluate our method on a broader set of tasks to assess its generalization capability. we constructed a dataset that combines multiple problem types, including GISP and MaxSAT, and re-ran the experiments with a single TRGNN model trained across all tasks. The results are as follows:

Times(s)

These findings demonstrate that even with a single trained model across multiple problem types, our approach remains competitive against SCIP. However, we found that when training on a general dataset, the performance is not as strong as training specifically for each problem. We believe your suggestion of using a single model to accommodate all problem types is fascinating, and we plan to explore it further. Achieving this goal involves overcoming several challenges, such as designing a model that can accurately learn problem features to provide suitable node selection strategies within similar problem types, ultimately achieving solving times comparable to those trained on specific problem datasets.

We also revised the experimental description to ensure precision. We now specifically state that our method outperforms other node selection strategies within the branch-and-bound framework, rather than making a general claim about heuristic superiority.

Response to the weaknesses 3:

We have enhanced the figure with a step-by-step description to ensure it is self-contained and more easily understood. We first apply the heuristic algorithm ``BestEstimate'' to pre-select $n$ candidate nodes and incorporate their estimate values into the node features. Subsequently, the TRGNN model processes these features and outputs a Q-value vector, from which the nodes with the highest Q-values are selected as the final choices.

Response to the weaknesses 4:

Thank you for pointing out that our literature review could be improved. We have carefully read these two papers and included descriptions of their methods in the related work section (p3,l122).

Response to the weaknesses 3:

We did not perform comparisons using Gurobi because it is a commercial solver that does not permit external modifications to the node selection module. We chose SCIP because it is an established benchmark solver widely adopted in the field for evaluating the performance of different components within branch-and-bound algorithms, as demonstrated in studies on node [1], variable [2,3], and cut-plane selection [4].

This work specifically focuses on the node selection problem. Although methods based on reinforcement learning have been applied to tasks such as variable selection and cut-plane selection within branch-and-bound algorithms, these components are distinct modules and do not directly relate to one another. The main challenges faced by these problems are unique, and each can be studied independently. For example, variable selection involves only representing the characteristics of a single node to identify the best branching variables, without the need to consider multiple nodes or global tree attributes. Additionally, there are theoretically proven optimal branching strategies, such as strong branching, which can be effectively learned. However, the criteria for node selection remain ambiguous. We believe that making comparisons between these disparate aspects is unnecessary.

[1] Labassi A G, Chételat D, Lodi A. Learning to compare nodes in branch and bound with graph neural networks[J]. Advances in neural information processing systems, 2022, 35: 32000-32010.

[2] Lin J, Meng X U, Xiong Z, et al. CAMBranch: Contrastive Learning with Augmented MILPs for Branching[C]//The Twelfth International Conference on Learning Representations.

[3] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks[J]. Advances in neural information processing systems, 2019, 32.

[4] Wang Z, Li X, Wang J, et al. Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model[C]//The Eleventh International Conference on Learning Representations.

Response to the question 2:

To ensure fair comparisons, we tested a GNN algorithm based on imitation learning with heuristic pre-selection (GNN+BestEstimate) to eliminate the impact of "BestEstimate" on the solving results. The results are included in Appendix E.8 of the revised manuscript. We found that the filtered results were consistent with the original ones because nodes ranked lower by the heuristic "BestEstimate" were seldom chosen by the GNN (see the response to weakness 2).

MaxSAT($n\in[80,100]$)

GISP($n\in[60,70]$)

Thanks for your valuable feedback and suggestions. We will address the issues pointed out in the weakness section in order.

Response to the weaknesses 1 and the question 1:

Complexity: With the inclusion of leaf nodes, the tripartite graph has a complexity of O(|V|+|C|+|LN|+|E|+|V||LN|), compared to the bipartite graph's O(|V|+|C|+|E|). While this increases the space overhead, the tripartite representation is more space-efficient during node selection. For every candidate leaf node, the bipartite approach requires a complete graph representation, leading to a space complexity of O(|LN|(|V|+|C|+|E|)). In problems where the number of constraints is similar to or exceeds the number of variables, such as GISP and MaxSAT, the tripartite graph saves space by avoiding redundant representations of constraints and variables.

We conducted an ablation experiment on the bipartite graph approach and included the results in Appendix E.6 of the revised manuscript. In this study, we used the BestEstimate heuristic to pre-filter candidate nodes and then represented each candidate node with a bipartite graph within our reinforcement learning framework (BRGNN). The training times for the MaxSAT and GISP datasets are listed below. The results indicate that the computational overhead primarily arises from reinforcement learning rather than the tripartite graph itself. Moreover, the tripartite graph representation can save 29.37% and 20.16% of training time on MaxSAT and GISP, respectively.

Training time(s)

We added tests for the average graph construction time, and inference time per instance on the MaxSAT and GISP datasets. Although we acknowledged that reinforcement learning required more time during the training phase compared to imitation learning (IL), it did not add to inference time. Additionally, the tripartite graph approach did not increase additional time overhead compared to the bipartite method.

Graph Construction Time(s)

Inference Time(s)

Advantages of the tripartite representation and contributions of the bipartite graph: The following results demonstrate the advantages of the tripartite graph over the bipartite representation. Experiments show that both TRGNN and BRGNN provide improvements over SCIP. Notably, the tripartite graph method outperforms the bipartite method, achieving improvements of 19.4% on the MaxSAT dataset and 2.5% on the GISP dataset.

MaxSAT($n\in[80,100]$)

GISP($n\in[60,70]$)

Response to the weaknesses 2:

Time complexity of this heuristic algorithm: The heuristic algorithm "BestEstimate" operates efficiently, requiring less than $1×10^{−5}$ seconds per instance on GISP and less than $1×10^{−3}$ seconds on MaxSAT.

Impact of the heuristic algorithm: In our work, we initially use the heuristic algorithm "BestEstimate" to pre-select a fixed candidate set of size n. To determine the potential impact of the heuristic algorithm on solution quality, we increased n from 5 to 10. We recorded the position of the nodes selected by our TRGNN within the rankings provided by the heuristic. These results are visualized in histograms included in Appendix E.7.

The results show that in MaxSAT and GISP, nodes ranked higher than 5 by BestEstimate are never chosen by TRGNN. This indicates that nodes not ranked among the top by "BestEstimate" have a very low probability of being selected. This is because BestEstimate primarily relies on the node estimate value which represents an optimistic prediction of the best feasible solution that can be found within the subtree of that node. Nodes ranked toward the end generally have poorer estimates, indicating a smaller probability of leading to optimal solutions.

Thanks for your valuable feedback and suggestions. We will address the issues pointed out in the weakness section in order.

Response to the weaknesses 1:

The leaf node vertices represent candidate leaf nodes for selection strategies within the branch-and-bound tree. Once a node is selected, the branch-and-bound algorithm splits it into two new leaf nodes by adding constraints of the form $\{x_i\leq z\}$ or $\{x_i\geq z\}$, where $x_i$ is the variable chosen for branching and $z\in \mathbb{Z}$. The LN set is constructed from these leaf node vertices. We included these descriptions in the revised manuscript(p5,l223).

Response to the weaknesses 2:

We added an explanation of the conversion on page 5, line 250 of the revised manuscript: The conversion begins with the root node, where variables and constraints are represented as "variable vertices" and "constraint vertices", respectively. As the branching process progresses, each step adds new constraints to the leaf nodes, encapsulated as "leaf node vertices" in the graph. These additional constraints differentiate each leaf node's MILP problem from the root node's problem. Edges connect these leaf node vertices to variable vertices, forming a path that represents the sequence of branching decisions made from the root node to each leaf node. For example, in Figure 1, the candidate leaf node in the lower left undergoes two branching steps, adding constraints $y\leq 1$ and $x\leq 1$, represented by edges $e_1$ and $e_3$, respectively.

Response to the question:

We added additional experiments to evaluate the effectiveness of directly using the heuristic "BestEstimate". To demonstrate the impact of the tripartite graph representation on solving efficiency compared to bipartite graphs, we conducted an ablation study. In this study, we used the BestEstimate heuristic to pre-filter candidate nodes and then represented each candidate node with a bipartite graph within our reinforcement learning framework (BRGNN). The results are as follows:

MaxSAT($n\in[80,100]$)

GISP($n\in[60,70]$)

Experiment shows that the "BestEstimate" method performs similarly to the default SCIP settings. Our tripartite graph approach (TRGNN) improves over SCIP and "BestEstimate". Notably, the tripartite graph method outperforms the bipartite method, achieving improvements of 19.4% on the MaxSAT dataset and 2.5% on the GISP dataset. We included the results in Appendix E.6 of the revised manuscript.