TreeDQN: Learning to minimize Branch-and-Bound tree

However, the global upper bound can change dynamically during the search, which might influence the probability. Does this paper use optimal solutions as upper bounds? Could the authors provide further clarification on this assumption?

In our experiments, we use DFS node selection during training and switch to the default node selection strategy during testing. We also experimented with training using the default node selection strategy. We observed that the agent trained with the default node selection strategy performs slightly less, compared to our final setup, due to higher stochasticity and violation of the Markov property of the training environment.

We present Theorem 4.1 to support the statement that a reinforcement learning agent should be able to converge to an optimal policy in a fully observed tree MDP when the probabilities $p^+$ and $p^-$ do not depend on the state. Indeed, the branching process in the actual B&B solver may violate some initial assumptions like the Markov property or the independence of $p^+$, $p^-$ probabilities from the state. However, if the state does not contain the exact value of the global upper bound, we can not accurately predict the number of child nodes. Thus, we can consider probabilities $p^+$ and $p^-$ independent from the state to some extent. So, if the violation of initial assumptions is small enough, the agent should be able to converge to a well-performing policy, as we demonstrate in our experiments.

Exploring Limited Generalization Ability: In comparing the results presented in Table 5 and Table 3, it is observed that TreeDQN appears to exhibit less stability in the context of transfer tasks. Could you please offer insights or explanations regarding this phenomenon?

Thank you for raising an interesting question! We train the TreeDQN agent to optimize the geometric mean of the expected return. So rare, large trees may have a less significant impact on the final policy. It can be seen from the Probability-probability plot for the Maximum Independent Set task (Fig. 4) that the TreeDQN starts falling behind the IL agent when the tasks become harder (in the upper right corner). Thus, in complex transfer tasks, the TreeDQN agent may underperform.

A Traditional vs. RL-based Variable Selection Perspective

RL methods can find a new branching strategy that could perform better than the traditional methods for a specific distribution of tasks. We believe that RL methods can improve the performance of Branch-and-Bound solvers in areas that require frequent solving of similar MILPs. For example, when a logistics company ships goods to customers or when we need to allocate limited resources like human workers or computing resources of a data center. At the present time, human-designed heuristics are better for tasks when you need to solve problems with significantly varying complexity and type or have only several task instances of the same kind. However, the development of multitask and meta-learning approaches may extend the applicability of reinforcement learning methods.

Perhaps the biggest limitation is the assumption that the upper bound has to be derivable from the current node or known ahead of time. The authors assert that this (as well as more intricate node selection policies) lead to at most a moderate distribution shift, but never demonstrate this effect.

In our experiments we use DFS during training and switch to the default node selection strategy during evaluation. If we assume that the Strong Branching heuristic is close to optimal in our benchmark tasks (Combinatorial Auction, Set Cover, Maximum Independent Set, Facility Location), we can estimate the maximum value of possible performance degradation as the difference between the performance of TreeDQN and Strong Branching:

Combinatorial Auction - 22%, Set Cover - 30%, Maximum Independent Set - 5%, Facility Location - 10%.

Another concern is regarding the difficulty distribution of instances. Random instance generation has been known to generate significant amounts of trivial instances compared to real-world equivalents. However, this is a limitation of most prior work on learnt variable selection rules as well.

In our work, we focus on the same tasks as previous works (Gasse, NeurIPS 2020, Scavuzzo, NeurIPS 2022) to fairly benchmark our method with methods from the literature. In the updated version of our paper, we added a more challenging Balanced Item Placement task (see general response and updated paper, Appendix D).

TreeDQN is also more expensive in terms of wall-clock-time than prior work (especially the IL agent), which can be seen in Figure 4. The paper does not make it clear whether this is due to TreeDQN using a different architecture, or TreeDQN simply creating more expensive nodes during branching.

Thank you for spotting this. We use the same Graph Convolutional Neural Network encoder architecture for all models in our benchmarks (IL, tmdp+DFS, FMCTS, TreeDQN). The TreeDQN is creating more expensive nodes during branching. It is clearly seen from the evaluation results on the Balanced Item Placement task (see Appendix D). In this task, all problem instances were finished by reaching a timeout. The TreeDQN agent solves much fewer LPs but achieves a much higher reward and much lower primal bound than the IL agent.

An important missing baseline in their comparisons is out-of-the-box SCIP, acting as an automatic state-of-the-art hand-crafted tradeoff between SB and cheaper heuristics.

We added SCIP to our evaluation results. Please see the general response and updated paper.

The paper needs an extensive re-write in terms of argumentation and clarity.

Thank you for providing detailed feedback! We corrected the issues. Please see the updated version of our paper.

Is the method run on CPU or GPU?

GPU

What is the performance of SCIP with default parameters on these instances (I.e. reliability pseudocost branching)?

Please see updated version of the paper

What is the model architecture (or more importantly: is it the same for all methods)?

We use the same Graph Convolutional Neural Network encoder architecture for all models in our benchmarks (IL, tmdp+DFS, FMCTS, TreeDQN).

Section 2.2 “Tree MDP” needs way more explanation.

We updated the background section and extended the description of Tree MDP. Please see the updated version.

Rather than just including a theorem about contraction in mean, the authors should have a main theorem that states the actual convergence guarantee that follows.

The convergence of Q-learning methods can be rigorously proved only for tabular MDPs, which is out of the scope of the present paper. To provide an intuition as to why our method should work, we prove the contraction in mean property of the tree Bellman operator.

My understanding is that this paper is methodologically very similar to Scavuzzo et al., and only differs in the mechanics of how the RL algorithm is trained.

Our method has two significant differences from the work of Scavuzzo et.al.:

1. Use of MSLE loss function. Distribution of tree sizes in the B&B method will always have a long tail (if we can not prune a tree, it will be a complete binary tree with the size growing exponentially with its depth). The MSLE loss function should generally work better than the MSE when predicting the size of the tree because it is more stable to outliers.
2. Our method is much more sample efficient than the method of Scavuzzo et.al.(tmdp+DFS). To make one gradient update tmdp+DFS needs to solve a batch of MILP tasks until completion. In our approach, we make as many gradient updates as the size of the tree. To further prove the quality of our method, we tested it on a challenging Balanced Item Problem from the ML4CO competition (NeurIPS 2022, see Appendix D). We show that our TreeDQN agent can get a mean reward higher than the Imitation learning baseline. Since solving a single MILP task in this problem takes 15 minutes, training a tmdp+DFS in a reasonable amount of time would be impossible.

No comparison is made to the default settings of any state-of-the-art solver (e.g., Gurobi, CPLEX, SCIP)

We added evaluation for the SCIP solver with the default set of parameters. Initially, we did not include it because the internal branching rules can make various modifications to the state of the solver, so it can not be considered a direct competitor to other methods. For more information see:

1. Discussion by Maxim Gasse (https://github.com/ds4dm/ecole/discussions/286#discussioncomment-2317487)
2. Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed-integer programming. In Operations Research Proceedings 2017, pages 165–170. Springer, 2018.

Overall the presentation did not convince me that this is a sufficiently novel contribution for ICLR.

We updated our paper to address the issues you mentioned. We would like to emphasize that our method is significantly more sample efficient than the method of Scavuzzo et.al. When solving a single MILP task, we can perform N gradient updates where N is the size of the resulting B&B tree, while tmdp+DFS needs to solve a batch of MILPs to make a single gradient update. This results in a much higher sample efficiency of our method. To further demonstrate the sample efficiency of our method, we trained and evaluated TreeDQN on the challenging Balanced Item Placement task from the ML4CO competition. The results in Appendix D demonstrate that our method outperforms Imitation Learning and Strong Branching in terms of total reward by a high margin. This result will not be possible with less sample-efficient methods since solving a single MILP instance of this problem requires 15 minutes.

I understand the first sentence, but what does the second sentence mean? What is “credit assignment”, and why is it/what does it mean for it to be biased upward?

Credit assignment is a problem in reinforcement learning when the immediate actions of an agent lead to rewards in the distant future, and the agent needs to figure out the connection between its actions and the delayed reward signal. We agree that this sentence is not clear and changed it to:

In the B&B search trees, the local decisions impact previously opened leaves via fathoming due to global upper bound pruning, which violates the Markov property.

Assuming that the training instances are easy (one needs to solve them optimally), how does the learned heuristic scale to larger problems?

In general, testing an ML model on out-of-domain tasks is hard. In our work, we demonstrate that our model can generalize to some extent to more complex tasks with a larger number of branching variables. The intuition of why it works is twofold:

1. The model learns a policy that can generalize to a larger number of branching variables.
2. During the solution, the domain of some variables is getting tightened to a single integer, and the actual amount of variables that can be branched decreases.

The number of seeds also seems to be small (5), for the kind of learning being done.

We follow Gasse, Exact combinatorial optimization with graph convolutional neural networks., NeurIPS 2020 and Scavuzzo, Learning to branch with tree mdps, NeurIPS 2022 and use 5 random seeds during testing. Using a much larger amount of seeds would be difficult since solving MILP tasks is time-consuming.

The main contribution of the paper, TreeDQN, is explained in a single paragraph in the main text.

Our method is described in 3 pages (pp. 4 - 6). It includes analysis of distributions of tree sizes, proof of convergence of the tree Bellman operator, discussion of our proposed loss function, implementation details (use of Double Dueling DQN adapted for tree MDP process), and training details.

Overall the background section could be re-written to use less space and pack more information to help the reader understand the work.

We updated the background section and improved the description of the Branch-and-Bound algorithm. Please see the updated version.

Why do we need to use DFS as node selection or set the global upper bound in the root to the optimal solution cost to guarantee the Markov property?

We improved this section. Please see the updated version. To guarantee the Markov property, we need probabilities $p^+$ and $p^−$ depending only on the parent state and action. However, they depend on the global upper bound (GUB), which can vary for different visiting orders. To enforce the Markov property, one can either set the GUB in the root node equal to the optimal solution or choose Depth First Search as a node selection strategy.

If GUB is set equal to the optimal solution, it will remain the same for every node of the tree since a node can not contain a solution better than the optimal.

We also can compute GUB for the descendant nodes if we know the parent node and use a deterministic top-down visiting strategy like DFS.

The gap between training and testing is due to assuming that one has the optimal solution in training? Why not use DFS and not assume that you have the optimal solution in training?

We do not assume that we have an optimal solution. In our experiments, we use DFS during training and switch to the SCIP default node selection strategy during testing since it is more efficient (but can violate the Markov property). In our experiments, we see that our TreeDQN agent performs close to the Imitation Learning agent and Strong Branching heuristic, so the gap between training and testing environments is sufficiently small.

How can more efficient heuristics for node selection also induce a gap between training and testing? And why is this important?

More efficient heuristics may violate the Markov property ($p^+$ and $p^-$ depend only on the current state). If they do, the reinforcement learning method may not learn an optimal policy since the state would not contain all the information to choose an optimal action.

It is important because we want to test and train our network on the same distribution. If we apply a different node selection strategy, it may lead to a different distribution of the number of descendant nodes, which could decrease the efficiency of our method. In our experiments, we do not see significant performance degradation.

Section 4 lists properties of a successful RL method for this problem, which includes off-policy and "work with tree MDP instead of temporal MDP". Why is it important to learn off-policy? We know of many successful on-policy algorithms for RL, what am I missing here? Why do they have to work with tree MDPs?

We updated this section. Solving MILP tasks is time-consuming. We need sample efficient methods to learn a variable selection policy. Off-policy methods are generally much more sample-efficient than on-policy since they can reuse arbitrary old experiences during training. In the paper, we updated this requirement from "Be off-policy" to “Be sample efficient”.

When solving a MILP task, the Branch-and-Bound solver splits the problem into subproblems and produces a binary tree. To train an RL agent, we need to map this tree to an episode. Considering the whole tree as a single episode under the tree MDP paradigm lets an agent directly optimize the size of the tree.

How is the training data generated?

For each task we have a distribution of parameters and randomly sample task instances from that distribution.

Do the problems differ in difficulty?

Yes. Depending on sampled parameters, the task could be easy (LP relaxation of the initial problem provides an integer feasible solution, so the size of the resulting B&B tree is 1) or require multiple branching decisions to find an optimal solution.

Do we have to optimally solve the problem to attain the Markov property to then train the model?

No. In our work, we use DFS during training and the default node selection strategy during testing.