A Markov decision process for variable selection in Branch and bound

Some articles have already defined branching as MDP. Can you summarize the differences between you and these articles?

7. The article quoted by the reviewer trains RL agents with evolutionary strategies using a novelty score based on a Wasserstein distance to measure the similarity between current and new candidate policies. Building on the work of (He et al. 2014), just like (Etheve et al. 2020) and (Scavuzzo et al. 2022), they effectively define branching as an MDP resembling our BBMDP. Explicitly, the difference between the MDP described in (Sun et al. 2020) and BBMDP is that we include all the nodes of the B&B tree in the current state, while they only consider open nodes. This is because our bipartite graph representation of B&B nodes include statistics on the whole B&B tree, therefore, keeping track of the B&B tree is mandatory to preserve the Markov property. Importantly the MDP formulation described in (Sun et al. 2020), similar to the one labeled as temporal MDP in (Scavuzzo et al. 2022), has been found impractical by (Etheve et al. 2020) and (Scavuzzo et al. 2022) to learn efficient branching strategy with approximate dynamic programming and policy gradient algorithms, which is why they preferred using TreeMDP. Our contribution proposes a synthesis of the temporal MDP and TreeMDP frameworks described in (Scavuzzo et al. 2022), that preserves the training convergence properties brought by TreeMDP as well as fundamental MDP properties.

The contribution summary of the article is unclear. Can you further summarize it?

8. We thank the reviewer for allowing us to clarify our contribution. We partly rewrote the introduction section, see lines 50-57, to make our contribution more explicit. In our work, we show that despite improving the convergence of RL algorithms, the TreeMDP formulation introduces approximations which undermine the asymptotic performance of RL branching agents in the general case. In order to address this issue, we introduced BBMDP, a principled vanilla MDP formulation for variable selection in B&B, which preserves convergence properties brought by TreeMDP without sacrificing optimality. Computational experiments validate our approach, as the DQN-BBMDP agent obtains both better training and generalization performance on the Ecole benchmark over TreeMDP agents. We believe that leveraging the BBMDP framework is essential for advancing learning-based variable selection strategies in the future, as it enables the integration of state-of-the-art MCTS model-based RL algorithms that have proven capable of surpassing human knowledge in combinatorial tasks.

We now address the questions explicitly raised by the reviewer.

The meaning of symbols is confusing. For example, what’s the meaning of V, E in Line 84?

1. We thank the reviewer for sharing their confusion regarding notations. We adopted a standard convention in graph theory, noting V the set of vertices and E the set of edges. Please indicate whether there are further disturbing notations.

Why is the reward defined as -2 in the MDP definition, as I know, some papers define the reward as -1, can you explain it?

2. We thank the reviewer for raising this question. In fact, defining r= -2, r=-1, or r = -10 yields equivalent optimal branching policies for BBDMP. We defined r = -2 so that W-values of node o_i could be interpreted as the size of the subtrees rooted in o_i, which simplifies explanations in section 3.2. However, in our experiments, we implemented r = -1 for all agents in order to allow clearer comparison. We rewrote section 3.1, line 212-216 as well as Appendix B in order to make this explicit.

This may be important because the convergence guarantees of RL algorithms are often made in the discounted setting with litter than 1, Why is this paper setting the discounted with 1. Is there any experimental or theoretical support for this point?

3. We thank the reviewer for raising this issue. Like (Etheve et al. 2020) and (Scavuzzo et al. 2022), in order to ensure alignment with the objective described in Equation 1 line 131, we set the discount factor to γ=1. This is made possible by the finite length of BBMDP episodes. Setting γ=1 also simplifies Equation (3) in Proposition 1, which, in turn, streamlines the implementation process.

According to Gasse et al. (2019), why was this paper not compared to the facilities dataset? Why was this paper not compared to the hard dataset? Why does this paper not report the average per-instance standard deviation in Table 1?

4. We thank the reviewer for raising their concern on the absence of the Capacity Facility Location benchmark, which is present in (Gasse et al. 2019) and (Scavuzzo et al. 2022). In fact, (Gasse et al. 2019) and (Scavuzzo et al. 2022) used former versions of SCIP, for which these instances were challenging to solve; this is not the case anymore. Owing to improvements in SCIP 8.0.1 presolve module, Capacity Facility Location instances as described in (Scavuzzo et al. 2022) are now solved in typically 2 to 5 fives nodes, when they are not solved directly to optimality during presolve, rendering training on this benchmark trivial. Regarding the second and third part o the reiewer's question, we will include harder datasets as well as the per-benchmark standard deviation in the Appendix.

Why did this paper only test 20 instances on the medium transfer instances instead of testing 100 instances like the easy difficulty level? What would happen if this method also tested the 100 instances on the medium difficulty level?

5. We thank the reviewer for pointing this out. We include computational results averaged over 100 medium instances, averaged over 5 seeds.

For the variable selection problem, reinforcement learning seems to have no advantage over imitation learning both in training speed and testing effectiveness. So, what is the motivation behind our research in this paper?

6. We thank the reviewer for raising this issue. As discussed in section 1 line 47, we know that if IL yields better performance at the moment, its performance is capped by that of strong branching, which is not an optimal expert for variable selection. Moreover, as now discussed in section 2.3 line 153-159, theoretical and computational studies have shown that even the suboptimal performance of SB was out of reach for neural networks trained by imitation. In fact, low tree sizes associated with SB happen to be primarily due to the formulation improvements resulting from the massive number of LP solved by SB, rather than to the intrinsic quality of branching decisions themselves. Therefore, replicating the exact branching decisions made by SB results in significantly larger trees compared to SB itself, further limiting the performance that IL agents can achieve.

We thank the reviewer for their valuable time and detailed feedback. We have made modifications to the paper that we hope improve clarity and presentation. We start by addressing the concerns raised by the reviewer in order.

The related work about imitation learning for variable selection is insufficient.

1. We thank the reviewer for raising this issue. At the reviewer’s request, we added a paragraph to our related work section line 153-159, which discusses extensions to the work of (Gasse et al. 2019) as well as theoretical limitations.

There is no pipeline to explain how the proposed method works.

2. We thank the reviewer for raising their concern on the absence of a general pipeline description. The overall DQN-BBMDP pipeline is actually simple, and very similar to the ones of DQN-retro (Parsonson et al. 2022) and (Scavuzzo et al. 2022), as described in section 4 line 338-341. Additionally, we provide the pseudocode for DQN-BBMDP as well as a full list of hyperparameters in Appendix B, along with a description of neural network architecture and state representation functions used to train RL agents are detailed in Appendix C. Is that inline with the reviewer’s expectations regarding pipeline description?

The proposed method seems to only apply to the binary integer programming problem, it is a little unclear to me how much technical novelty is in the B&B MDP and whether the contributions in this paper are significant enough.

3. We thank the reviewer for raising their concern, however, our work is not limited to binary problems. Throughout the document, we consider general mixed integer linear programs, as defined line 75-79. If the reviewer is interested in applications of BBMDP beyond the MILP framework, we stress that our method effectively generalizes to any combinatorial problem traditionally solved by branch and bound, meaning any combinatorial problem for which there exist efficient separation and evaluation methods. Regarding the primary innovations brought by BBMDP, we added a general comment that we hope helps clarify the technical novelty of our contribution.

The experiment seems insufficient, only testing in easy and medium difficulty levels, lack of comparison in hard difficulty levels.

4. We thank the reviewer for raising this issue. Since no prior RL contribution tested its agents on higher-dimensional problems, for the sake of comparison, we did not carry out tests on harder instance benchmarks at first. In fact, RL agents more than IL agents have been found to struggle to generalize to higher dimensions, which is why prior contributions only evaluated generalization on medium benchmarks. Nevertheless, we will include performance comparison between RL and IL agents on the hard benchmark shortly.

The ideas in the paper took me some time to properly digest. I believe all of the information needed for the reader to digest is there, but think that the paper could make this process easier for the reader.

5. We have made several revisions to the paper to clarify our contribution. We hope these changes enhance the readability and make the paper more digestible for the reader.

Dear Reviewer jMj7,

Thank you again for your valuable feedback. We have conducted additional experiments on medium and hard instances that we integrated to Appendix H, along with additional performance metrics. We also provided thorough discussions to address your concerns. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We appreciate the time and effort you have dedicated to reviewing our work.

Sincerely,

Authors

While the proposed methods show improved performance and reduce the gap with IL approaches, a considerable performance disparity remains.

We thank the reviewer for raising their concern. In fact, we believe the performance gains presented in Table 1 are substantial. We include two additional columns in Table 1, showing the aggregate average performance obtained by each agent across the four MILP benchmarks, normalized by the score of DQN-BBMDP. It appears that the performance gap between IL and DQN-BBMDP is narrower than the gap between DQN-BBMDP and any other RL agent. This is particularly true when evaluating generalization performance on the medium dataset, as discussed line 435-437 in the latest version, which underpins the computational benefit of adopting BBDMP over TreeMDP.

Additionally, all tested problem classes are synthetic mathematical benchmarks, leaving the performance on realistic datasets unexamined.

We thank the reviewer for raising their concern. We argue that the Ecole benchmark is a well-established benchmark for training and evaluating learning agents in general, beyond variable selection. Furthermore, our experimental protocol is in line with that of prior IL and RL contributions, who trained and tested their baselines exclusively on the Ecole benchmark. Notwithstanding, we agree with the reviewer that showcasing enhanced performance on real-world instance datasets is critical for the development of learning-based branching strategies in the future.

We now address the question explicitly raised by the reviewer.

Why define R(s, a) = −2 for all transitions until episode termination? Is intuition behind the number -2? Is that the results of tuning?

1. We thank the reviewer for raising this question. In fact, defining r= -2, r=-1, or r = -10 yields equivalent optimal branching policies for BBDMP. We defined r = -2 so that W-values of node o_i could be interpreted as the size of the subtree rooted in o_i, which simplifies explanations in section 3.2. However, in our experiments, we implemented r = -1 for all agents in order to allow clearer comparison with prior RL baselines. We rewrote section 3.1, line 212-216 as well as Appendix B in order to make this explicit.

Any intuition of why choosing the HL-Gauss cross-entropy loss?

2. We thank the reviewer for raising this question. Complete description and theoretical motivation for the use of HL-Gauss loss can be found in Appendix E, referred to line 316.

Why not including IL-DFS to the medium problem classes? Will the drop of the performance of using DFS will become more significant for the larger instances?

3. We thank the reviewer for pointing this out. The performance gap between IL and IL-DFS on medium instances is inline with that on easy instances. We include these results in the latest submission, in order to remove ambiguity.

We thank the reviewer for their valuable time and detailed feedback. We have made modifications to the paper that we hope improve clarity and presentation. We address the concerns raised by the reviewer in order.

The adoption of a DFS node selection strategy allows for a more canonical Bellman operator and potentially broader applicability of current RL frameworks. However, the impact of this restriction on performance is not fully explored, and the paper lacks a discussion on potential trade-offs related to this design choice.

We thank the reviewer for pointing out this issue. Ideally, variable and node selection policies should be optimized jointly in Equation (1) in order to fully optimize the performance of B&B over a distribution of instances. Following findings (Etheve 2021), who found node selection optimization to be negligible against variable selection optimization, we focus on variable selection, and adopt a DFS node selection policy to enable the decomposition of the V-value function into a sum of independent W-values. Incidentally, our DFS-based DQN-BBMDP agent was found to clearly outperform the prior state-of-the-art DQN-retro agent, which uses SCIP default node selection heuristic. Moreover, when training and testing DQN-BBMDP following this same SCIP node selection heuristic, we found performance to be strictly equivalent to the DFS baseline, which suggests that the adoption of DFS is not compulsory to maintain training performance. We believe this to be due to the behavior of the SCIP default node selection heuristic, which exhibits diving behavior resembling that of DFS. This is all discussed in the ablation study in section 4.4 and in Appendix F, referred to line 453, that we partly rewrote to address more specifically the reviewer’s concern.

The authors highlight BBMDP’s potential to support a wider range of RL algorithms, yet only DQN, which is also compatible with TreeMDP, is tested. Consequently, the empirical results do not demonstrate the benefits of BBMDP’s broader RL applicability.

We thank the reviewer for raising this issue. As highlighted in Figure 3, we show that BBMDP is better suited than TreeMDP for k-step temporal difference learning, since k-step DQN-TreeMDP yields inconsistent Bellman updates. Our computational experiments support this finding. As shown in Table 1 and 2, p. 9-10, DQN-BBMDP clearly outperforms DQN-tMDP as well as other TreeMDP agents, while the ablation study highlights that k-step temporal difference improves the performance of DQN-BBMDP agent, while it undermines the performance of Tree-DQN BBMDP. Moreover, we believe that leveraging the BBMDP framework is essential for advancing learning-based variable selection strategies in the future, as it enables the integration of state-of-the-art MCTS model-based RL algorithms that have proven capable of surpassing human intelligence in combinatorial tasks.

For medium instance testing, only 20 instances are evaluated, which may be insufficient to reliably represent each problem class. Increasing the test set to at least 100 instances would provide a more robust assessment of performance across diverse scenarios.

We thank the reviewer for pointing this out. We include computational results over 100 medium instances, averaged over 5 seeds, in our latest submission.

When comparing methods on node count and solution time, there are inconsistencies between the two metrics: a shorter runtime does not always correspond to fewer nodes processed. For instance, DQN-BBMDP sometimes achieves a lower node count yet requires more time, and vice versa when compared with IL approaches.

We thank the reviewer for pointing this out. In fact, if time and node metrics are generally aligned in B&B (this is reflected overall in our results tables) this is not automatic. In fact, strategy A may yield more nodes and yet be faster than strategy B, for example if the nodes explored by strategy A require in average fewer simplex iterations to compute linear relaxations. Nevertheless, RL branching agents are generally trained to minimize B&B tree size, as this objective has proven to be a more robust and consistent target across various hardware configurations, thus fostering performance reproducibility.

Dear Reviewer 3mcR,

Thank you again for your valuable feedback. We have conducted further experiments and provided thorough discussions to address your orignal concerns. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We sincerely appreciate the time and effort you have dedicated to reviewing our work.

Kind regards,

Authors

We thank the reviewer for their valuable time and feedback. We address their questions in order.

Can you show the sample complexity of the methods compared to previous ones?

1. We understand that the reviewer is interested in comparing the sample efficiency of the different RL agents. We provide training curves in Appendix G, referred to line 369, which show that sample efficiency is roughly equivalent between DQN-BBMDP, DQN-TreeMDP and DQN-Retro. We did not retrain the PG-tMDP agent from (Scavuzzo et al. 2022), however, we are confident that sample complexity would be worse than that of DQN agents, since REINFORCE is an on-policy learning algorithm, while DQN is off-policy. If we misunderstood the reviewer’s point, could the reviewer please reformulate their question.

Is your methods also effective on larger instances? For instances that cannot be solved within the runtime limit, one can still evaluate the primal-dual gap/primal-dual integral to see if the method is effective or not.

2. Thank you for raising this important issue. Since no prior RL contribution tested its agents on higher-dimensional problems, for the sake of comparison, we did not carry out tests on harder instance benchmarks at first. In fact, RL agents more than IL agents have been found to struggle to generalize to higher dimensions, which is why prior contributions only evaluated generalization on medium benchmarks. Nevertheless, we will include performance comparison between RL and IL agents on the hard benchmark shortly.

Dear Reviewer ETsw,

Thank you again for your valuable feedback. We have conducted additional experiments on medium and hard instances that we integrated to Appendix H, along with additional performance metrics. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We appreciate the time and effort you have dedicated to reviewing our work.

Sincerely,

Authors

We thank the reviewer for their valuable time and feedback. We have made modifications to the paper that we hope improve clarity and presentation. We address each concern in order:

The primary innovations of BBMDP are unclear.

1. We thank the reviewer for sharing their concerns on the primary innovations of BBMDP. We added a general comment that we hope helps clarify our contribution.

The experiments are conducted on a relatively small scale. The medium instances require only 1 minute to solve.

2. We thank the reviewer for raising this important issue. Since no prior RL contribution tested its agents on higher-dimensional problems, for the sake of comparison, we did not carry out tests on harder benchmarks at first. In fact, RL agents more than IL agents have been found to struggle to generalize to higher-dimensional instances, which is why prior RL contributions only evaluated generalization on medium benchmarks. Nevertheless, we will include performance comparison between RL and IL agents on hard benchmarks similar to the one in (Gasse et al. 2019).

BBMDP's performance is not significantly superior to other RL methods. It is even inferior on the medium dataset.

3. We thank the reviewer for raising their concern. In fact, we believe the performance gains presented in Table 1 are substantial. As highlighted in the introduction, MILP solvers are highly optimized software, and achieving a 10–15% reduction in solving time is usually recognized as a significant achievement within the combinatorial optimization community. Additionally, due to the relatively small size of our training instances, surpassing existing solvers becomes even more challenging, as these solvers excel at solving lower-dimensional instances. In order to make our results more meaningful, we include two additional columns in Table 1 p.9, showing the aggregate average performance obtained by each agent across the four MILP benchmarks, normalized by the score of DQN-BBMDP. It appears that the performance gap between IL and DQN-BBMDP is clearly narrower than the gap between DQN-BBMDP and any other RL agent. This is particularly true when evaluating generalization performance on the medium dataset, as discussed line 436-438 in the latest version, which underpins the computational benefit of adopting BBDMP over TreeMDP.

We also address the questions explicitly raised by the reviewer.

Could you clearly differentiate between BBMDP and TreeMDP?

1. The main difference between BBMDP and TreeMDP, is that BBMDP is a MDP, while TreeMDP is not. We included clearer comparisons between BBMDP and TreeMDP in section 3.1 line 216-219, as well as in the introduction, line 50-55, in order to make it more explicit for the reader. In fact, the BBMDP framework allows to leverage a broader range of RL algorithms in order to learn efficient branching strategies, while preserving the convergence properties brought by TreeMDP’s use of DFS node selection policy. In particular, this is achieved by defining the entire B&B tree as the current state, instead of merely the current B&B node as in TreeMDP.

What does "suboptimal branching experts" refer to? Is it the strong branching rule?

2. Yes, this is strong branching. We added a paragraph on imitation learning in the Related Work section 2.3, line 152-159, in order to make this more explicit for the reader.

Given that node selection and variable selection influence each other, what does it mean to have this fixed order?

3. We thank the reviewer for pointing out this issue. Ideally, variable and node selection policies should be optimized jointly in Equation (1) in order to fully optimize the performance of B&B over a distribution of instances. Following findings of (Etheve 2021), who found node selection optimization to be negligible against variable selection optimization, we focus on improving variable selection. However, we argue that our BBMDP framework is a necessary step towards the joint optimization of node and variable selection strategies. In fact, node and variable selection strategies can be optimized jointly within the BBMDP framework. In fact, this is simply achieved by redefining action selection as the process of selecting both an open node and an integer variable to branch on. Such a reformulation is not possible within the TreeMDP framework, as states are defined as the current B&B nodes, which, by definition, are determined by the node selection policy, and can hence not be governed by the action selection policy.

Could you conduct tests on larger datasets, similar to those used by Gasse et al.?

4. At the reviewer’s request, we will include tests on larger datasets, similar to the ones in Gasse et al. (2019).

Would it be possible to provide additional metrics, such as wins and P-D convergence plots?

5. At the reviewer’s request, we will provide additional performance metrics in the Appendix.

Dear Reviewer hrBM,

Thank you again for your valuable feedback. We have conducted additional experiments on medium and hard instances that we integrated to Appendix H, along with additional performance metrics. We also provided thorough discussions to address your concerns. As the rebuttal period is nearing its conclusion, we wanted to follow up to ensure our responses have adequately addressed the reviewers' concerns. Please let us know if there are any remaining questions or areas where further clarification is needed. We appreciate the time and effort you have dedicated to reviewing our work.

Sincerely,

Authors