Reinforcement Learning for Node Selection in Branch-and-Bound

First and foremost, we thank the reviewer for his time. We thank the reviewer for noting our improvements on one of the core aspects of the branch-and-bound algorithm. > 1) Reinforcement Learning provides an advantage over Imitation Learning, It is not really possible for our methods to use an off-the-shelf imitation learning approach due to one of our (implicit) core assumptions: The reinforcement learner is going to “discover” novel problems during search which were not originally specified, i.e. while we only generate TSP instances, due to the branching and cutting inside the algorithm, the model will still observe sub-trees which have significantly different structure. This is why we can get away with training only on 200 synthetic instances, while prior art often uses 100k across different problems. However, this also means that imitation learning algorithms are going to get stuck (if they work well) as they are not going to explore as much. Further, using off-the-shelf imitation learning models is not possible due to how the model represents the environment: For instance, which future actions a model has fully depends on which past actions were performed, i.e. you have #leaves “actions”, and which actions you have available depends on the prior actions. This means behavioral cloning by e.g. minimizing the KL-divergence between agent and expert distributions is simply not possible, because after two or three steps the distributions between them will be almost fully disjoint: Even the domain of the expert’s probability density function (i.e. set of leaves) might be different from what the agent explored (meaning that e.g. the KL-divergence would always be infinite). This does not mean imitation learning is fully impossible, but it does mean that imitation learning would need specific algorithmic adaptations to work in this setting. In that sense the advantage of Reinforcement Learning over Imitation Learning is that this policy is trainable _at all_ using standard techniques. We have clarified this in our methods section. Were we able to clarify your concerns? > 2) considering the entire tree state is better than just considering isolated nodes. These are points which distinguish authors' work from prior work. Unfortunately, authors compare against only SCIP's default node selector, and previously proposed algorithms are not considered. Just considering isolated nodes it is not possible to design a node selection policy as node selection specifically relies on the relative difference between the quality of two nodes. This is why Labassi et al had to phrase their "node local" representation as a comparison between two nodes as individual nodes are fundamentally not capable of selecting their own priority in isolation. The closest thing we can try is setting our message-passing iterations to zero, which means that only the pathwise sums are used to build the tree representations. While these are still global representations, this would allow one to test whether the quality of the non-local embeddings has significant effects on the overall policy's quality. Thank you for discussing this point, we will run these experiments and update the paper as soon as the results are ready (soon). You further note that a comparison against Labassi et al would have been useful: This is true, however benchmarking other learned node selectors proved challenging: The major piece of prior art is Labassi et al’s “Learning to Compare Nodes in Branch and Bound with Graph Neural Networks”. Unfortunately this method is hard-coded on SCIP version 7, while we rely on SCIP version 8. Considering that “The SCIP Optimization Suite 8.0” (https://or.rwth-aachen.de/files/research/repORt/scipopt-80.pdf) estimates the difference between SCIP 7 and SCIP 8 at up-to 50%, meaning that labassi’s method loses simply due to being implemented in a 2 year old MILP framework (as a side note: Labassi also only works for Linear Problems, so would not even apply to our nonlinear benchmarks). Considering that SCIP has been the most dominant open-source MILP solver for over a decade (see e.g. https://plato.asu.edu/bench.html), we think that benchmarking against it is a fair representation of the overall performance (i.e. we consider the SOTA MILP solver, rather than the SOTA under the Deep Learning heuristics specifically).

Once again, thank you for your remarks regarding local vs global representations! We conducted additional experiments by training an additional agent without the GNN (i.e. zero message passing steps), to test the performance in a “minimally global” setting. Note that completely independent node predictors do not work, as without correlating nodes at least pairwise, no node can determine whether it is “the most optimal” simply because the node does not know which other options exist. Testing the model without message passing, gave some interesting insights. Firstly, the model without the GNN is considerably more noisy; so much so that benchmarking on our tests sets does not really make sense: Running the same model 3 times on TSPLIB essentially yields 3 different results. Considering only the cases where the GNN-free model reaches low optimality gaps, the model needed considerably more nodes than the baseline or our model with GNN to reach comparable performance (roughly 30%, but that number is prone to noise). Secondly, models trained without a GNN diverge on the training set: Starting off at a reward of roughly zero, it diverges to a reward of -0.2 (i.e. 20% worse than SCIP) by the end of training. We have added these additional details in appendix F. Thank you once again for your pointer and we would be excited to answer additional questions!

We first and foremost want to thank the reviewer for his time. Thank you for highlighting the strengths of our paper in the form of global tree representation, our thorough benchmarking and supplemental information. > The strong motivation leads to a much larger cost in carrying out the algorithm, especially when it involves recursion.. However, it’s not clear from the paper as to why the authors only choose the upper bound as a factor of choosing. Would be interesting if they have a study –of maybe a comparison–leading to that choice. Due to the fact we do not train our model during inference (solving the benchmarking instances), the actual overhead is relatively small and mostly exists due to python being slower than optimized C code. We will clarify this in our revision. We could also parameterize the selection of leaves as a comparison, but that would ultimately yield a very similar objective. Ultimately we select max(leaves) one could also rephrase this as selecting the leaf such that it is the most optimal one wrt node comparison, but ultimately this would produce the objective “choose x such that x >= y for all leaves y”, which in turn amounts to maximization. We mostly chose to select based on maximum probability as it aligns well with prior research into reinforcement learning (i.e. the same as action selection in other environments as well). > To solve this complex problem, the proposed method has to be broken down into many phases as shown in Section 2. That raises a question about the practicality: can the method be integrated as one to make it end-to-end. If not yet, what are the factors needed or what changes to enable that. The graphic may be a little misleading here: The model is trained end-to-end. One has to think of SCIP as the RL “environment” which, just like all other RL environments , is thought of as a black box of input actions and output states. The actual selection policy is still trained end-to-end, just like in all other RL problems. > Another unclear aspect is the design of the reward method, e.g. why that formula in terms of motivation and explanation, and why not replace the term (“-1”) in Equation 5 with a constant C and study different values of it? The movement by -1 is simply mean-shifting the reward, just like one would do in a normal regression problem. Clipping has been a common technique for reward stabilization for a number of years (see e.g. Human-level control through deep reinforcement learning https://www.nature.com/articles/nature14236), especially in environments with a high possible range of rewards (such as Atari). We will make sure to reference this. > Why PPO? Would also be nice if comparing PPO to alternatives such as maybe TRPO, SAC, … We chose PPO due to its relative robustness and easy hyperparameter tuning. Off-policy methods like SAC are theoretically very appealing, but end up being hard to tune properly. As our method relies on a novel network design in a relatively under researched field, we opted to err on the side of robustness. > Yet another heuristics is to remove problems >100% or 0 gap. That begs a question on the quality of design including the reward function. This is simply a restriction one has when working with mixed-integer solvers such as SCIP: For some instances, SCIP’s solver and simplification routines are simply so advanced that the instance becomes trivial. At that point, one could keep this instance in the training set, but that would give misleading rewards to the model since even horrible selections could solve these instances simply due to the power of SCIP itself. On the other hand, there are problems that are so hard one can never make any progress on them, even if you had oracle node-selections. To improve the signal-to-noise ratio of our reward, we decided to filter those out proactively. This is presumably also one of the reasons why we can train a highly generalizing agent with only 200 instances, compared to e.g. Labassi which needed over 100k training instances across different problems. > Additionally: some monor typos [...] Thank you for the heads up! We will fix this as soon as we update the paper with the additional results mentioned for Reviewr hSJj.

First and foremost, we thank the reviewer for his time and effort and thank you for recognizing our main contributions. > There are existing related works that use graph neural networks for node selection in the branch-and-bound algorithm. The proposed method in this paper uses graph neural networks for tree representation, but the difference from the existing works is not clearly stated. We are not aware of any method that utilizes Graph Neural Networks to represent the branch and bound tree. Do you have references for relevant works? We are only aware of Graph representations of individual nodes in the tree, i.e. every node is one constraint graph between the node’s variables and constraints. One contemporary work published during this review cycle also uses an implicit tree representation, where instead of a timeseries the authors consider a “Tree series” where the MDP is modelled as a tree rather than a linear timeseries. They also consider the variable selection problem, rather than the node selection problem. Both of these approaches are completely orthogonal to ours: Our approach allows for TreeMDPs and nodes being represented as Graphs just the same. However, in some sense our approach can be seen as a transpose of the constraint-graph representation: Constraint graphs consider one node and anchor their graph to the instance, while our approach considers the entire graph and anchors its graph to the branch and bound structure. Our approach does not need this implicit correspondence between a nodes constraint matrix and graph, which allows us to tackle nonlinear problems in which no constraint matrix exists. Does the reviewer think it would be useful for us to make this connection as part of the paper? > The structure of RL such as states, actions, and reward function is not rigorously defined in the paper. This makes it harder to understand how the RL method works in the proposed method. We amended our paper to define this more thoroughly by giving the tuple of (State, Action, Reward) explicitly. > As the branch-and-bound algorithm proceeds, the number of nodes and the tree structure keep changing. Then, should the RL agent be trained from the scratch for every step of the branch-and-bound algorithm? This is not a problem due to how we design our model: Each state is an entire Tree that is parameterized as a graph neural network. After each state transition we still have a graph, which can be processed just the same using the same network and the same weights. The trick behind our algorithm is precisely that we can obtain a global view on the entire problem _without_ needing any modifications to the network (similar to how an LSTM works regardless of sequence length, our GNN works regardless of tree size and topology). Bundling the next remarks into one: > The discussion on the learning cost of the RL algorithm is required. How is the cost due to collecting the enough experiences for the convergence of the RL policy? It seems that the RL agent should be trained for each problem instance. Is this training of RL agent for each problem instance is mandatory to use the proposed method? [...] All experiments in this paper were performed using the same agent trained only on synthetic samples. This means that during benchmarking no training takes place at all: It just infers the correct next node by using the existing fixed weights. Overall our method was only ever trained on a small dataset of 200 instances of the traveling salesmen problem for what amounts to 16 epochs (generation details are in section 4.3). Specifically, the benchmarks are all done using a _single pretrained_ agent: The agent was trained once on the synthetic instances, the weights are frozen and then the agent is run on the different benchmark datasets. These datasets are substantially more complex, larger, and of completely different problems than what can be found in the training dataset. In practice, this would amount to e.g. SCIP being delivered with a pretrained policy which will be automatically used without additional training on novel problems. Other reviewers also noted this confusion, hence we updated the paper to make this more clear (see abstract)

First and foremost we want to thank the reviewer for their time and effort. > The definition of the reward is not rigorously defined. Specifically, the paper does not disclose how are the gap(node selector) and gap(scip) are calibrated. It could be Thank you, we did indeed not define this thoroughly enough. Your first variant is the correct one: We define the gap(node selector) and gap(scip) as the optimality gap reached by our selector or SCIP after the time budget is reached. This accounts for the fact that SCIP node-selection may be faster than our node selection, which wouldn’t be accounted for when measuring relative to the number of nodes solved. We updated the paper accordingly. > The score in evaluation need more justification. From my perspective, the most important goal of learning a node selection policy is finding good primal solutions. With this aim, none of the scores are a good choice. The second priority for a node selection policy is to close the duality gap. In this sense, "Utility/Nodes" is not good choices. The objective of our metrics was mostly to preserve the goal of minimizing the duality gap, while also accounting for the fact that the duality gap may have very different scales from problem to problem, hence the normalization using the SCIP baseline and zero-centering of the “our gap” / “scip gap” loss. We agree with you and the other reviewers, therefore we decide to also publish the shifted geometric mean of the duality gap for all instances in each dataset to give more of a global view of our methods performance. The reason we did not do so initially is due to the fact that shifted geomean does not work if infinite duality gaps are in the results. In the new results we model infinities as a duality gap of 10^20, just like SCIP would. > The paper consider a small threshold 45 seconds. This is a relatively small time budget for solvers to solve MIP problems. To demonstrate the learned policy is practical, the results with a longer running time should be reported. We also share your concern of our short runtime: We initially chose this runtime since we were mostly interested in the initial (most impactful) phase of node selection, and other works (such as Labassi et al.) only having an average solver time of less than thirty seconds, even on their largest instances. However, we do concede that evaluating with larger time budgets is very important: We have added additional runs on our real-world datasets with a time budget of 5 minutes for TSP, MINLPlib, and MIPLIB. For these tests we increase the number of nodes processed by our method from 250 to 650, as the longer overall runtime justifies running our selector for a longer time as well. As you can see, we still outperform the SCIP baseline despite only being trained on instances with a 45s time limit, usually even increasing the relative gap between our method and scip. > Only the results on benchmarks are provided in the paper. I am curious about the performance on the training data. We also added information on our training results in the appendix. We hope we managed to address all your concerns and are happy to discuss further.