Towards Better Branching Policies: Leveraging the Sequential Nature of Branch-and-Bound Tree

First, we appreciate you for highlighting the strengths of our paper: incorporating the sequential nature of B&B, the introduction of the linear-complexity Mamba architecture, the detailed description of sequence modeling and contrastive learning along with ablation studies, as well as your recognition of the superior performance of our method on different datasets. Next, please allow us to address the weaknesses and questions you raised one by one.

Response to Weaknesses 1 and Question 4: Missing Ablation of T-BranT-p

In the original paper (line 284), it is explained that T-BranT must use relpscost at the root node once to obtain historical information. Therefore, there is no purely neural network-based T-BranT-p unless their algorithm design is modified (i.e., their source code needs to be changed). However, we have still attempted this approach, and the results are as follows.

Table 1: Comparison between Mamba-Branching-p and T-BranT-p on MILP-S. This table serves as a supplement to the ablation experiments. Here, "-p" denotes the pure neural network method without relpscost initialization.

As can be observed, T-BranT-p performs worse than Mamba-Branching-p.

Response to Weakness 2 and Question 5: Incomplete Ablations -- Standard Sequence Modeling and Effect of Positional Encodings

Thank you for your suggestion! We have already included other sequence modeling approach -- Transformer-Branching-p -- in our ablation study. Additionally, since positional encoding is a natural component in sequence models, it was initially overlooked in our ablation experiments. However, we are happy to provide further ablation results, including:

1. Testing GRU as an alternative sequence model, named GRU-Branching-p (-p denotes pure neural network), in addition to Transformer.
2. Results from Mamba-Branching-p with positional encoding removed, named Mamba-Branching-p (w/o pe).

The corresponding results are presented in the table below.

Table 2: Supplementary ablation experiments on MILP-S. All methods adopt pure neural networks without relpscost initialization. Among them, the method using Transformer as the sequence model has been provided in the original paper, and we further supplement the method using GRU as the sequence model. Meanwhile, the results without positional encoding (w/o pe) in Mamba-Branching-p is also presented.

From Table 2, it can be observed that Mamba demonstrates superior performance as a sequence model in the branching policy compared to both Transformer and GRU. Additionally, the performance of Mamba-Branching degrades when positional encoding is removed, which confirms the importance of positional encoding.

Response to weakness 3: No Comparison with “Exact Combinatorial Optimization with Temporo-Attentional Graph Neural Networks”

Thank you very much for pointing out this paper! We acknowledge that there is some similarity between their work and ours. However, their approach primarily focuses on graph structures and graph neural networks (GNNs). Relying on graph structures inherently limits generalization capability, as it is only applicable to scenarios involving repeatedly solving similar problems. In contrast, Mamba-Branching is designed to handle arbitrary heterogeneous problems, which represents a key distinction.

For further discussion, please refer to our responses to Reviewer 3WGQ, specifically the section titled "Response to weakness 4: Why do we not use Ecole-Generated Instances nor compare with other baselines?":

Response to weakness 4: Suitable for Certain MILPs

While our method does not universally outperform relpscost, it demonstrates superior performance on real-world complex problems. Compared to simpler cases, these complex problems better reflect practical application scenarios and offer higher utility value.

Response to Question 1: Notation Clarification

The notation $o_t$ refers to the set of outputs at an arbitrary branching step t, while $o_T$ specifically denotes the set of outputs at the final branching step T. A more rigorous formulation would be: $\forall t \in\{0,1,...,T\}$.

Response to Question 2: Proof of Proposition

Regarding Proposition 1, we will provide explanations from two perspectives: first, an intuitive explanation from the conceptual standpoint; second, an attempt to provide an explanation using mathematical formulations.

First, we make the following two assumptions, which will serve as the foundation for our subsequent analysis:

1. The feature embeddings of the optimal branch decision variable ($e_t^a$) can be distinguished from those of other branch variables ($e_t^i, \forall i\in \mathcal{C}_t, i\neq a$) in the vector space.
2. The feature embedding $e_t$ is informative for branch decision-making.

Intuitive Explanation

Based on assumption 1, we establish an anchor point $e_t^m$ and employ contrastive learning to train the model such that: (1) the optimal branch variable's feature $e_t^a$ is pulled closer to $e_t^m$, while (2) other variables' features are pushed away from $e_t^m$. This approach amplifies the separation between optimal and non-optimal features, thereby ensuring sufficient distinguishability when these features are subsequently processed by the Mamba architecture.

Mathematical Formulations

For each branching variable $i$, we define $F(i)$ as the branching score function (in this paper, the relpscost score) for variable $i$, such that the optimal branching variable satisfies $a = \arg\max_{i} F(i).$

Assumption 2 posits that the embeddings can encode branching quality information, which we simplify to a linear relationship $e_t^i = \alpha F(i) + \epsilon_i,$where $\alpha \in \mathbb{R}^d$ is a variable independent vector representing the quality-sensitive direction in the embedding space. $\epsilon_i \in \mathbb{R}^d$​ is a noise term satisfying $\mathbb{E}(\epsilon_i)=0$ with small magnitude $|\epsilon_i|$.

We use max pooling over the embeddings as the anchor point, defined as:

=[...,\max_i (F(i)\alpha(j)+\epsilon_i(j)),...].$$ For $e_t^a$, we have: $$e_t^a=[...,\max_i F(i)\alpha(j) + \epsilon_a(j),...].$$ Indeed, if we assume that all $\epsilon_i$ terms are sufficiently similar in magnitude, we can derive the approximation $e_t^a \approx e_t^m$. Therefore, we can reasonably establish that $$\forall i \neq a,\text{sim}(e_t^a, e_t^m) > \text{sim}(e_t^i, e_t^m).$$ This formulation is mathematically **equivalent** to the expression presented in the original paper. $$\forall t, \exists \delta > 0 \text{ s.t. } \text{sim}(e_t^a, e_t^m) \geq \max_{i \neq a} \text{sim}(e_t^i, e_t^m) + \delta$$ Certainly, we acknowledge that the proof involves certain assumptions and approximations, which may lack full mathematical rigor. Additionally, during the neural network training process under contrastive loss, we cannot strictly guarantee that $\delta>0$ holds completely. However, we believe these results effectively **reflect the underlying intuition** behind our design: to make the optimal variable's features closer to the anchor point while pushing other features farther away, thereby making the optimal variable's features more **distinctive** in the vector space. > ### Response to Question 3: Inconsistent Baseline Performance In the original paper's Table 1, the results were obtained on the MILP-S dataset, which **differs from the dataset used in the original T-BranT paper (their dataset was more aligned with MILP-L)**. The MILP-S contains only **8** test cases and serves merely as a toy dataset for preliminary validation. On the **MILP-L** dataset, T-BranT outperforms TreeGate on both the **57** easy instances and **16** hard instances (see Table 2 at line 297 in our original paper). These results are **not contradictory** to those reported in the original T-BranT paper. > ### Response to limitation 1: Two Specific MILP Test Sets In fact, the number of test instances in our dataset **already exceeds** that of previous works (we have 57 + 16 = 73, while TreeGate [1] has 8 and T-BranT [2] has 66), which already demonstrates stronger generalizability. For more information, Please refer to the **Response to Weakness 1 to Reviewer KMMV: Insufficient experimental scale and lack of statistical significance analysis**. > ### Response to limitation 2: Potential of RL-based Methods Please refer to the following responses for **Reviewer 3WGQ, "Response to Weakness 2: Optimization Process vs. Supervised Imitation"**. To summarize, due to challenges such as sparse rewards and credit assignment, to the best of our knowledge, **RL paradigms have not yet surpassed imitation learning for branching policies**. > ### Reference [1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021. [2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

First of all, we appreciate your recognition of our work, including addressing a significant gap in neural branching research, robust performance on large, heterogeneous MILP instances, and the paper being well-written and well-structured. Below, please allow us to respond to all your points regarding weaknesses and questions.

Response to Weakness 1: Statistical Significance Testing

Thank you for your valuable suggestions! We have supplemented detailed statistical analyses in the "Response to Weakness 1" section for reviewer KMMV, including significance tests and other statistical results.

For the significance test, we employed the Friedman test with Conover post-hoc analysis, which is a significance test method similar to the Wilcoxon signed-rank test. However, it is more suitable for our scenario involving more than two methods.

Response to Weakness 2: Whether It Benefits from Hardware Acceleration

Thank you for your valuable suggestions! The key concerns you have raised is "Can the results be maintained on devices less powerful than A100 (or even on CPUs)?"

We have provided experimental results on RTX 4090, as shown in the following table:

Table 1: Supplementary results obtained on the RTX 4090 device. The experimental results are the geometric mean of the primal-dual integrals for 16 difficult instances in MILP-L. Compared with previous experiments, no changes were made to the code other than the replacement of hardware equipment. Relpscost was also re-run on the new equipment to ensure a fair comparison.

It can be seen that Mamba-Branching still maintains its advantages even on GPU that is inferior to the A100. Although the RTX 4090 is still a good GPU, due to constraints on our available equipment, we have been unable to obtain a less powerful GPU for further experiments.

Meanwhile, we attempted to run Mamba-Branching on a CPU, but in the mamba_ssm library (the official code repository provided by the authors of Mamba), the selective_scan_cuda function requires execution on a GPU and cannot run in a pure CPU environment. Therefore, we were unable to test the performance in a pure CPU environment within a short period of time. Furthermore, we emphasize that branch policies maintaining efficiency in pure CPU environments are indeed a widely discussed direction [1,2,3], but this is not the focus of our work.

Response to Weakness 3: Motivation for Using a Contrastive Loss

Regarding the motivation for using the contrastive loss, we have provided a detailed explanation in the "Response to Question 2" section for Reviewer TcMy. Due to space constraints, we briefly restate its core idea here: we explain it from an intuitive perspective and use mathematical formulas to elaborate why local-global mutual information should be maximized.

First, we make the following two assumptions:

1. The feature embeddings of the optimal branch decision variable can be distinguished from those of other branch variables in the vector space.
2. The feature embedding $e_t$ is informative for branch decision-making.

Intuitive Explanation

Based on assumption 1, we establish an anchor point $e_t^m$ and employ contrastive learning to train the model such that: (1) the optimal branch variable's feature $e_t^a$ is pulled closer to $e_t^m$, while (2) other variables' features are pushed away from $e_t^m$. This approach amplifies the separation between optimal and non-optimal features, thereby ensuring sufficient distinguishability when these features are subsequently processed by Mamba.

Mathematical Formulations

For each branching variable $i$, we define $F(i)$ as the branching score function for variable $i$, such that the optimal branching variable satisfies $a = \arg\max_{i} F(i).$

Assumption 2 posits that the embeddings can encode branching quality information, which we simplify to a linear relationship $e_t^i = \alpha F(i) + \epsilon_i,$where $\alpha \in \mathbb{R}^d$ is a variable independent vector. $\epsilon_i \in \mathbb{R}^d$​ is a noise term satisfying $\mathbb{E}(\epsilon_i)=0$ with $|\epsilon_i| \approx 0$.

We use max pooling over the embeddings as the anchor:

=[...,\max_i (F(i)\alpha(j)+\epsilon_i(j)),...].$$ For $e_t^a$, we have: $$e_t^a=[...,\max_i F(i)\alpha(j) + \epsilon_a(j),...].$$ Indeed, we can derive the approximation $e_t^a \approx e_t^m$, then reasonably establish that: $$\forall i \neq a,\text{sim}(e_t^a, e_t^m) > \text{sim}(e_t^i, e_t^m).$$ This formulation is mathematically equivalent to the expression presented in the original paper. > ### Response to Weakness 4: Connection to Established Contrastive Learning Methods We acknowledge that our research is indeed not strongly related to CLIP and is actually more similar to DGI. However, rather than a strict extension of CLIP, we merely drew **inspiration** from contrastive learning methods like CLIP. We will add DGI to the introduction (alongside CLIP) in the revised paper to highlight these as our inspirational sources. > ### Response to Weakness 5 and Question 2: A Simpler Pretraining Strategies Thank you for your suggestions. You have indeed proposed an idea that is more intuitive, natural, and simpler compared to contrastive learning: _attaching a linear classification head to predict the best branching feature, training it until convergence, and then discarding the head_. Unfortunately, in our work, we adopted this approach **from the very beginning** but found that **its performance was unsatisfactory**. Subsequently, we further reflected and attributed the poor performance to the **insufficient discriminative power** of the embedding features of each variable. Therefore, we further designed a contrastive learning method to address this issue. We are happy to provide the results of the training conducted using your proposed approach, named **Mamba-Branching-classifier**. Specifically, we first trained a TreeGate network, discarded its linear classification head (retaining only the embedding feature output), and then trained it jointly with Mamba. | | Mamba-Branching | Mamba-Branching-classifier | TreeGate | |------------|-----------------|----------------------------|----------| | Nodes | 2054.99 | 3353.60 | 2171.31 | | Fair Nodes | 2077.55 | 3420.68 | 2205.06 | Table 2: Validation of the approach "training a linear classifier on labels and discarding it", named Mamba-Branching-classifier. The experiments are conducted on MILP-S. Compared to Mamba-Branching, Mamba-Branching-classifier **merely** replaces the contrastive loss with the aforementioned method. From this set of results, Mamba-Branching significantly outperforms Mamba-Branching-classifier, and the latter fails to surpass TreeGate, which demonstrates the **importance of contrastive learning**. > ### Response to Question 1: Performance on Less Powerful Hardware and Per-Instance Comparisons > #### Performance on Less Powerful Hardware We fully understand your concerns and have provided results on less powerful hardware in **"Response to Weakness 2"**. It is important to emphasize that our method benefits from GPU acceleration but is **not entirely attributed to** it. We believe that this series of machine learning-based methods all attributed to **data-driven characteristics**; thus, [1, 2, 3] achieve high performance on CPUs, yet this is **not the focus of our work**. > #### Per-instance comparison We are pleased to provide the results for each hard instance in MILP-L as follows: | | Mamba-Branching | relpscost | | ------------------------ | --------------- | ------------- | | atlanta-ip | 24258.31 | **24170.83** | | bab2 | **38080.78** | 42185.32 | | bab5 | 3294.13 | **2881.17** | | bab6 | **20686.83** | 22492.31 | | harp2 | **44.92** | 76.33 | | map16715-04 | 65686.53 | **59963.96** | | msc98-ip | **1322.72** | 1530.67 | | mspp16 | 37661.03 | **35465.03** | | n3seq24 | **7145.50** | 7836.84 | | neos-4338804-snowy | **5880.37** | 5880.46 | | neos-4387871-tavua | **67630.53** | 72370.35 | | neos-4647030-tutaki | **2463.27** | 2484.55 | | nursesched-medium-hint03 | 115857.37 | **114998.07** | | opm2-z10-s4 | **107706.76** | 112561.74 | | pigeon-10 | 36003.53 | **36003.52** | | radiationm40-10-02 | **597.08** | 624.90 | Table 3: Comparison of primal-dual integral between Mamba-Branching and relpscost on 16 hard instances in MILP-L. For each instance, the geometric mean of the results across 5 seeds is calculated. Of **16** instances, Mamba-Branching leads in **10** compared to relpscost. This is similar to the win/tie/loss table in **"Response to Weakness 1" by Reviewer KMMV**, except that the median of each instance is replaced with the geometric mean, further enriching the experimental results. > ### Reference [1] Gupta, Prateek, et al. "Hybrid models for learning to branch." _Advances in neural information processing systems_ 33 (2020): 18087-18097. [2] Kuang, Yufei, et al. "Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework." _The Twelfth International Conference on Learning Representations_. 2024. [3] Kuang, Yufei, et al. "Towards general algorithm discovery for combinatorial optimization: Learning symbolic branching policy from bipartite graph." _Forty-first International Conference on Machine Learning_. 2024.

Thank you very much for your valuable suggestions and the effort you have put into reviewing our paper! The questions you raised have provided us with excellent insights and have helped make our work more comprehensive. Regarding the two remaining points of confusion, we fully understand your perspective, and we would like to supplement the following:

Response to Q1: Motivation of the Contrastive Loss

First of all, we fully acknowledge that you are absolutely right: indeed, the standard supervised learning loss is also intuitively reasonable. We admit that we cannot provide a rigorous mathematical proof through more detailed theoretical analysis to demonstrate the advantage of contrastive loss over supervised learning loss.

However, our experimental results validate that contrastive loss achieves better performance than supervised learning loss -- in fact, the method based on supervised learning loss even fail to surpass the baselines.

Your suggestion is truly insightful: a more detailed theoretical analysis behind these experimental results presents a challenging yet promising new direction. For now, what we can do is to demonstrate the superiority of contrastive loss through experimental evidence.

Response to Q2: Performance Improvement is not Statistically Significant

We fully agree with your observation that while the statistical results demonstrate Mamba-Branching's superiority over relpscost, the advantage does not reach statistical significance. We would like to highlight that our method represents meaningful progress compared to previous baselines [1,2] -- whereas existing baselines fail to outperform relpscost in any scenario, our approach achieves superior performance on the most practically relevant and challenging real-world problems.

Your expectation is indeed insightful -- achieving statistically significant improvements over relpscost remains an important goal for future work in this field. At present, Mamba-Branching's demonstrated capability is to significantly outperform other baselines while also surpassing relpscost.

Acknowledgement

We sincerely appreciate your valuable contributions to our work! Your insightful comments have provided us with unique perspectives that have significantly helped improve our paper.

Reference

[1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

First, we appreciate your recognition of the strengths of our work, including the clarity of the paper writing, the well-defined motivation, the novel and insightful Mamba sequence modeling, and the effective contrastive learning pre-training, as well as your acknowledgment of the high efficiency in solving difficult problems. Next, let me address your points regarding weaknesses and the questions raised.

Response to Weaknesses 1 and 2

Weakness 1: Evaluation metrics for easy instances, nodes or time?

First, we sincerely thank you for valuable feedback. In this field that emphasizes the generalization of branching policies, the two prior works [1, 2] evaluated easy instances using only nodes and fair nodes as metrics. This is because solving time is influenced not only by the node count (fewer nodes generally lead to fewer simplex iterations) but also by the neural network’s inference time, which can vary significantly across hardware devices. Thus, while we included solving time in our experiments for reference, we emphasize that a completely fair comparison is challenging due to potential discrepancies in hardware environments across methods.

Weaknesses 2: No advantage in solve time over baselines.

However, we are happy to provide the solving time results as follows.

table 1: The solving time results for several competitive methods on MILP-S (8 instances) and easy instances in MILP-L (57 instances). Here, "-p" indicates the pure use of neural networks. It should be noted that, except for the results of TreeGate and T-BranT under MILP-L, which are supplemented in the table here, all other results can be found in the result logs.

We acknowledge that among the three MILP-S groups initialized with a single relpscost (TreeGate, T-BranT, Mamba-Branching), TreeGate has a slight advantage (111.17 vs. Mamba-Branching's 112.32). However, after excluding relpscost initialization (TreeGate-p vs. Mamba-Branching-p), Mamba-Branching-p (147.96) is faster than TreeGate-p (163.39). Furthermore, for the easy instances in MILP-L, Mamba-Branching (123.79) achieves the fastest solving time among all neural branching policies. Compared with the 8 instances in MILP-S, the 57 instances in MILP-L are more convincing.

The reasons for these observations can be summarized as follows:

• Architectural Complexity: Mamba-Branching's inherently more complex network structure leads to longer inference times, explaining why TreeGate can sometimes achieve shorter solving times despite exploring more nodes.
• Scalability Advantage: For MILP-L with more test instances (57 vs. 8), Mamba-Branching's superior node efficiency offsets its higher computational overhead, resulting in better overall solving performance.
• Initialization Impact: The impact of initialization may also lead to unfair comparison, as factors other than the performance of the neural network are involved. After excluding relpscost initialization, Mamba-Branching-p consistently demonstrates faster solving times.

In summary, the statement that "No advantage in solve time over baselines, Mamba-Branching does not outperform the TreeGate baseline in terms of actual solving time" requires clarification: While TreeGate is marginally faster on one specific MILP-S (8 test instances), Mamba-Branching demonstrates significantly better performance on MILP-L easy instances (57 test instances), which better represents its practical effectiveness.

Response to Q1: Evaluation Based on Solving Time

In our responses to Weakness 1 and Weakness 2, we have provided solving time results and corresponding analyses. The results demonstrate that while Mamba-Branching performs slightly worse than TreeGate on MILP-S, it outperforms TreeGate on more test instances (easy instances of MILP-L) and surpasses TreeGate in pure neural network tests where the influence of relpscost is excluded. The reasons for these observations have been thoroughly analyzed in the aforementioned responses.

We would like to emphasize that all neural branching policies are indeed slower than relpscost due to the substantial gap in node counts on easy instances -- this is an undeniable fact. However, it should be noted that neither TreeGate nor T-BranT surpass relpscost in any scenario, whereas Mamba-Branching achieves superior performance over relpscost on hard instances of MILP-L. Furthermore, Section 5.2.3 of our original paper provides a detailed analysis of the underlying reasons for this phenomenon. In fact, the strong branching initialization of relpscost is particularly time-consuming for complex problems, which makes it lose its advantages in difficult scenarios and perform worse than Mamba-Branching. A more comprehensive comparison and analysis between neural branching policies and relpscost will be presented in our response to Q2.

Response to Q2: Machine Learning Cannot Surpass Expert Strategy Relpcost

I fully understand your concern regarding TreeGate, T-BranT, and Mamba-Branching not surpassing relpscost on easy instances. Let me address this from two perspectives: first, the original explanations provided by TreeGate and T-BranT regarding this matter, and second, the advantages of our Mamba-Branching compared to relpscost as presented in our work.

Original Explanations of TreeGate and T-BranT

• TreeGate's original paper states "While we train our BVS policies to imitate the SCIP default policy relpscost, our objective is not to outperform relpscost. Indeed, expert BVS policies like relpscost are tuned over thousands of solvers' proprietary instances: comprehensively improving on them is a very hard task, impossible to guarantee in our purely-research experimental setting, and should thus not be the only yardstick to determine the validity (and practicality) of a learned policy."
• Similarly, T-BranT explains "In fact, as implemented in the SCIP solver, branching with relpscost will trigger side-effects that modify the internal SCIP states and facilitate the following branching processes. And it is hard to re-implement a pure version of relpscost with its peculiarities retained. Thus, we do not judge our models by whether they can surpass relpscost as Zarpellon et al. [1] do."

As evident, both papers provide clear explanations for why direct comparison with relpscost may not be necessary or appropriate.

Advantages of Mamba-Branching Compared to relpscost

Compared to TreeGate and T-BranT, Mamba-Branching has already demonstrated the potential to surpass relpscost, outperforming it on difficult problems in MILP-L. In my opinion, the fundamental reason lies in the fact that complex problems involve a larger number of variables, making the strong branching initialization process of relpscost excessively time-consuming. As a result, relpscost loses its advantage on large-scale problems. While Mamba-Branching may not perform as well as relpscost on simpler problems, its superior capability on more realistic and practically valuable complex problems should not be overlooked.

Response to Q3: Suggestions for Strengthening the Work

We sincerely appreciate your valuable suggestions, which reflect your profound understanding of the field. As you aptly noted, GCNN shows poor generalization on heterogeneous problems -- this is precisely what motivated our adoption of the TreeGate feature + relpscost. Regarding your comments on the TreeGate feature + relpscost expert, we would like to elaborate on the advantages of this paradigm over GCNN + strong branching.

1. As noted in [1], relpscost represents a more practical expert since strong branching is rarely used directly in real-world problem solving. This provides significant benefits during dataset collection -- the time required for gathering relpscost data is substantially less than for strong branching. While we cannot provide exact quantitative comparisons (as this wasn't our paper's focus), empirical evidence shows strong branching becomes prohibitively slow for complex problems, whereas relpscost remains computationally efficient.
2. As you mentioned, TreeGate effectively addresses the generalization issue. They emphasize incorporating tree-search-related features into the design without focusing on specific instances, while pseudo-costs align with the requirements of tree search by leveraging historical information. Therefore, they integrate a substantial number of pseudo-costs into the features (SCIPgetAvgPseudocostScore).
3. Relpscost essentially represents an improved form of pseudo-cost that incorporates historical strong branching experience. The features capture "imperfect" pseudo-costs while the relpscost labels contain "refined" pseudo-costs. The neural network learns to transform pseudo-costs from imperfect to refined versions -- this represents meaningful learning rather than overfitting as suggested.

In summary, we believe the TreeGate feature design combined with relpscost expert represents a necessary choice to achieve generalization capability, while maintaining dataset collection efficiency.

Reference

[1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

We sincerely appreciate your feedback! We are more than happy to continue discussing the issues you raised -- although we would like to first clarify that your questions are not actually directed at our work, but rather challenge certain aspects of previous research in this field[1,2] -- nevertheless, we are very willing to address your questions.

Response to 1,2,3: Strong Branching or Relpscost? Further Comparative Experiments

We thank you for raising this insightful experiment! To maintain the generalization capability of the branching policy (this is a fundamental premise of our work, as we aim to focus specifically on generalization performance), we adopted the same feature design and network architecture as TreeGate [1]. Under this framework, we trained policies using both strong branching and relpscost as experts, with results below:

Table 1: The imitation learning results using TreeGate as the network framework, with strong branching and relpscost serving as the experts respectively. The training was conducted for 50 epochs in all cases. The table reports the final network's loss and accuracy on both the training and test sets, as well as the solving time performance on test instances from MILP-S.

The results demonstrate that under the TreeGate framework, imitating strong branching achieves significantly lower accuracy compared to imitating relpscost, making training considerably more difficult. Meanwhile, on test instances, the policy imitating relpscost shows clearly superior performance, having learned meaningful decision-making patterns.

As you mentioned, the purpose of imitation learning is:
"To approximate a powerful but slow expert (e.g., strong branching) in order to achieve faster solving time with a learned policy. This is what the GCNN paper does—they use strong branching as the expert, then train a neural network that imitates it efficiently."

We agree that strong branching is a powerful expert in contexts like GCNN. However, our experiments under TreeGate's feature design reveal that relpscost is a more suitable expert for learning generalizable policies, likely due to TreeGate's generalization-oriented feature design, which exhibits better compatibility and alignment with relpscost.

Therefore, under the current feature design, imitating relpscost demonstrates more effective learning compared to imitating strong branching. While modifying the feature design or network architecture (e.g., abandoning TreeGate’s framework) could be an alternative approach, we note that:

1. Our paper’s primary contribution lies in Mamba-based sequential modeling and contrastive learning, rather than in re-evaluating the feature design choices of prior methods. Indeed, if we abandon TreeGate's generalization-oriented feature design, how to develop features that are both compatible with strong branching and maintain generalization capability presents a highly challenging new research direction. We must acknowledge your remarkable insightfulness -- this new research direction is indeed what you anticipated to see. However, unfortunately, this lies entirely outside the scope of our current research focus.
2. These comparative experiments are intended to analyze TreeGate’s behavior under different experts, rather than to serve as an ablation study for our proposed method.

We appreciate the reviewer’s perspective and are happy to further discuss these trade-offs if needed.

Reference

[1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

We appreciate the opportunity to clarify this important point. As previously mentioned in our response, we have consistently maintained that solving time is determined by both the number of nodes explored and the inference time of neural networks (or other). As noted in our original submission:

"The solving time is influenced not only by node count (where fewer nodes typically reduce simplex iterations) but also by the neural network's inference time."

To be precise, our claim means fewer nodes generally lead to reduced simplex iterations, rather than asserting that the number of nodes is the sole determinant of solving time. This distinction is crucial.

The observed phenomenon that relpscost explores fewer nodes than GCNN yet requires longer solution time can be attributed to the computational overhead of its strong branching in early stages. This finding is consistent with our explanation: the strong branching employed by relpscost in early stages leads to prolonged inference time. Although it results in fewer nodes explored (and consequently fewer simplex iterations), the disadvantage in inference time ultimately causes relpscost to be slower than GCNN in overall solution time. This serves as compelling evidence of how these two factors jointly influence the solving time.

Moreover, for the same reason, the strong branching initialization of relpscost proves excessively time-consuming on complex problems, which explains why Mamba-Branching outperforms relpscost in such scenarios.

And as you requested, we have carefully conducted additional experiments evaluating solving time performance. The results consistently demonstrate Mamba-Branching's advantages over baseline methods, validating our contributions.

Thank you for your response! The discussion has been highly beneficial to me. It is evident that you possess profound understanding and unique insights in this field, and I truly cherish this valuable opportunity to exchange ideas with you.

I fully acknowledge your perspective on our work: it is undeniable that we proposed a new neural network/method. Compared to those works that have made exceptionally outstanding contributions, we must admit that our contribution is relatively modest. However, please allow me to provide some additional clarification regarding our work.

Several Pioneering Works

First, this field originated from two seminal papers [1,2]. Both studies designed key features based on critical information in the branch-and-bound and employed machine learning/deep learning to address the variable selection problem. As you rightly pointed out, these works made highly pioneering contributions to the field -- they required not only an in-depth understanding of MILP solvers to design those crucial features but also a profound grasp of neural network techniques to develop specialized architectures.

Following the same reason, I personally believe that TreeGate [3] is also a pioneering work. They proposed a generalizable branching policy from two perspectives: MILP-knowledge-based feature design and new neural network architecture. However, as you rightly pointed out, their work remains controversial -- they were unable to surpass relpscost.

Subsequent Related Works -- From the Perspective of Neural Networks and Deep Learning

Many subsequent works have been built upon these pioneering works [1,2,3]. Most of these works have adopted the feature design established by their predecessors, leading to a series of new research directions in branching policies, including but not limited to:

1. New network architectures [4]
2. Updates in training paradigms: Addressing issues in RL-based approaches [5,6]
3. Enhancement or accelerated collection of expert datasets: Improving quality [7,8] or efficiency [9] of data acquisition
4. Hardware-friendly branching policies: CPU-based rather than GPU-based implementations [10,11,12]

The examples we've listed likely represent just the tip of the iceberg, and these works have all been published at top-tier conferences in the neural network community (including, of course, NeurIPS). We wish to emphasize that all these approaches examine the problem from a neural network perspective, solving MILP problems through deep learning methodologies. Compared to the pioneering works, they did not propose new feature designs based on novel MILP insights.

Clarification of Contributions

We would like to reiterate that, compared to TreeGate and T-BranT, we have achieved meaningful progress. While TreeGate and T-BranT fail to surpass relpscost in all scenarios, our method demonstrates superior performance on complex and meaningful instances where relpscost does not hold a significant advantage. This addresses your concern: "Why not just use relpscost directly?" In particularly challenging instances where relpscost itself struggles, Mamba-Branching may indeed be worth considering.

We fully acknowledge that, compared to the pioneering works in this field, our contribution is more incremental. Our work primarily introduces a new neural network/method from the perspective of the deep learning and neural network community to improve branching policies, without making groundbreaking advances from the MILP community’s standpoint. However, many recent papers in this area -- published at top-tier machine learning/deep learning conferences (including but certainly not limited to [4–12]) -- have similarly focused on enhancing branching policies purely from a deep learning perspective.

We completely respect your viewpoint: NeurIPS is one of the premier conferences for deep learning, and given your rigorous academic standards and responsibilities as a reviewer, you believe that pioneering works are more suitable for NeurIPS. This is entirely reasonable -- academic discourse naturally invites diverse perspectives ("A thousand readers, a thousand Hamlets"). While we stand by our position, we deeply admire your scholarly rigor.

As you rightly noted, "MILP optimization is inherently more complex than some other domains." We believe our discussion is not a reflection of harsh criticism but rather a productive and profound academic exchange aimed at advancing the field.

Acknowledgments

Finally, we sincerely appreciate the time and effort you have devoted to this discussion. Your insights are thoughtful and deeply informed, and we are grateful for the valuable feedback you have provided to improve our work. Thank you for your contribution to our paper!

Reference

[1] Khalil, Elias, et al. "Learning to branch in mixed integer programming." Proceedings of the AAAI conference on artificial intelligence. Vol. 30. No. 1. 2016.

[2] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in neural information processing systems 32 (2019).

[3] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[4] Ye, Xinyu, et al. "On Designing General and Expressive Quantum Graph Neural Networks with Applications to MILP Instance Representation." The Thirteenth International Conference on Learning Representations (2025).

[5] Scavuzzo, Lara, et al. "Learning to branch with tree mdps." Advances in neural information processing systems 35 (2022): 18514-18526.

[6] Parsonson, Christopher WF, Alexandre Laterre, and Thomas D. Barrett. "Reinforcement learning for branch-and-bound optimisation using retrospective trajectories." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.

[7] Zhang, Changwen, et al. "Towards imitation learning to branch for mip: A hybrid reinforcement learning based sample augmentation approach." The Twelfth International Conference on Learning Representations. 2024.

[8] Gupta, Prateek, et al. "Lookback for Learning to Branch." Transactions on Machine Learning Research.

[9] Lin, Jiacheng, et al. "CAMBranch: Contrastive Learning with Augmented MILPs for Branching." The Twelfth International Conference on Learning Representations (2024).

[10] Gupta, Prateek, et al. "Hybrid models for learning to branch." Advances in neural information processing systems 33 (2020): 18087-18097.

[11] Kuang, Yufei, et al. "Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework." The Twelfth International Conference on Learning Representations. (2024).

[12] Kuang, Yufei, et al. "Towards general algorithm discovery for combinatorial optimization: Learning symbolic branching policy from bipartite graph." Forty-first International Conference on Machine Learning. 2024.

First, we appreciate your recognition of our strengths, including the innovation of our research perspective, the emphasis on the evolution process of the branch-and-bound tree, the practicality tested on real datasets, and the support for open source. Now, please allow me to address your pointed-out weaknesses and questions one by one.

Weakness 1: Insufficient experimental scale and lack of statistical significance analysis.

We sincerely appreciate your feedback! In fact, two prior works in the same field [1, 2] employed 8 and 66 test instances, respectively, whereas our evaluation already includes a larger number of test instances. Moreover, these works also reported results using the geometric mean: given the high variance from inherent variability across test instances, it mitigates outlier impacts better than the arithmetic mean.

To further address your concerns, we would be delighted to provide additional statistical results to demonstrate the statistical properties of our method.

Additional statistical information

Quartile Tables

Table 1: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the quartile table for time. For example, Mamba-Branching achieves the time of 140.33 at the 50%, meaning that 50% of the instances have solving time within 140.33. Meanwhile, the solving time contains difficulty information, and from this table, we can observe the adaptability of the method to problems of varying difficulties.

Table 2: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the quartile table for Node counts. The meaning of this table is similar to that of Table 1, and it can also indicate the adaptability of the method to problems of varying difficulties.

As shown, Mamba-Branching attains the smallest time and node count at the 25th, 50th, and 75th percentiles, indicating consistently superior performance across all difficulty ranges compared to the other two methods. This suggests that Mamba-Branching’s lower geometric mean is not due to exceptional performance on a few extreme instances but rather stems from robust and balanced improvements across the entire benchmark.

The primal-dual integral, which is related to bound values (independent of problem difficulty) and thus does not reflect problem complexity, is not included in our analysis but presented later with other statistical metrics. Additionally, the MILP-S benchmark, with only 8 test instances (too few for statistically rigorous analysis), was excluded from our statistical evaluation.

Win/Tie/Loss Statistics Table

Table 3: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the Win/Loss table for node counts. Since 57 instances are too many to display their results directly, we use the win/tie/loss format to show the median performance (across 5 random seeds) of different methods on various instances when compared pairwise.

Table 4: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the Win/Loss table for time. The meaning of this table is consistent with that of Table 3, both aiming to present the performance comparison of methods on each instance within the limited space.

Table 5: For the hard instances in the MILP-L dataset (16 instances, each with 5 random seeds), the Win/Loss table for primal-dual integral. In our response to Question 1 for Reviewer X7WR, we have also specifically presented the results for each instance.

It can be observed that Mamba-Branching outperforms both TreeGate and T-BranT on both easy and hard instances, while also achieving superior performance over relpscost on difficult instances. This finding aligns with the original conclusions presented in this paper.

Friedman test with Conover post-hoc analysis

1. Friedman test results for nodes (57 easy instances in MILP-L): Test statistic=2.502, p-value=0.2862, indicating no statistically significant differences.
2. Friedman test results for time (57 easy instances in MILP-L): Test statistic=18.000, p-value=0.0001, indicating statistically significant differences. Conover post-hoc analysis can be performed, as shown in Table 6.
3. Friedman test results for primal-dual integral (16 hard instances in MILP-L): Test statistic=8.625, p-value = 0.0347, indicating statistically significant differences. Conover post-hoc analysis can be performed, as shown in Table 7.

Table 6: Conover post-hoc results for time (57 easy instances in MILP-L). The content of the table is p-values; if a p-value is < 0.05, it can be considered that there is a significant difference.

Table 7: Conover post-hoc results for primal-dual integral (16 hard instances in MILP-L). The meaning of this table is consistent with that of Table 6.

The Friedman test with Conover post-hoc analysis is a non-parametric statistical method for comparing multiple methods across multiple instances, especially when data may violate normality assumptions. In fact, this approach is a similar significance test method to the Wilcoxon signed-rank tests suggested by Reviewer X7WR in Weakness 1. However, it is more suitable for our scenario involving more than two methods. Its procedure includes: (1) calculating instance-wise ranks; (2) conducting the Friedman test for overall significance, and if p<0.05; (3) applying Conover's test for detailed comparisons.

On easy instances, in terms of runtime, Mamba-Branching demonstrates statistically significant differences compared to T-BranT (p=0.000014), while showing marginally significant differences with TreeGate (p=0.071287). For hard instances, Mamba-Branching has statistically significant differences vs. both TreeGate (p=0.011501) and T-BranT (p=0.007880), but no significant difference vs. relpscost (p=0.114340) -- here, reference to earlier statistical results is needed. This is reasonable as its performance advantage over relpscost is smaller than over other methods.

Weakness 2: Lack of citation to "Learning to Branch in Mixed Integer Programming"

Thank you for your reminder and suggestions! This paper is the origin of learning to branch, and we will list it as an important work in the related work section.

Question 1: Role of Proposition 1

Regarding this aspect, due to word count constraints, we have provided a detailed explanation in our response to Reviewer TcMy's Question 2: Proof of Proposition.

Question 2: The rationale for choosing relpscost over strong branching as the expert

This hypothesis is entirely derived from [1], where the original text states:

"Our expert branching scheme is SCIP default, relpscost, i.e., a reliability version of hybrid branching in which SB and PC scores are complemented with other ones reflecting the candidates’ role in the search; relpscost is a more realistic expert (nobody uses SB in practice), and the most suited in our context, given the emphasis we put on the search tree."

Regarding why relpscost is adopted as the expert over Strong Branching (SB) in generalization scenarios, as well as relpscost’s advantages over SB in dataset collection, further explanations can be found in the following sections:

1. "Response to Q3" for Reviewer QH4H
2. "Response to Weakness 4: Rationale for Expert Policy Selection" for Reviewer 3WGQ

Reference

[1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

First, thank you for pointing out our strengths, including the clarity of the paper writing and the design of sequence modeling and contrastive learning. Below, we will elaborate on the weaknesses you identified and the questions you raised.

Response to Weakness 1: MDP or POMDP?

We appreciate your feedback! Due to NeurIPS' page limits, we prioritized discussing sequential modeling and contrastive learning, leaving no space for analyzing whether the environment is a fully observable MDP or POMDP.

In fact, the environment is an MDP; however, the performance of sequence-based policies is superior to state-based policies, which has been verified in Decision Transformer (DT) [5]. DT is still based on MDP, but it achieves better results by using historical trajectories as input. More importantly, as pointed out in [1], the B&B environment has a severe long-term credit assignment problem, where the impact of a branching decision may lag until the state many steps later. The original DT paper also emphasizes that their sequence modeling method effectively mitigates the long-term credit assignment problem, which is completely consistent with our approach.

Response to Weakness 2: Generalization Concerns and Optimization Process

We sincerely appreciate your insightful comments! Indeed, both points raised are profound, and we would like to address them individually.

Generalization Concerns

In our work, generalization means the policy can train on certain instances and deploy on completely unseen, heterogeneous ones -- a significant improvement over GCNNs as shown in our results.

This generalization ability benefits from the TreeGate feature design (Zarpellon et al.) and expert selection. TreeGate features are instance-independent, emphasizing the tree search process and thus incorporating numerous pseudocost-related terms. Meanwhile, based on the feature design, more appropriate relpscost is used as the expert. In contrast, GCNNs' features contain substantial instance-specific information, leading to poor generalization.

Optimization Process vs. Supervised Imitation

As highlighted in references [1,2], the RL training process -- a most typical optimization process -- in B&B environments faces several fundamental challenges: including sparse rewards, credit assignment difficulties, and high variance in policy gradients caused by long episodes. To the best of our knowledge, for branching policies, supervised imitation learning remains stronger than other training paradigms in the current state of research.

Response to Weakness 3: Concerns Regarding Token Length

We appreciate your attention to this implementation detail. We would like to clarify that 24 does not represent the token length. As clarified in Section 4.2 (Line 201) of our manuscript, T=24 represents the total number of branching steps considered, while the actual number of tokens processed by Mamba is calculated as: $\sum_{t=0}^T |\mathcal{C}_t| + T$.

For example, satellites1-25 (in MILP-L) has a SCIP solving time of 952.04 seconds, which can be considered a medium-difficulty instance. For this particular case, we conducted experiments where the token count reached 11,624 for t=0~24, which is a considerably large number.

You might argue that considering only the past T=24 historical states and actions is insufficient. However, we justify this choice based on the following two points:

1. For complex problems where $|\mathcal{C}_t|$ is significantly larger, the token count would grow dramatically. You raised a valid concern that T=24 may not fully demonstrate the applicability to complex problems. However, we specifically chose T=24 precisely because complex problems typically involve more candidate variables, and this value represents a carefully considered trade-off.
2. The current state is indeed included in the input sequence. With T=24, our model receives strictly more input information than TreeGate's architecture.

Thus, compared to TreeGate, our method incorporates more comprehensive input information, and T=24 was selected as a necessary trade-off to manage memory consumption effectively.

Response to weakness 4: Ecole Instances, Baselines, Expert Differences, Statistical Data, and Training Volume

We sincerely appreciate your valuable feedback. These comments can be categorized into four key aspects:

1. The use of ecole instances and comparisons with other baselines
2. Differences in expert for imitation learning
3. Insufficient statistical information in the results
4. Concerns regarding the training data volume

We will address each of these points systematically in the following response.

Why do we not use Ecole-Generated Instances nor compare with other baselines?

Previous methods[1,2,3] often use Ecole-generated instances for homogeneous problems -- generating small-scale instances (randomized parameters) for training/testing and larger-scale instances for transferability evaluation, with Strong Branching as the expert to train GCNNs. Ecole here mainly serves to generate diverse instances of the same problem.

In contrast, our training instances for MILP-S come from 19 distinct problems, with expert data collected via relpscost, and test problems are entirely different from these 19. This is because Zarpellon et al.'s method (TreeGate) ensures the ability to handle heterogeneous MILPs through network and feature design, which GCNNs fundamentally lack due to their problem-specific feature design.

Thus, TreeGate and GCNN are applied in completely different scenarios: TreeGate focuses on solving unknown heterogeneous problems, while GCNN targets the same type of problem. Hence, using Ecole-generated instances as test instances would be meaningless for our evaluation.

As clarified earlier, the papers you cited [1,2,3] all use GCNNs as their network architecture and do not aim for generalization. Our network architecture, following TreeGate, is fundamentally different. Nevertheless, we did include results from [3], which performed notably poorly. Since [1,2] share the same architectural limitations (unless their network designs are modified), their results would likely be similarly inadequate, making further comparisons uninformative for evaluating our contributions.

Rationale for Expert Selection

We acknowledge that relpscost is indeed less accurate than strong branching. Consequently, using relpscost as the expert policy for GCNN would inevitably degrade its performance. However, we deliberately chose Relpscost for the following critical reasons:

1. Computational Tractability in Data Collection: Our dataset construction requires solving training instances with Relpscost to collect (state-action) pairs. While strong branching is more precise, its prohibitive computational cost makes it impractical for large-scale data generation on complex instances. Relpscost provides a feasible trade-off between efficiency and solution quality.
2. Feature-Expert Alignment for Generalization: To ensure TreeGate's generalization capability across arbitrary instances, the feature design incorporates numerous pseudo-cost-related components. These features inherently align better with relpscost's behavior, as relpscost is a pseudo-cost that leverages high-quality historical information from strong branching. Using strong branching labels would create a mismatch between the features and expert policy, severely degrading model performance.

We have also provided detailed explanations in "Response to Q3" for Reviewer QH4H.

Why No Standard Deviation?

Since the test instances consist of various types of problems, each with inherent differences in difficulty and the number of nodes, the variance is not meaningful for our evaluation. Meanwhile, we use the geometric mean instead of the arithmetic mean to reduce the impact of extreme values across different problem types.

We have also incorporated additional statistical information in "Response to Weakness 1" for Reviewer KMMV.

Real Data Volume

As addressed in previous responses, the actual dataset does not simply consist of the number of instances. Rather, each instance contains a large collection of state-action data pairs. This point has been elaborated in detail in Line 238 of our manuscript. Specifically, the total number of training data pairs is 153,167 for MILP-S and 393,668 for MILP-L.

Regarding the issue with the code not running

"mamba_ssm" is a Python library, not a file written by us, and you can install it via pip install.

Reference

[1] Scavuzzo, Lara, et al. "Learning to branch with tree mdps." Advances in neural information processing systems 35 (2022): 18514-18526.

[2] Parsonson, Christopher WF, Alexandre Laterre, and Thomas D. Barrett. "Reinforcement learning for branch-and-bound optimisation using retrospective trajectories." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.

[3] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in neural information processing systems 32 (2019).

[4] Chen, Lili, et al. "Decision transformer: Reinforcement learning via sequence modeling." Advances in neural information processing systems 34 (2021): 15084-15097.

Response to Q2: Reason for using Relpscost and Results on homogeneous problems

Thank you for your suggestion! First, we would like to emphasize that our method focuses on heterogeneous scenarios (the premise), and TreeGate features is better suited for the relpscost expert. Nevertheless, we would be happy to conduct experiments in homogeneous settings as you suggested. We will address your concerns from these two perspectives separately.

Strong Branching or Relpscost? Further Comparative Experiments

To maintain the generalization capability of the branching policy (this is a fundamental premise of our work, as we aim to focus specifically on generalization performance), we adopted the same feature design and network architecture as TreeGate [1]. Under this framework, we trained policies using both strong branching and relpscost as experts, with results below:

Table 1: The imitation learning results using TreeGate as the network framework, with strong branching and relpscost serving as the experts respectively. The training was conducted for 50 epochs in all cases. The table reports the final network's loss and accuracy on both the training and test sets, as well as the solving time performance on test instances from MILP-S.

The results demonstrate that under the TreeGate framework, imitating strong branching achieves significantly lower accuracy compared to imitating relpscost, making training considerably more difficult. Meanwhile, on test instances, the policy imitating relpscost shows clearly superior performance.

Results on homogeneous problems

Many reviewers have raised concerns that imitating relpscost may not surpass relpscost itself. Therefore, here we conduct experiments on homogeneous scenarios. Specifically, we use Set Covering for both training and testing instances, only varying the instance parameters. The results are as follows:

Table 1: Results of training and testing on Set Covering. Both Mamba-Branching and TreeGate were initialized with relpscost once. During training, the expert policy being imitated was relpscost, as the previous section has already demonstrated that imitating Strong Branching leads to significantly worse training accuracy.

This result clearly demonstrates one key point: imitating relpscost does not inherently prevent a branching policy from surpassing relpscost. However, why does Mamba-Branching only exceed relpscost on complex problems in heterogeneous scenarios? We argue that this is fundamentally due to the inherent complexity of heterogeneous settings -- all neural networks face generalization challenges, whereas relpscost remains consistent across any problem. The intrinsic difficulty of heterogeneous scenarios leads to Mamba-Branching surpassing relpscost only in complex instances. However, if the problem difficulty is reduced (e.g., by switching to homogeneous settings), exceeding relpscost is not impossible.

Therefore, we would like to emphasize: Mamba-Branching can surpass relpscost in complex heterogeneous scenarios, representing an improvement over prior work. However, the concern that Mamba-Branching does not consistently outperform relpscost stems from our deliberate choice of a challenging setting -- heterogeneous scenarios. In homogeneous problems, Mamba-Branching does achieve superior performance over relpscost.

Thank you for your response! We sincerely appreciate your engagement in this discussion, and please allow me to address your concerns.

Response to Q1: Expectations on Useful Representation Learning

We emphasize that the design of a branching policy consists of two key components: feature design and network architecture design. As extensively discussed with Reviewer QH4H, feature design benefits from the MILP community, while network architecture design draws from advances in the deep learning community.

In our work, the feature design is entirely adopted from TreeGate, whereas our primary contribution lies in the neural network architecture: a novel design based on Mamba for sequential modeling and contrastive learning.

Compared to learning representations directly from raw data (as in typical representation learning methods), the branch-and-bound tree does not possess readily available raw data. Instead, we must manually design a set of features to serve as the neural network's primary input. Effective features require deep domain knowledge of MILP solvers and careful, manual engineering.

Response to Q3: Time Horizon

We understand your concerns, but the selection of 24 time horizons is a carefully considered trade-off given hardware constraints. We justify this choice from three perspectives:

1. Hardware Efficiency: As we mentioned in our previous rebuttal, while the 24-time horizon remains within reasonable limits, it already incurs substantial hardware overhead. Based on the experimental results, this choice achieves performance improvements while maintaining reasonable computational costs.

2. Advancement Over Prior Work: Compared to TreeGate, which only considers the current time horizon, our ability to incorporate 24 time horizons represents meaningful progress.

3. Alignment with Motivation: While it may appear contradictory at first glance, we emphasize that utilizing the entire sequence is not necessarily optimal. For instance, in reinforcement learning methods for POMDPs, RNN-based approaches often process the hidden state from the previous steps and the current observation -- despite having access to longer histories, RNNs employ forgetting mechanisms rather than retaining complete historical information. Similarly, for branch-and-bound trees, 24 time horizons strike a balance: they capture relevant sequential information while avoiding excessive focus on overly lengthy histories.

In summary, the 24-time horizon achieves hardware feasibility while demonstrating meaningful improvements over prior work. Meanwhile, although sequential information is indeed crucial (as per our motivation) -- similar to other sequence modeling approaches (e.g., RNNs) -- it is neither necessary nor optimal to remember the complete history. The incorporation of forgetting mechanisms aligns with, rather than contradicts, our original motivation.

Rationale for Expert Selection: Strong Branching or Relpscost?

We note that Reviewers 3WGQ, KMMV, and QH4H have all raised concerns about our use of relpscost as the expert for imitation learning, with Reviewer QH4H particularly rejecting this approach entirely and suggesting that we should instead adopt the GCNN + strong branching expert training paradigm [3].

We fully acknowledge that GCNN + strong branching represents a more commonly used and performance-proven approach. However, the application scenario of our work differs fundamentally from that of GCNN: while GCNN focuses on training and testing on homogeneous instances, our method specifically targets testing on completely heterogeneous instances, emphasizing the generalization capability of the branching policy.

Therefore, we emphasize that our approach fundamentally relies on the TreeGate neural network architecture and feature design specifically tailored for generalized branching policies. Under this framework, we have experimentally validated the necessity of using relpscost as the expert policy and provided thorough analysis of the underlying rationale.

We would like to clarify upfront that TreeGate+relpscost is not our original contribution, but rather represents the standard paradigm commonly adopted in prior work on generalized branching policies [1,2].

Comparative Experiments

Under TreeGate, we trained policies using both strong branching and relpscost as experts, with results below:

Table 1: The imitation learning results using TreeGate as the network framework, with strong branching and relpscost serving as the experts respectively. The training was conducted for 50 epochs in all cases. The table reports the final network's loss and accuracy on both the training and test sets, as well as the solving time performance on test instances from MILP-S.

The results demonstrate that under the TreeGate framework, imitating strong branching achieves significantly lower accuracy compared to imitating relpscost. Meanwhile, on test instances, the policy imitating relpscost shows clearly superior performance.

Analysis and Clarification

TreeGate emphasize incorporating tree-search-related features into the design without focusing on specific instances, while pseudo-costs align with the requirements of tree search by leveraging historical information. And relpscost essentially represents an improved form of pseudo-cost that incorporates historical strong branching experience.

The features capture "imperfect" pseudo-costs while the relpscost labels contain "refined" pseudo-costs. The neural network learns to transform pseudo-costs from imperfect to refined versions. The feature design inherently results in better compatibility between TreeGate and relpscost, which consequently leads to the failure of TreeGate + strong branching.

Moreover, relpscost outperforms strong branching in terms of dataset collection speed. Although compared to the fundamental limitations of strong branching, this advantage might be relatively less significant.

Finally, we would like to clarify the following points:

1. Our paper’s primary contribution lies in Mamba-based sequential modeling and contrastive learning, rather than in re-evaluating the feature design choices of prior methods. Under the current framework, the TreeGate + strong branching is unsuitable. Why don't we modify the feature design to accommodate strong branching? This is indeed a highly insightful suggestion. However, such modification would extend far beyond the scope of our current paper and represents an entirely new research direction -- one that is both promising and challenging in its own right.
2. These comparative experiments are intended to analyze TreeGate’s behavior under different experts, rather than to serve as an ablation study for our proposed method.

Reference

[1] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 5. 2021.

[2] Lin, Jiacheng, et al. "Learning to branch with Tree-aware Branching Transformers." Knowledge-Based Systems 252 (2022): 109455.

[3] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." Advances in neural information processing systems 32 (2019).

Proof of Proposition 1 -- Motivation for the Contrastive Loss

Reviewers KMMV, X7WR, and TcMy have all raised questions regarding Proposition 1, requesting further clarification on its connection to the contrastive learning approach and its role in our methodology, as well as potentially requiring a formal proof. In response, we have provided explanations from two perspectives: first, an intuitive explanation from the conceptual standpoint; second, an attempt to provide an explanation using mathematical formulations.

First, we make the following two assumptions, which will serve as the foundation for our subsequent analysis:

1. The feature embeddings of the optimal branch decision variable ($e_t^a$) can be distinguished from those of other branch variables ($e_t^i, \forall i\in \mathcal{C}_t, i\neq a$) in the vector space.
2. The feature embedding $e_t$ is informative for branch decision-making.

Intuitive Explanation

Based on assumption 1, we establish an anchor point $e_t^m$ and employ contrastive learning to train the model such that: (1) the optimal branch variable's feature $e_t^a$ is pulled closer to $e_t^m$, while (2) other variables' features are pushed away from $e_t^m$. This approach amplifies the separation between optimal and non-optimal features, thereby ensuring sufficient distinguishability when these features are subsequently processed by the Mamba architecture.

Mathematical Formulations

For each branching variable $i$, we define $F(i)$ as the branching score function (in this paper, the relpscost score) for variable $i$, such that the optimal branching variable satisfies $a = \arg\max_{i} F(i).$

Assumption 2 posits that the embeddings can encode branching quality information, which we simplify to a linear relationship $e_t^i = \alpha F(i) + \epsilon_i,$where $\alpha \in \mathbb{R}^d$ is a variable independent vector representing the quality-sensitive direction in the embedding space. $\epsilon_i \in \mathbb{R}^d$​ is a noise term satisfying $\mathbb{E}(\epsilon_i)=0$ with small magnitude $|\epsilon_i|$.

We use max pooling over the embeddings as the anchor point, defined as:

=[...,\max_i (F(i)\alpha(j)+\epsilon_i(j)),...].$$ For $e_t^a$, we have: $$e_t^a=[...,\max_i F(i)\alpha(j) + \epsilon_a(j),...].$$ Indeed, if we assume that all $\epsilon_i$ terms are sufficiently similar in magnitude, we can derive the approximation $e_t^a \approx e_t^m$. Therefore, we can reasonably establish that $$\forall i \neq a,\text{sim}(e_t^a, e_t^m) > \text{sim}(e_t^i, e_t^m).$$ This formulation is mathematically **equivalent** to the expression presented in the original paper. $$\forall t, \exists \delta > 0 \text{ s.t. } \text{sim}(e_t^a, e_t^m) \geq \max_{i \neq a} \text{sim}(e_t^i, e_t^m) + \delta$$ Certainly, we acknowledge that the proof involves certain assumptions and approximations, which may lack full mathematical rigor. Additionally, during the neural network training process under contrastive loss, we cannot strictly guarantee that $\delta>0$ holds completely. However, we believe these results effectively **reflect the underlying intuition** behind our design: to make the optimal variable's features closer to the anchor point while pushing other features farther away, thereby making the optimal variable's features more **distinctive** in the vector space.

Additional Statistical Information

Reviewer 3WGQ, KMMV, X7WR and TcMy have expressed concerns regarding the number of test instances in our experiments. In fact, the number of test instances already exceeds that of previous works (we have 57 + 16 = 73, while TreeGate [1] has 8 and T-BranT [2] has 66), which already demonstrates stronger generalizability.

However, we have provided additional statistical information to further demonstrate the advantages of our method.

Quartile Tables

Table 1: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the quartile table for time. For example, Mamba-Branching achieves the time of 140.33 at the 50%, meaning that 50% of the instances have solving time within 140.33. Meanwhile, the solving time contains difficulty information, and from this table, we can observe the adaptability of the method to problems of varying difficulties.

Table 2: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the quartile table for Node counts. The meaning of this table is similar to that of Table 1.

As shown, Mamba-Branching attains the smallest time and node count at the 25th, 50th, and 75th percentiles, indicating consistently superior performance across all difficulty ranges compared to the other two methods. This suggests that Mamba-Branching’s lower geometric mean is not due to exceptional performance on a few extreme instances but rather stems from robust and balanced improvements across the entire benchmark.

Win/Tie/Loss Statistics Table

Table 3: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the Win/Loss table for node counts. Since 57 instances are too many to display their results directly, we use the win/tie/loss format to show the median performance (across 5 random seeds) of different methods on various instances when compared pairwise.

Table 4: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the Win/Loss table for time. The meaning of this table is consistent with that of Table 3.

Table 5: For the hard instances in the MILP-L dataset (16 instances, each with 5 random seeds), the Win/Loss table for primal-dual integral.

It can be observed that Mamba-Branching outperforms both TreeGate and T-BranT on both easy and hard instances, while also achieving superior performance over relpscost on difficult instances. This finding aligns with the original conclusions presented in this paper.

Additional Ablation Studies

Reviewers X7WR and TcMy have each suggested additional ablation studies, including:

1. Replacing the contrastive learning with standard supervised learning, then discarding the linear classification head after training, named Mamba-Branching-classifier.

2. Adding T-BranT-p, which refers to T-BranT without the 1-step relpscost initialization, purely using the neural network.

3. Removing the positional encoding in Mamba-Branching, named Mamba-Branching (w/o pe).

4. Replacing the sequence model with GRU, named GRU-Branching.

Here, we systematically organize all supplementary results under both initialized and non-initialized (-p) settings for a comprehensive comparison.

Table 1: Performance comparison on MILP-S: All methods use one-time relpscost initialization. Mamba-Branching-classifier is added, which does not employ contrastive learning but instead uses standard supervised learning, with the linear classification head discarded after pre-training.

Table 2: Performance comparison on MILP-S: All methods rely purely on neural networks (-p), with TBranT-p, Mamba-Branching-p (w/o pe), and GRU-Branching-p added. Here, TBranT-p achieves pure neural network inference through algorithmic modifications, Mamba-Branching-p (w/o pe) removes positional encoding, and GRU-Branching-p replaces the sequence model with a GRU.

The aforementioned results further demonstrate the advantages of Mamba-Branching, which is consistent with the conclusions drawn in the original paper.

Without Comparison to Other Baselines

Reviewer 3WGQ mentioned that we should compare with baselines [1, 2], and Reviewer TcMy suggested a comparison with [3]. These works all employ neural networks for branching decisions, which aligns with our research domain, and we will include them in the related work section in the subsequent version.

However, we would like to emphasize that these works are not directly comparable to ours. This is because they are all based on GCNN frameworks. As we mentioned earlier, these works focus on solving isomorphic problems repeatedly -- where the same type of problem can have varying parameters but retains an unchanged structure. In contrast, our method emphasizes a generalized branching policy: it is trained on certain problems and then tested on completely unknown and heterogeneous instances. This distinction is crucial, as evidenced by our experimental results, which show that GCNN performs very poorly on heterogeneous instances.

Therefore, since [1,2,3] are all GCNN-based, their network architectures are inherently unsuitable for heterogeneous-instance scenarios. We believe that the comparison with GCNN is already sufficient, and further comparisons with these GCNN-based methods would not meaningfully validate our contributions.

Without Comparison to Other Training Paradigms

Both reviewers TcMy and 3WGQ pointed out that we should consider comparisons with paradigms beyond imitation learning, such as the reinforcement learning (RL) paradigm. Indeed, reinforcement learning methods do not rely on expert demonstrations and thus have the potential to surpass imitation learning approaches.

However, as discussed in [1,2], the characteristics of the branch-and-bound environment pose significant challenges for policy training under the RL paradigm, including:

1. Sparse reward problem
2. Long-episode problem: the excessive number of steps in an episode leads to high variance in policy gradients.
3. Long-term credit assignment problem: a single branching decision may have delayed effects that persist over many steps.

To the best of our knowledge, imitation learning remains the most effective paradigm for training branching policies to date.

Reference

[1] Scavuzzo, Lara, et al. "Learning to branch with tree mdps." Advances in neural information processing systems 35 (2022): 18514-18526.

[2] Parsonson, Christopher WF, Alexandre Laterre, and Thomas D. Barrett. "Reinforcement learning for branch-and-bound optimisation using retrospective trajectories." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.

[3] Seyfi, Mehdi, et al. "Exact combinatorial optimization with temporo-attentional graph neural networks." Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2023.

Is it truly impossible to surpass relpscost itself by imitating relpscost? -- Experiments in Homogeneous Scenarios and the Fundamental Challenges in Heterogeneous Scenarios

Many reviewers have raised concerns that imitating relpscost may not surpass relpscost itself. Therefore, here we conduct experiments on homogeneous scenarios. Specifically, we use Set Covering for both training and testing instances, only varying the instance parameters. The results are as follows:

Table 1: Results of training and testing on Set Covering. Both Mamba-Branching and TreeGate were initialized with relpscost once. During training, the expert policy being imitated was relpscost, as the previous section has already demonstrated that imitating Strong Branching leads to significantly worse training accuracy.

This result clearly demonstrates one key point: imitating relpscost does not inherently prevent a branching policy from surpassing relpscost. However, why does Mamba-Branching only exceed relpscost on complex problems in heterogeneous scenarios? We argue that this is fundamentally due to the inherent complexity of heterogeneous settings -- all neural networks face generalization challenges, whereas relpscost remains consistent across any problem. The intrinsic difficulty of heterogeneous scenarios leads to Mamba-Branching surpassing relpscost only in complex instances. However, if the problem difficulty is reduced (e.g., by switching to homogeneous settings), exceeding relpscost is not impossible.

Therefore, we would like to emphasize: Mamba-Branching can surpass relpscost in complex heterogeneous scenarios, representing an improvement over prior work. However, the concern that Mamba-Branching does not consistently outperform relpscost stems from our deliberate choice of a challenging setting -- heterogeneous scenarios. In homogeneous problems, Mamba-Branching does achieve superior performance over relpscost.

Further Suggestion: Comparison with GCNN in Homogeneous Scenarios

Currently, since we have demonstrated in homogeneous scenarios that TreeGate + relpscost can outperform relpscost, the reviewers further suggest comparing with GCNN under the same setting while following GCNN's experimental setup. However, we emphasize that this would again entirely deviate from our original goal -- achieving breakthroughs in heterogeneous scenarios. If we retain TreeGate + relpscost, a method specifically designed for heterogeneous scenarios, it will undoubtedly be uncompetitive compared to GCNN in homogeneous scenarios. However, if we completely abandon the TreeGate network and switch to using the GCNN network with the same experimental setup as GCNN, it would become an entirely new research direction -- requiring changes to the entire methodology and network design. Moreover, such a shift would deviate from the original focus of our work, which is dedicated to heterogeneous scenario research.

We acknowledge that such a comparison would make our paper more compelling. However, due to the page limit of NeurIPS, our study on heterogeneous scenarios already occupies the full capacity of the manuscript. Adding an entirely new set of experiments in homogeneous scenarios would make the paper overly lengthy.