A Markov decision process for variable selection in Branch and bound

Authors: Paul STRANG, Zacharie ALES, Côme Bissuel, Safia Kedad-Sidhoum, Olivier Juan, Emmanuel Rachelson
Primary area: reinforcement learning
Keywords: Mixed-integer linear programming; Branch and bound; Reinforcement learning; Markov decision process

Abstract:
Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and bound (B\&B). A key factor influencing the performance of B\&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B\&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce B\&B MDPs, a principled vanilla MDP formulation for variable selection in B\&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B\&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

Decision: reject
Reviewer scores: 3, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1730711525874

thread_type:
official_review

<thread_object>
creator: reviewer_jmj7

<content>
summary:
This work addresses the issue that these alternative MDP formulations introduce approximations that undermine the asymptotic performance of RL branching agents in the general case. This paper introduces a B&B MDP formulation for variable selection in B&B, which preserves optimality without sacrificing the convergence properties brought by previous contributions. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

strengths:
1)	Original: This paper introduces a vanilla MDP formulation for variable selection in B&B, allowing the leveraging of a broad range of RL algorithms to learn optimal B&B heuristics.
2)	Quality:
The overall presentation is good
The paper discusses the related works about RL-based methods in a fairly clear manner.
3)	Clarity: 
Overall, the paper is clear and easy to follow, however, some writing is confusing, especially since some symbols are not defined.
4)	Significance: 
The paper studies introduce a vanilla MDP applied to the variable selection problem to learn optimal B&B branching strategies, which seems to be an important research direction.

weaknesses:
1.	The related work about imitation learning for variable selection is insufficient,
2.	There is no pipeline to explain how the proposed method works.
3.	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.
4.	The experiment seems insufficient, only testing in easy and medium difficulty levels, lack of comparison in hard difficulty levels.
5.	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.

questions:
1.	The meaning of symbols is confusing. For example, what’s the meaning of ($v, \varepsilon$) in Line 84?
2.	Why is the reward defined as -2 in the MDP definition, as I know, some papers define the reward as -1[1], can you explain it?
3.	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?
4.	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?
5.	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?
6.	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?
7.	Some articles have already defined branching as MDP [1]. Can you summarize the differences between you and these articles?
8.	The contribution summary of the article is unclear. Can you further summarize it?
[1] Improving Learning to Branch via Reinforcement Learning. NeurIPS Workshop, 2020. https://openreview.net/forum?id=z4D7-PTxTb
</content>
</thread_object>

</thread>
<thread>
creation date:
1730788291944

thread_type:
official_review

<thread_object>
creator: reviewer_3mcr

<content>
summary:
This paper introduces a novel Markov Decision Process (MDP) framework, BBMDP, for optimizing variable selection in Branch and Bound (B&B) algorithms in Mixed Integer Programming (MIP). By restricting the node selection strategy to depth-first search (DFS), the authors derive a more canonical Bellman equation for BBMDP, enabling broader use of reinforcement learning frameworks. This approach offers greater robustness than existing TreeMDP models by preserving optimality and convergence properties. The authors apply Deep Q-learning to BBMDP, demonstrating improved performance over previous RL approaches on TreeMDP across multiple MILP benchmarks, with significant reductions in both computation time and the number of B&B nodes required. Results further suggest that BBMDP effectively narrows the gap between reinforcement learning and imitation learning methods.

strengths:
1. The paper is well-written and easy to follow
2. The introduction of BBMDP provides a principled, canonical MDP formulation for variable selection in B&B, addressing limitations of previous TreeMDP approaches by enabling a broader application of reinforcement learning techniques with theoretical support.
3. The paper includes experiments on many standard MILP benchmarks

weaknesses:
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.

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.

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.

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.

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

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

questions:
Besides the concerns raised in the weakness part, I have the following additional questions:

1. Why define R(s, a) = −2 for all transitions until episode termination? Is intuition behind the number -2? Is that the results of tuning?
2. Any intuition of why choosing the HL-Gauss cross-entropy loss?
3. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730861994478

thread_type:
official_review

<thread_object>
creator: reviewer_etsw

<content>
summary:
The paper investigates an RL method for variable selection in branch-and-bound. It applies the general definition of MDP to B&B search so that general RL algorithms and theories can be applied to solve the problem. The MDP is solved with Q-learning. In experiments, the method is evaluated on four standard MILP benchmarks and compared against other RL methods. It achieve the best results compared to other RL methods, but still worse than IL methods.

strengths:
1. The paper developed BBMDP tailored for B&B search that allows the application of a boarder range of developed RL methods.
2. The empirical results look promising in comparison to other RL methods.
3. The paper is well-written and easy to follow.

weaknesses:
I don’t see major weaknesses, but have a couple of questions that could be of potential improvement to the paper:
1. Can you show the sample complexity of the methods compared to previous ones?
2. 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.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730963070235

thread_type:
official_review

<thread_object>
creator: reviewer_hrbm

<content>
summary:
This paper studies learning efficient branching strategies by reinforcement, and introduces B&B MDPs, a principled vanilla MDP formulation for variable selection, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B&B heuristics. The proposed method defines a Bellman optimality operator to unlock the full potential of approximate dynamic programming algorithms. On easy instances, DQNBBMDP consistently obtains best performance among RL agents

strengths:
This paper overperforms the previous RL agents while narrowing the gap with the IL approach.

weaknesses:
1. The primary innovations of BBMDP are unclear.
2. The experiments are conducted on a relatively small scale. The medium instances require only 1 minute to solve.
3. BBMDP's performance is not significantly superior to other RL methods. It is even inferior on the medium dataset.

questions:
1. Could you clearly differentiate between BBMDP and TreeMDP?
2. Regarding the statement: “Yet, if the performance of IL heuristics are capped by that of the suboptimal branching experts they learn from, the performance of RL branching strategies are, in theory, only bounded by the maximum score achievable.” What does "suboptimal branching experts" refer to? Is it the strong branching rule?
3. On page 2, line 91, there's a mention of “Since ρ necessarily defines a total order on nodes.” Given that node selection and variable selection influence each other, what does it mean to have this fixed order?
4. Could you conduct tests on larger datasets, similar to those used by Gasse et al.?
5. Would it be possible to provide additional metrics, such as wins and P-D convergence plots?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732286574753

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
BBMDP primary innovations

comment:
Three reviewers have expressed concerns about the primary innovations of BBMDP, particularly in relation to the TreeMDP framework. These general concerns are addressed in this section. To put it shortly, the main difference between BBMDP and TreeMDP, is that BBMDP is a MDP, while TreeMDP is not. In fact, BBMDP, preserves the training convergence properties brought by the TreeMDP framework, along with fundamental MDP properties. 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.

When training neural networks to learn efficient branching strategies, the choice of state representation function is key. In their seminal work, Gasse et al. (2019) introduced bipartite graph representations for encoding MILPs, demonstrating their effectiveness in learning to imitate strong branching decisions at each node of the branch-and-bound process. In TreeMDPs, Scavuzzo et al. (2022) define states as B&B nodes, allowing to reuse the bipartite graph representation and graph convolutional architecture introduced by Gasse et al. (2019) to learn efficient branching strategies by reinforcement. However, TreeMDPs are not MDPs, as they do not define a Markov process on the state random variable: a TreeMDP transition yields two future states, and is hence not a stochastic process on the state variables. In our work, we define BBMDP, a principled MDP formulation for variable selection in B&B. In particular, we define state as the entire B&B tree, not just the current node. Consequently, we cannot use MILP bipartite graphs to represent MDP states, nor use graph convolutional neural networks to learn policies or value functions directly. A potential solution is to represent B&B trees as hypergraphs, where each B&B node is encoded by its corresponding MILP bipartite graph. However, this approach faces two significant challenges: designing an efficient function approximator for such a complex data structure, and mitigating the redundancy in this representation, which leads to significant computational overhead. This is one of the reasons why (Etheve et al. 2020) and (Scavuzzo et al. 2022) considered the standard MDP framework impractical for learning branching strategies. In Section 3.2, we propose a principled solution to this issue by demonstrating that, in a DFS context, the V-value of a BBMDP state can be decomposed as the sum of the W-values of all its open nodes. Additionally, we show that these W-value functions can be learned by traditional approximate value iteration algorithms. As demonstrated in Section 3.3, this allows to train GCNNs via Q-learning to approximate proxy value functions, using bipartite graphs to represent B&B nodes, and ultimately to derive greedy policies for BBMDPs. In Section 3.4, we highlight the advantages of BBMDP over TreeMDP by presenting a concrete example in which TreeMDP results in inconsistent learning schemes. Finally, our computational experiments presented in Section 4 further supports the adoption of BBMDP over TreeMDP, as the DQN-BBMDP agent clearly outperforms TreeMDP agents on both training and generalization instances of the Ecole benchmark.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732728273740

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Furter computational results

comment:
Three reviewers have inquired about the generalization capacity of our agent on more challenging instance benchmarks. In response to the reviewers' request, in Appendix H, we include further computational results on hard instance benchmarks as defined in Gasse et al. (2019). We observe that while the IL expert demonstrates reasonable generalization capability, achieving performance comparable to SCIP on hard instance benchmarks, all RL baselines perform poorly, with none managing to outperform the random agent across the four benchmarks, as shown in Table 5 p.21. This underscores the limited generalization capacity of current model-free RL agents to higher-dimensional instances, and highlights the need to adapt model-based RL approaches to the B&B setting, by leveraging the BBMDP framework.

In response to the reviewers' request, we have also updated the computational results for the easy and medium instance benchmarks presented in Table 1, now including performance scores obtained across 100 instances and 5 seeds. These computational results are consistent with the ones presented in prior versions. Per-benchmark standard deviations can be found in Table 7 in Appendix H. 

Finally, in order to better differentiate between baselines across easy, medium and hard instance benchmarks, we include additional performance metrics such as wins and average baseline rank, as shown in Table 6. The performance ranking derived from these supplementary metrics is consistent with the one discussed in Section 4.3, based on the computational results presented in Table 1.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper describes a new RL technique to obtain a good branching heuristic for B&B applied to ILP problems.  It claims to improve the state of the art of RL techniques for branching.  The strengths of the paper include a challenging problem and some interesting ideas.  The main weakness of the paper is the weak performance of the approach that is worse than some other RL techniques on hard instances and worse than imitation learning in general.  The rebuttal and the revised paper clarified many things and improved substantially the experiments.  However, given that the main claim of the paper is that the proposed technique improves on previous RL techniques, but the results on hard instances show the opposite, this work is not ready for publication.  Just to be clear, this is not just a question of results, but there needs to be a clear justification for why the proposed technique should improve with respect to RL alternatives.  The paper suggests that the proposed technique is based on a proper MDP formulation in contrast to previous formulations, but does this does not seem to help empirically.  Similarly, the paper justifies the investigation of RL techniques on the basis that they are not limited to a suboptimal expert, but the imitation learning techniques still dominate.  This means that some other factor is at play.  The authors are encouraged to understand what are the main factors of success that help imitation learning and other RL techniques outperform their technique in hard instances.