A Markov Decision Process for Variable Selection in Branch & Bound

3. We thank the reviewer for prompting us to broaden the discussion. First, we would like to emphasize, as noted by the reviewer, that our contribution is primarily theoretical in nature: our goal is to develop a principled MDP formulation for variable selection in B&B that supersedes TreeMDP. Accordingly, our experimental focus was to demonstrate the performance gains of DQN-BBMDP relative to prior RL baselines from the literature, all of which were trained within the TreeMDP framework. That said, we agree that exploring the implementation of a broader range of RL algorithms within the BBMDP framework is a promising direction for future research. In particular, we believe that a specific class of policy iteration algorithms —namely, MCTS-based approaches from the AlphaZero family— could prove especially effective in the B&B setting. [2] In fact, in the context of complex combinatorial board games, the integration of value and policy networks with lookahead search via Monte Carlo Tree Search (MCTS) has been shown to guide action selection towards high-value states, effectively mitigating exploration and credit assignment issues arising from the sparse-reward environment setting. As learning variable selection in B&B is faced with the same predicaments that arise in combinatorial board games, namely sparse and delayed rewards, long planning horizons and highly structured combinatorial state-action spaces, we believe that adapting MCTS-based algorithms to the B&B setting represents a promising avenue for advancing RL-based branching strategies. Interestingly, by providing a principled formulation of variable selection in B&B, the BBMDP framework naturally enables the derivation of a policy improvement operator via MCTS. In contrast, as highlighted on line 651 in Appendix H, TreeMDP is fundamentally incompatible with MCTS-based planning. In fact, by discarding the temporal perspective of B&B, TreeMDP introduces inconsistencies that prevent search algorithms such as MCTS from being effectively adapted to variable selection, thereby hindering the integration of model-based planning techniques into the B&B framework.

We now turn to addressing the remaining questions raised by the reviewer.

1. Importantly, BBMDP does not introduce any additional computational or memory overhead beyond what is already required by the MILP solver itself. In fact, regardless of the MDP formalism used to model the branching decision process, the underlying solver (in our case, SCIP) must keep track of all open nodes in the B&B tree to ensure both correctness and effectiveness of the solving process, independently of whether this information is ultimately utilized by the branching agent. Moreover, as discussed in lines 231-234 of the paper, under DFS the optimal policy can be retrieved simply from the information associated with the current B&B node, by acting greedily with respect to the optimal $\bar{Q}$-function. Hence, to ensure a fair and rigorous comparison with prior IL and RL baselines, our DQN-BBMDP agent retains the same observation function and neural network architecture as used in previous works.

2. Unfortunately, we only trained our DQN-TreeMDP and DQN-BBMDP baselines for values of $k$-step return in {1, 3}. Despite the shortness of the discussion period and the substantial training time of our RL agents, we will do our best to include computational results for more comprehensive values of $$k by the end of the author-reviewer discussion period. In any case, we would be happy to include these additional results in the final version of the paper, should the review process permit it.

3. The HL-Gauss loss is defined by a total of four parameters. The first two, $z_{min}$ and $z_{max}$ specify the support of the value function. These are not standard tunable hyperparameters, as they are tightly constrained by the B&B tree sizes encountered during both training and testing. As discussed in lines 594-601 of the paper, we chose $z_{min} = -1, z_{max} = 16$ to cover the range of observed tree sizes in the Ecole benchmark. Moreover, we fixed the number of histogram bins to $m_b = 18$ in order to maintain unit-width bins. Finally, the standard deviation was set $\sigma=0.75$, following the choice of Farebrother et al. This correspond to spreading the Gaussian probability mass over approximately 6 bins, a choice that proved robust across different benchmarks in their study. Overall, none of these parameters required particular tuning for HL-Gauss to achieve strong performance.

[2] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., ... & Hassabis, D. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140-1144.

We thank the reviewer for their valuable time and feedback. We start by addressing the main concerns raised by the reviewer.

1. We emphasize that our DQN-BBMDP implementation differs from the DQN-TreeMDP baseline in only two aspects: the use of the BBMDP formulation and the adoption of the HL-Gauss loss. Moreover, as illustrated in Figure 3, TreeMDP and BBMDP induce equivalent learning updates when trained following 1-step temporal difference targets. Hence, to disentangle the contribution of each innovation, we report results for agents trained with both $k=1$ and $k=3$ step returns.

We believe this extended ablation study now exhaustively covers all meaningful combinations of DQN-BBMDP and DQN-TreeMDP. As discussed in Section 4.2, these results support two key conclusions: (1) the majority of the performance gains in DQN-BBMDP stem from the use of the HL-Gauss loss; and (2) when training over multi-step rollout trajectories ($k>1$), the BBMDP formulation leads to further performance improvements over the $k=1$ baseline, whereas TreeMDP results in a performance degradation relative to its own $k=1$ baseline. This observation is consistent with the claims made in lines 49-62 of the paper.

2. We thank the reviewer for raising their concern. We agree that the reliance on DFS is a limitation of our current approach, as DFS is known to be suboptimal compared to the sophisticated node selection heuristics implemented in MILP solvers. Nevertheless, we believe two observations help put this limitation into perspective.

• First, we stress that despite relying on DFS, our DQN-BBMDP agent clearly and consistently outperforms the DQN-Retro baseline, which was specifically designed to enable learning to branch under SCIP’s default node selection policy. As discussed in lines 620-624 in Appendix F, this provides compelling evidence that, although DFS is generally expected to hinder the training performance of RL agents, the theoretical guarantees brought by DFS in BBMDP enable to surpass the prior state-of-the-art non-DFS agents. This observation is consistent with the findings of Etheve et al. [1], who showed that efficiently optimizing the branching policy has a substantially greater impact on B&B performance than optimizing the node selection policy.
• Second, while the theoretical properties derived in Section 4.3 are specific to the DFS setting, we emphasize that the BBMDP formulation introduced in Section 3.1 remains valid under any node selection policy. This is in contrast to TreeMDP, which is not consistent outside of the DFS regime. Therefore, BBMDP provides a principled foundation for future work that seeks to integrate more elaborate node selection strategies, beyond DFS. Crucially, enabling such approaches will require the development of scalable observation functions capable of efficiently encoding the rich, structured information present in evolving B&B trees.

[1] Etheve, M. (2021). Solving repeated optimization problems by Machine Learning (Doctoral dissertation, HESAM Université).

We thank the reviewer for their valuable time and interest in our work. We carefully examined the datasets shared in the official implementation repository of Wang et al. (https://github.com/MIRALab-USTC/L2O-HEM-Torch) and found that the production planning instances referenced by the reviewer were, in fact, the only ones missing from the public release. If the reviewer is aware of an alternative source for obtaining this instance dataset, we would be grateful for their guidance.

• We appreciate the reviewer’s concern but believe it may stem from a misunderstanding. Reinforcement learning fundamentally addresses sequential decision-making problems, which are most commonly modeled as Markov Decision Processes (MDPs). In order to apply an RL algorithm to a given problem, it is essential to first define a corresponding MDP formulation that faithfully captures the problem's dynamics and objectives. Therefore, the central contribution associated with BBMDP is to restore the temporal MDP perspective that was explicitly set aside in the recent TreeMDP framework. In fact, as discussed in lines 255-256, by discarding the notions of temporality and sequentiality which are core to both MDPs and B&B, TreeMDP fails to describe variable selection accurately in the general case. This is exemplified in Figure 3, as applying the TreeMDP dynamics for $k$ consecutive steps produces B&B trees that do not reflect the true internal state of the B&B process. As a result, TreeMDP’s structural limitations fundamentally restrict the range of RL algorithms that can be effectively applied in B&B. In contrast, as discussed in lines 264-267 of the paper, the BBMDP framework allows to leverage any traditional RL algorithm for the task of learning to branch in B&B, including algorithms that were not compatible with the previous TreeMDP framework, such as k-step temporal difference, TD($\lambda$), along with MCTS-based algorithms from the AlphaZero family.
• We are unsure about the specific argument the reviewer intends to make, but we believe the confusion may arise from a conflation of the roles played by the branching and node selection heuristics. In both BBMDP and TreeMDP, the action set consists of the set of fractional variables in the LP relaxation of the current node, i.e. the branching candidates. In contrast, the choice of which node to expand next from the pool of open nodes is delegated to the node selection policy $\rho$, which operates independently of the branching decisions. As made explicit in lines 104–106 of the paper, our objective is to optimize the branching policy while keeping the node selection policy fixed. As in TreeMDP, we adopt $\rho$ = DFS as the node selection policy, in order to enable the decomposition of B&B episodes into independent subtree trajectories. This is thoroughly exposed in section 3.2. This design choice helps mitigate credit assignment issues by reducing the typical length of episode trajectories logarithmically with respect to the size of the whole B&B tree. Hence, the branching decision process in itself is equivalent in both TreeMDP and BBMDP, in particular, there is no computational or memory overhead associated with the choice of BBMDP over TreeMDP as both frameworks are designed to optimize branching policies over subtree trajectories. It is possible that we may have misunderstood the reviewer’s concern. If so, we would be happy to address it in more detail, and we kindly invite the reviewer to reformulate their concern for clarification.

We sincerely thank the reviewer for taking the time to engage with our work. We appreciate the feedback, and we provide below detailed responses to the concerns raised.

1. We agree that clear and consistent notation is essential, particularly at the intersection of B&B and RL, where symbolic overload can easily arise. Throughout the paper, we have aimed to keep the notation as concise and consistent as possible. That said, we acknowledge that the inclusion of a dedicated nomenclature table could further improve readability. We would be happy to include a glossary in the revised version to help readers quickly reference key definitions from both the MILP and MDP frameworks.

• We thank the reviewer for their suggestion. We agree that, given additional space, incorporating a summarized version of the side-by-side comparison between BBMDP and TreeMDP from Appendix H into the main body of the paper would help further clarify the key distinctions between the two frameworks. That said, we would like to emphasize that we have made a consistent effort to highlight these differences throughout the main text, for example, in lines 157–164, 183–186, as well as in Section 3.4 (BBMDP vs. TreeMDP), where Figure 3 provides a clear visual illustration of the differences in learning updates induced by the two frameworks.
• We thank the reviewer for this helpful observation. We understand that navigating the appendix may be challenging in its current form. To improve clarity and accessibility, we would be happy to reorder the appendix sections to match the order in which they are first referenced in the main text. This reorganization should help ensure that the supplementary material is more naturally aligned with the reader’s progression through the paper.
• We thank the reviewer for pointing this out. Indeed, the HL-Gauss cross-entropy is introduced in line 251 with limited context in the main body of the paper, which may leave readers unfamiliar with this technique seeking additional clarification. Our intent was to keep the main text focused on the core conceptual contribution, namely, the formal derivation of a MDP formulation of variable selection in B&B, while relegating implementation and technical details to the appendix. That said, we agree that, given additional space, the motivation behind this design choice would be more appropriately introduced in the main text.
• We thank the reviewer for raising this question. As stated in lines 180–182 of the paper, our choice of r=−2 is purely cosmetic, intended to align the cumulative reward of a BBMDP episode with the actual size of the corresponding B&B tree, thereby simplifying theoretical interpretation. In fact, setting $r=−2$, $r=−1$, $r=−10$, or more generally $r=−k$ for any positive constant $k$ yields strictly equivalent optimal branching policies under the BBMDP formulation. If there are other specific modeling choices the reviewer believes should be clarified, we would be happy to elaborate further.
• We thank the reviewer for raising their concern. However, we would like to clarify that the BBMDP workflow follows exactly the same structure as the B&B workflow depicted in Figure 2. As such, we believe that adding an additional figure would likely be redundant.
• We thank the reviewer for raising this point. Unfortunately, there is no universal metric to quantify the intrinsic difficulty of MILP instances. Table 3 in Appendix A reports statistics such as the number of variables and constraints, which can offer some intuition but are not always reliable indicators of solving complexity. In practice, a more informative proxy for instance difficulty is the solving time required by a general-purpose MILP solver. In this regard, the performance of the SCIP baseline across the Ecole benchmark, as reported in Table 1, provides a reasonable empirical estimate of the relative difficulty of the instances considered.

We thank the reviewer for their valuable time and interest in our work. We address the two questions raised by the reviewer in order.

1. We use the term opposite in its mathematical sense, referring to the additive inverse: for any real number $x \in \mathbb{R}$, its opposite is $−x$. We hope this clarifies the definition of $\bar{V}^\pi$: $\bar{V}^\pi (s_t, o_i)$ is defined as the opposite size of $T(o_i)$, the B&B subtree rooted at node $o_i$, obtained when applying the branching policy $\pi$ and the node selection policy $\rho$ from state $s_t$. In our work, we show that under DFS, the value of $\bar{V}^\pi (s_t, o_i)$ in fact only depends on $o_i$ and $\bar{x}_{o_i}$, the incumbent value at the time when the node $o_i$ is processed by the B&B algorithm. Specifically, this time step is denoted $\tau_i$ in line 204 of the paper.
2. We thank the reviewer for prompting us to broaden the discussion. As noted in our conclusion, we believe that one key reason for the relatively limited generalization capacity of DQN agents to higher-dimensional MILPs—compared to the IL baseline—is that their decisions are greedily derived from evaluating Q-values over the entire action set. Since Q-networks are trained on MILP instances with structurally lower associated B&B trees, DQN policies are more prone to suffer from out-of-distribution effects when evaluated on more complex instances. We therefore agree with the reviewer that exploring, beyond REINFORCE, more advanced policy gradient algorithms that directly learn branching policies is a promising research direction. In particular, we believe that a specific class of policy iteration algorithms —namely, MCTS-based approaches from the AlphaZero family— could prove especially effective in the B&B setting. [1] In fact, in the context of complex combinatorial board games, the integration of value and policy networks with lookahead search via Monte Carlo Tree Search (MCTS) has been shown to guide action selection towards high-value states, effectively mitigating exploration and credit assignment issues arising from the sparse-reward environment setting. As learning variable selection in B&B is faced with the same predicaments that arise in combinatorial board games, namely sparse and delayed rewards, long planning horizons and highly structured combinatorial state-action spaces, adapting MCTS-based algorithms to the B&B setting represents a promising avenue for advancing RL-based branching strategies. Interestingly, by providing a principled formulation of variable selection in B&B, the BBMDP framework naturally enables the derivation of a policy improvement operator via MCTS. In contrast, as highlighted on line 651 in Appendix H, TreeMDP is fundamentally incompatible with MCTS-based planning. In fact, by discarding the temporal perspective of B&B, TreeMDP introduces inconsistencies that prevent search algorithms such as MCTS from being effectively adapted to variable selection, thereby hindering the integration of model-based planning techniques into the B&B framework.

[1] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., ... & Hassabis, D. (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419), 1140-1144.

After reading the other reviews, I remain positive about the paper and would like to keep my score unchanged.