Reinforcement Learning for Node Selection in Branch-and-Bound
Authors: Alexander Julian Mattick
Christopher Mutschler
Venue: Accepted by TMLR ()

Abstract: A big challenge in branch and bound lies in identifying the optimal node within the search tree from which to proceed. 
Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data.
In contrast to existing approaches that only consider isolated nodes, we propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state.
To achieve this, we train a graph neural network that produces a probability distribution based on the path from the model's root to its ``to-be-selected'' leaves. Representing node-selection as a probability distribution allows us to train a decision-making policy using state-of-the-art RL techniques that capture both intrinsic node-quality and node-evaluation costs.
Our method induces a high quality node selection policy on a set of varied and complex problem sets, despite only being trained on specially designed, synthetic travelling salesmen problem (TSP) instances.
Using such a \emph{fixed pretrained} policy shows significant improvements on several benchmarks in optimality gap reductions and per-node efficiency under strict time constraints.

Published in Transactions on Machine Learning Research (12/2024)
Reinforcement Learning for Node Selection in Branch-and- Bound
Alexander Mattick
alezander mattich@ris.fhomhhffr de christopher christopher. www.scerrrrreissssuaaooooooeeee
Christopher Mutschler
Fraunhofer IIS, Frounhofer Instttute for Integrated Circuits 1IS Nordostpark 84, 90411 Nürnbery, Germany
Reviewed on OpenReview: https: // openreview. net/ permformm? id= VrWl6yN41E
Abstract
A big challenge in branch-and-bound lies in identifying the optimal node within the search tree from which to proceed. Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive subnode selectors, or learned node selectors that rely on individual node data. In contrast to existing approaches that only consider isolated nodes, we propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state. To achieve this, we train a graph neural network that produces probability distribution based on the path from the model's root to its "to-be-sclocted" leaves. Representing node-selection a probability distribution allows us to train recision-making policy using state-of- the-art RL techniques that capture both intrinsic node-quality and node-evaluation costs. Our method induces high quality node selection policy on a set of varied and complex problem sets, despite only being trained on specially designed synthetic traveling salesmen problem (TSP) instances. Using such a fixed pretrained policy shows significant improvements on several benchmarks optimality gap reductions and per-node efficiency under short time limit of 45s and demonstrates generalization significantly longer 5min time limit.
state-of-the-art
1 Introduction
The optimization paradigm mixod integer programming plays a crucial role addressing a wide range of complex problems, including scheduling (Bayliss el al. 2017 process planning (Floudas & Lin 2005), and network design (Menon al.] 2013). prominent algorithmic approach employed solve these problems is brdnud-and-bound (BnB), which recursively subdivides the original problem into smaller sub-problems through variable branching and pruning based inferred problem bounds. BnB is also one of the main
algorithms implemented in SCIP (Bestuzheva et al. 2021 slate-of-the art mixed integer linear and mixed integer nonlinear solver.
An often understudied aspect is the node selection problem, which involves determining which nodes within the search tree are most, promising for further exploration. This due the intrinsic complexity of understanding the emergent effects of node selection on overall performance for human experts. Contemporary methods addressing the problem of node selection typically adopt. a perspective per node (Yilmaz & Yorke-Smith 2021; He et al. 2014 Morrison et al. 2016), incorporating varying levels of complexity and relying imitation learning (II.) from existing heuristics (Yilmaz & Yorke-Smith 2021 He et al.) 2014). However, they fail to fully capture the rich structural information present within the branch-and-bound tree itself.
We propose a novel selection heuristic that leverages the power bi-simulation: The BnB tree structure and expansion/prin /pruning dynamics are directly replicated inside our neural network model. We now employ reinforeement learning (RL) learn heuristic that naturally well aligned to the branch-and-bourd problem, Fig. The resulting method is able to take advantage of the inherent structure within the

---

Published in Transactions on Machine Learning Research (12/2024)
Branch and Bound Tree
Independent Node Processing
steps message passing (+ MLP))
Path Extraction
for each node
Pig (1%
NO
extract features
(1g)
E Be (t.,)
11
222
Ra
normalize
(g(()))
(g(
12
7L4
MLP processing
(n
Ag(
Poix V/ (or(he (aa)) 6rh2))
Pou V/ (r(hh ((N66n)) ((o6r))))
branching candidates rlg, fly, 144
Por 1/ (1 0u2) ((he(n)) ((w(0r))))
- tree-dependent node representations hy())))
representation
branching nade
Figure 1: Overview of our approach: (1) SCIP solves individual nodes and executes existing heuristics. (2) Features are extracted from every sarch-and-boune node and sent to individual normalization and embedding. (3) The node embeddings are subject to K steps of GNN message passing on the induced Iree-structure. The embeddings are projected to scalar weights and values using a Multi Layer Perceptron (MLP). (4) Based on the node embeddings, we generate root-to-leave paths, from which we sample the next node. The resulting node submitted SCIP and we return step
branch-and-bound algorithm, lcading to a superior genoralization compared to the seminal work by Labassi et al. )202)). This allows the RL policy to directly account for the BuB tree's dynamics.
We reason that RL specifically is a good fit for this type of training as external parameters outside the pure quality of node have to be taken into account. For example, a node A might promise a significantly bigger decrease in the expected optimality gap than second node B, but node A might take twice long to evaluate, making B the "correct" choice despite its lower theoretical utility. By incorporating the bi-simulation technique, we can effectively capture and propagate relevant information throughout the tree.
The main contributions of this paper are:
1. method for processing branch-and- bound trees of arbitrary size, which probabilistically samples leaves of the BnB tree by modcling the selection a root-to-lcaf traversal of the BnB tree,
2. way of sampling optimization instances of intermediary difficuly,,
3. a thorough time-limited benchmark on industrial-scale instances contained in TSPLIB, MINLPLib, and MIPLIB, and
4. an analysis of the learned node selector using explainable-AI Al techniques
To the best of our knowledge, we are the first to present a learned selection method that now only generalizes across instance types but that also applicable nonlinear mixed-integer optimization.
The rest of this article is structured as follows. Sect. describes branch-and-bound and Sect. 3 discusses related work. Sect. exxlains method, i.e., node representation, node selection agent, and how we generate training instances. Sect. discusses the experiments, and Seet. B discusses limitations. Sec. concludes.
2 Branch and Bound
BuB is one of the most effective methods for solving mixed integer programming (MIP) problems. It recursively solves relaxed versions of the original problem, gradually strengthening the constraints until it finds an optimal solution. The first step relaxes the original MIP instance into a tractable subproblem by dropping all integrality constraints such that the subproblem can later be strictified into a MIP solution. For simplicity, we focus our explanation to the case of mixed integer linear programs (MILP) while our method theoretically works for any type of constraint allowed in SCIP (see nonlinear results in Sec. 5.3.1
2

---

Published in Transactions on Machine Learning Research (12/2024)
and Bestuzheva et al. (0023) ) Concretely MILP has the form
PMILP min (nin o. y/ By 2 b, e z").
(1)
where 01 and 02 are coefficient vectors, A and B are constraint matrices, and x and y are variable vectors. The integrality constraint y 2d requires y to be an integer. In the relaxation step, this constraint is dropped, leading to the following simplified problem:
P Prelaxed = min cf vl By 2 b).
(2)
Now, the problem becomes a linear program without integrality constraints, which can be exactly solved using the Simplex (Dantzig 1982 or other efficient linear programming algorithms.
After solving the relaxed problem, BuB proceeds to the branching step: First, a non-integral ys is chosen. The branching step then derives two problems: The first problem (Eq. 3 adds a lower bound to variable Ui. while the second problem (Eq. 4 adds an upper bound to variable yi- These two directions represent the rounding choices to enforce integrality for y
Prolaxed min x v/ + By 2 b S [c]}
(3)
p Prelaxed min[c] c y/ + By W. 2 [c]}
(4)
The resulting decision tree, with two nodes representing the derived problems can now be processed recursively. However, naive recursive approach exhaustively enumerates all integral vertices, leading an impractical computational effort. Hence, in the bounding step, nodes that are deemed to be worse than the currently known best solution are discarded. To do this, BnB stores previously found solutions which can be used as lower bound to possible solutions. Tf node has lower bound larger than a currently found integral solution, no node in that subtree has to be processed.
The interplay these three coops-relxxations branching, and bounding forms the core of branch- bound. It enables the systematic exploration of the solution space while efficiently pruning unpromising regions. Through this iterative process, the algorithm converges towards the globally optimal solution for the original MTP problem, while producing optimality bounds at every iteration.
3 Related Work
Learning node selection, where learned heuristics pick the best node to continue from the search tree, has only rarely been addressed in research. Prior work that learns such node selection strategies made significant. contributions to improve the efficiency and effectiveness of the optimization.
Notably, many approaches rely on per-node features and Imitation Learning (II.). Otten & Dechter 2012 study the estimation of subproblem complexity as a means to enhance parallelization efficiency. By estimating the complexity of subproblems, the algorithm can allocate computational resources of parallel solvers more effectively. Yilmaz& & Sorke-Smith (202]) employ IL to directly select the most promising node for exploration. Their approach utilizes set of per-node features to train model that can accurately determine which node to choose. He et al. (2014) make use of support vector machines and IL to create a hybrid heuristic based on existing heuristics. By leveraging per-node features, their approach aims to improve node selection decisions. While these prior approaches yield valuable insights, they are inherently limited by their focus on per-node features.
Labassi et al. 2022 propose the use of Siamese graph neural networks, representing cach node as a graph that connects sariables with the relevant constraints. Their objective is to directly imitate an optimal diving oracle, which descends depth-first firstt towards a node containing a minimal value. This approach facilitates learning from node comparisons and enables the model to make informed decisions during node selection. This means that Labassi ct al. 2022 manages to study pairs of leaf-subproblems, rather than studying every
There are non- non-binare binary, "wide" branching strategies which we will not consider here explicitly. However, our approach is flexible enough to allow for arbitrary branching width. See Morrison et al. (2016) for an overview.
3

---

Published in Transactions on Machine Learning Research (12/2024)
subproblem in isolation. However, this method still does not utilize the high information content given by the tree structure itself: The search tree itself slowly gathers information in the form of, e.g,, cutting planes or the optimality of solutions close to (but not inside) the current subproblem's feasible set.
Aside of the work in learning node selection, there is also substantial work in learning different heuristics for branch and bound. One commonly learned component of branch-and-bound
the variable selection heuristic (Scavuzzo et al., 2022 Parsonson et al., 2022; Gasse et al.) 2019 [theve al.) 2020). Variable selection is the problem of which variable to apply the branch for the subproblems, i.e,, which y; to add
constraint to in Eqs 3 and 4 Other frequently learned heuristics include cut-selection methods (Tang
ct al. 2019 Wang et al. 2023 Paulus et al. 2022 Turner et al. (022). Cut selection is part of an extension
of branch-and-bound known as branch-and-cut which additionally adds constraints to sub-problerns that remove solutions that are feasible in a node's linear relaxation, but are infeasible in the original MILP model. Specifically, if x is a solution to the relaxed Equation [ but not a solution to the MILP Equation | a new constraint is placed into the relaxation that removes the found z from the problem. Such cuts are generally not unique. Cul selection is the process of picking the best cuts from a set of different feasible cuts. However, all these (types of) heuristics are orthogonal to our node selection problem: One can apply both our learned node selector as well as any combination of cut and variable selectors.
Compared to both cut and variable selection, node selection is severely under-researched due to its inherent complexity. While both variable selection and cut selection can be solved by studying a single sub-problen in isolation, node selection has to study the set of all possible uub-problems as a whole, which increases the complexity of building node selectors.
4 Methodology
We model the node selection process as a sequential Markov Decision Process (MDP). An MDP consists of a set of observable states s E S, a set of controllable actions a E A, a reward function R(s) describing the quality of an individual state s E S in isolation, and a (typically unknown) transition distribution T: x A + S that takes in a current state s E and an action a E A, proposed by a decision-making policy π S - A, and produces a distribution over new state s' S. The policy is usually thought of as a conditional distribution x (als) produeing the next action a A under the knowledge of the current state E S. Our objective is to find the policy optimal x², which maximizes the expected discounted sum of future rewards:
max 7
n" argmax, E
(5)
where 0 < y < 1 is a factor to trade immediate over future rewards (Sutton & Barto 2018
RL is the process of solving such MDPs by repeatedly rolling out x on an environment and using the resulting trajectories to find a policy π that maximizes the return. Several solvers for MDPs exist, such as Deep Q-Networks (DQN) (Mnih et al. 2015) or Proximal Policy Optimization (PPO) (Schulman et al. 2017 In this paper we use PPO to solve the MDP.
In our case, we phrase our optimization problem as an MDP, where states are represented using directed aanechand--ounn trees, actions a, are all selectable leaf-nodes, and the reward R is set according to Eq. b in Sec. 4.1 The transitions are given by the SCIP-solver and its heuristics: Given the current state (BnB tree) and the node selection by म, the SCIP solver produces new nodes as children of the selected ones, and prunes unnecessary nodes from the tree. To solve the MDP, PPO needs a representation for the policy π and model describing the caate-value-funee
defined as (ss) max, Q(s,, a) (see Schulman et al. (017)).
In our model, we represent the branch-and-boume tree as a directed Graph Neural Network (GNN) whose nodes and edges are in an 1:1 correspondence lo the branch-and--buund nodes and edges, see Sec. 4.2 This means that for every node in the BuB tree there is exactly one node in the GNN, and every connection in the BuB tree replicated in the GNN graph. As the BnB tree grows, the GNN graph grows as well, solving one of the biggest issues in node selection: Since the BuB tree grows and shrinks dynamically, the mumber of different node selections (= actions) changes drastically. One benefit of our GNN model is that the resulting
4

---

Published in Transactions on Machine Learning Research (12/2024)
directed graph automatically grows/shrinks the action space new nodes are added/pruned from the tree since the policy's action-space directly corresponds to the leaves of the GNN/BuB tree. This allows our network to phrase node selection explicitly as distribution over node-selections, rather than using implicit comparisons as in Labassi et al. (2022).
4.1 Reward Definition
A common issue in MIP training is the lack of good reward functions. For instance, the primal-dual integral used in Gasse et al. (2022) has the issue of depending on the scale of the objective, needing a primally feasible solution at the root, and being very brittle if different instance difficulties exist in the instance pool. Gasse jet al. (002)) circumvents these issues by generating similar instances, while also supplying a feasible solution at the root. However, to increase generality, we do not want to make as strict assumptions as having similar instance difficulties, introducing need for new reward function. A reasonable reward measure captures the achieved performance against a well-known baseline. In our case, we choose our reward, to be
r= r=- _appNooe Selector) -1).
(6)
gap(SCIP)
where (SCIP)IP) denotes the optimality gap reachable by the standard SCIP node selector in the set time limit (for us 45s), and gap(node selector) denotes the gap reachable by our method within the set time limit. This represents the relative performance of our selector compared to the performance achieved by SCIP
Intuitively, the aim of this reward function is to decrease the optimality gap achieved by our node-selector (i.e., gap(node selector)), normalized by the results achieved by the existing state-of- thee-arr node-selection methods in the SCIP (Bestuzheva et al. 2021 solver (i.e., gcp(SCIP)). This accounts for varying instance hardness in the datasct. Further, we shift this performance mcasure, such that any value > 0 corresponds to our selector being superior to existing solvers, while value 0 corresponds to our selector being worse, and clip the reward between (1,-1) to ensure symmetry around zero is commonly done in prior work (sce, c.g. MMni et al. (2015): Dayal et al. (2022)) ). This formulation has the advantage of looking at relative improvements over a baseline, rather than absolute performance, which allows us to use instances of varying complexity during training.
We also experimented with other metrics that aim to normalize for the complexity of the instance themselves (see Appendix Cp. We found that the reward metric as proposed here is the most stable to train and yields the best results w.r.t. minimizing the optimality gap.
4.2 Tree Representation
To represent the MDP's state, we propose a novel approach that involves bi-simulating the existing branch- and-bound tree using a graph neural network (GNN). Specifically, we consider the state to be a directed tree
T (V, F),, where V are individual subproblems created by SCIP, and E are edges set according to SCIP's node-expansion rules. More preciscly, the tree's root is the principle relaxation (Eq. D and its children are the two rounding choices (Eqs. 3 and 4p. BuB proceeds to recursively split nodes, adding the splits children to the node it was split from.
For processing inside the neural network, we extract features (sce Appendix A] from each node, keeping the structure intact: T = (extract(V). E). We ensure that the features stay at a constant size, independent from, e.g., the number of variables and constraints, to enable efficient batch-evahution of the entire tree.
For processing the tree T, we use messago-passing from the children to the parent. Pruned or missing nodes are replaced with constant to maintain uniformity over the graph structure. Message-passing enables us to consider the depth-K subtree under every node by running K steps of message passing from the children to the parent. Concretely, the internal representation can be thought of initializing ho(n) = æ(n) (with z(n) being the features associated with node n) and then running K itcrations jointly for all nodes n:
h (141 = (n)) + emb (l(le(())) + he (right((n))
(7)
2
5

---

Published in Transactions on Machine Learning Research (12/2024)
where left(n) and right(n) are the left and right children of n, respectively, (n(n) is the hidden representation of node after I. steps of message passing, and emb is function that takes the mean hidden state of all embeddings and creates an updated node embedding. Doing this for K steps aggregates the information of the depth-K limited subtree of n into the node n.
4.3 RL for Node Selection
While the GNN model is appealing, it is impossible to train using contemporary imitation learning techniques, as the expert's action domain (i.e., leaves) may not be the same as the policy's action domain, meaning that the divergence between these policies is undefined.
To solve this problem, we choose to use model-free rein learning techniques directly maximize the probability of choosing the correct node. State-of- State-of-the-art reinforcement learning techniques, such proximal policy optimization (PPO) (Schulman et al., 2017), need to be able to compute two functions: The value function V(s)= = m Q(s, a), and the likelihood function T [a]s)) PPO uses the value function to reduce the variance of the advantage computation. In our work, we utilize the Generalized Advantage Estimator (GAE) Schulman et al. 2015)) which provides a continuous mixture bootstrapped and Monte Carlo estimated advantages. As turns out, there are efficient ways to compute both of these values from a tree representation:
Firstly, we produce probability distribution of node-selections ei. actions) by computing the expected "weight" across the unique path from the graph's 's root to the "to-be-selccted" leaves. These weights are mathematically equivalent to the unnormalized log- log-probabilities of choosing leaf-node by recursively choosing either the right or left child with probability and - respectively. The full derivation of this can found in Appendix
Concretely, let n a leaf node in the set of choosable nodes E, also let P(r, n) be the unique path from the root to the candidate leaf node, with [P(r,n) describing its length. We define the expected path weight ('(n) to a leaf node & as
('(n) = [((r,))
Σ W(hx(u)).
(8)
uEP(r,))
Selection now is performed in accordance to sampling from a selection policy i induced by
[n| trce) softmax ((W"(n))Vn E (6)).
(9)
Intuitively, this means that we select a node exactly if the expected utility along its path is high. Note that this definition is naturally self-correcting as erroneous over-selection of one subtree will lead to that tree being completed, which removes the leaves from the selection pool 6.
Similar to the log-likel we parameterize the value function as root-to-lcaf sum, which is aggregated using a max(.) over paths.
[()s)) F(n]s)
(10)
n)]
(ee)))(frisee frightt|s) + (hx(()))s)) f(n)s) s) f(left] (s) +
(11)
V(s) = max (f(n) Vn E 88,
(12)
where f(h,) is a trained per-node estimator, f is the path-aggregated f-function, and 6 is the set of open nodes as proposed by the branch-and-bouud method. For an alternative parametrization of V--) that justifies the use of f as Q-function, see Appendix J
Since we can compute the action likelihood I (a]s), the value function V(s), and the Q-function Q(s,a), we can use any Actor-Critic method (like PPO (Schulman et al., 2017 or A3C MMnih et al. 2016 for training this model. We use PPO due to its ease of use and robustness.
According to these definitions, we only need to predict the node embeddings for cach node hgg (m), the per-node f-uunction (n)ss)))s) and the weight of each node W (ha (u)). We parameterize all of these ML.Ps (more architectural details can be found in Appendix

---

Published in Transactions on Machine Learning Research (12/2024)
This method provides low, but measurable overhead compared to existing node selectors, even if we discount the fact that our Python-based implementation is vastly slower than SCIP's highly optimized C-based implementation. Hence, we focus our model on being efficient at the beginning of the selection process, where good node selections are exponentially more important as finding more optimal solutions earlier allows to prune more nodes from the exponentially expanding search tree. Specifically we evaluate our heuristic at every node for the first 250 selections, then at every tenth node for the next 750 nodes, and finally switch to classical selectors for the remaining nodes
4.4 Data Generation & Agent Training
In training MIPs, a critical challenge lies in generating sufficiently complex training problems. First, to learn from interesting structures, we need to decide on some specific problem, whose e-g. salisfiability is knowable generating random constraint matrices will likely generate empty polyhedrons, or polyhedrons with many eliminable constraints (e-g., in the constraint set consisting of c² x S b and c'xx S b+ p with A 0 one constraint is always eliminable). This may seem unlikely, but notice how we can construct aligned vectors by linearly combining different rows (just like in LP-dual formulations). In practice, selecting a sufficiently large class of problems may be enough as during the branch-and-cut process many sub-problems of different characteristics are generated. Since our algorithm naturally decomposes the problem into sub-trees, we can assume any policy that performs well on the entire tree also performs well on sub-polyhedra generated during the branch-and-cut.
For this reason we consider the large class of Traveling Salesman Problem (TSP), which itself has rich use-cases in planning and logistics, but also in optimal control, the manufacturing of microchips and DNA soquencing (see Cook et al. (2011)). The TSP problem consists of finding a round-trip path in a weighted graph, such that every verlex is visited exactly once, and the total path-length is minimal (for more details and a mathematical formulation, see Appendix F
For training, we would like to use random instances of TSP but generating them can be challenging. Random sampling of distance matrices often results in easy problem instances, which do not challenge the solver. Consequently, significant effort is being devoted into devising methods for generating random but hard instances, particularly for problems like the TSP, where specific generators for challenging problems have been designed (see Vercesi et al. (2023) and Rardin et al. (1993)) ). However, for our specific use cases, these provably hard problems may not be very informative as they rarely contain efficiently selectable nodes.
To generate these internediary-difffeul problems, we adopt multi-step approach: We begin by generating random instances and then apply some mutation techniques (Bossek et al. 2019) to introduce variations, and ensure diversity within the problem set. Next, select the instance of median-optimality gap from the pool, which produces an instance of typical difficulty. The optimality gap, representing the best normalized difference between the lower and upper bound for a solution found during the solver's budget-restricled execulion, serves as a crucial metric to assess difficulty. This method is used to produce 200 intermediary-difice training instances.
To ensure the quality of candidate problems, we exclude problems with more than 100% or zero optimality gap, these scenarios present challenges in reward assignment during RL. To reduce overall variance of our training, the minimum number of nodes in the problems, discarding every instance with less than 100 nodes. This is essential as we do not expect such small problems to give clean reward signals to the reinforcement learner.
limit the ground-truth variance in optimality gap. Additionally, we impose constraint on
5 Experiments
For our experiments we consider the instances of TSPLIB (Reinelt 1991) and MIPLIB (Gleixner et al. 2021 which are one of the most used datasets for benchmarking MIP Trameworks and thusly form a strong baseline to test against. We further test against the UFLP instance generator by (Kochetov & Ivanenko 2005), which
TThis accounts for the "phasc-tramsition" in MIP solvers where optimality neods to be proved by closing the remaining branches although the theoretically optimal point is already found (Morrison et al. 2016). Note that with tuned implementation could run our method for more nodes, where we expect. further improvements.
7

---

Published in Transactions on Machine Learning Research (12/2024)
specifically produces instances hard to solve for branch-and-boun and against MINLPLIB Bussicck et al, 2003), which contains mixed inleger nonlinear progrums, to show generalization to vastly different problems.
We perform all our training and the experiments on a Ryzen 7 5800x3d CPU, where training completes after approx. 6h. After the model is trained on the synthetic TSP instances, we freeze the network and apply it to both the "in distribution" TSPLIB and the "out of distribution" UFLP. MINLPPLBB and MIPLIIB instances. This is in contrast to prior work such as those from Labassi al. (2022), who train separate models for all instance types and do not manage generalize to forcign instances (see Sec 5.4 Our source code is publicly available and can be used to reproduce the experiments We use the default hyperparameters as proposed by CleanRL (Huang et al. 2021
For our benchmarks on TSPLIB, UFLP, MIPLIB and MINLPLIB, we impose a time limit of 45s and 5min. We report the expected reward (Eq. 6), the geometric mean of the achieved gap for both our and the bascline mothod, and the win-rate of our method as defined by gap(ours) S gap(baseline) R For longer runs with a timelimit of 30min see Appendix D
5.1 Baselines
We run both our method and SCIP for 45s. We then filter out all runs where SCIP has managed explore less than nodes, as in these runs even perfect node selection makes no difference in performance. If we included those in our average, we would have significant number of lines where our node-selector has zero advantage over the traditional SCIP one, not because our selector is better or worse than SCIP, but simply because it wasn't 't called in the first place. We set this time-limit. relatively low as our prototype selector only runs at the beginning of the solver process, mcaning that over time the effects of the traditional solver take over.
Additionally, we also consider an evaluation with 5min time limit. For those runs, the limit until we switch to the naive node selector is set to 650 nodes to account for the higher time limit. In general, the relative performance of our method compared to the baseline increases with the 5min budget.
Finally, we also benchmark against the previous state-of-the-ars by Labassi et al. (0022), which represents optimal node selection as a comparison problem where a siamese network is used to compare different leaf nodes against each other and picking the "highest" node as the next selection.
5.2 Results
While all results can be found in Appendix we report an aggregated view for each benchmark in Table ! In addition our "reward" metric we report the winning ratio of our method over the bascline, and the geometric mean of the gaps at the end of solving (lower better).
For benchmarking and training, leave all settings, such as presolvers, primal heuristies, diving heuristics, constraint specializations, etc. at their default settings to allow the bascline to perform best. All instances are solved using the same model without any fine-tuning. We expect that tuning, e-g., the aggressiveness of primal heuristics, increases the performance our method, as it decreases the relative cost of evaluating a neural network, but for the sake of comparison we use the default parameters for all our tests. We train our node selection policy on problem instances according to Sec. 4.4 and apply it on problems from different benchmarks.
3Source code: httpp:///ithhn http:///ggttuuu...oo/tttaaaaaae haaaaataeee.irarrersesaaahhhaaaa
'All of these metrics give a slightly different view of the performance of our method: The reward metric is naturally balanced to weight the improvement relative to the difficulty of the problem reward captures the improvement over the baseline in percent (higher is better). The downside of this is that because reward is balanced, it will assign the same reward to improvement of 6gap 2.5gap to 0.5gap + 0.25gap, which can overemphasize the impact of easy to solve instances. Win-rate is supplementary metric showing the percentage of iustances where model beats the baselive. This can help distributed among the instances (higher better). Finally, comparing the geometric mean is
show how the improvements the gold-standard tool in measuring solver performancc (Bestuzheva ct al. 2021 In contrast to the reward metric, goometric means are specifically designed reject outliers increasing the robustness of the metric. We report both our geometric mean and the SCIP baseline's geometric mean (our gap < SCIP gap better).
8

---

Published in Transactions on Machine Learning Research (12/2024)
Table I: Performance across benchmarks (the policy only saw TSP instances during training). The reward is the normalized improvement over the bascline (Eq. 6 averaged over the benchmarking dataset, the win-rate shows how often our method produces a better (or in case of both methods reaching 0% gap equal) optimality gap, and the geometric means are the shifted geometrie means of optimality gaps computed over the benchmarking dataset.
Benchmark
Reward
Win-rate
geo-mean Ours
geo-mean SCIP
TSPLIB RRinnelt
1991
0.184 #0.52
0.50
0.931
0.957
UFLP (Kochetov Ivanenko
2005
0.078 10.19
0.636
0.491
0.520
MINLPLib (Bussieck et al. 2003
0.487 10.60
0.852
28.783
31.185
MIPLIB [Gleixner al. 2021
0.140 #0.69
0.769
545.879
848.628
TSPLIB @5min
0.192 10.51
0.600
1.615
2.000
MINI.Pib@5min
0.486 +0.60
0.840
17.409
20.460
MIPLIB@5mmnn
0.150 +0.69
0.671
66.861
106.400
First, we will discuss TSPLIB itself, which while dramatically more complex than our selected training instances, still contains instances from the same problem family as the training set (Sec. 5.2.1 Second, we consider instances of the Uncapacitated Facility Location Problem (UFLP) as generated by Kochetov & Ivanenko (2005)'s 's problem generator. These problems are designed to be particularly challenging to branch-and- bound solvers due to their large optimality gap (Sec. L.I. While the first two benchmarks focused specific problems (giving you notion of how well the algorithm does the problem itself) we next consider "'metaabenccmarrs""" that consist of many different problems, but relatively few instances of cach. MINLPLIB (Bussieck et. al., (2033 is mett--benchmark for nonlinear mixed-integer programming (Sec. 5.3. and MIPLIB (Gleixner et al. 2021) a benchmark for mixed integer programming (Sec. 5.3.2). We also consider generalization against the uncapacitated facility location problem using strong instance generator, see Appendix [.I] Our benchmarks are diverse and complex and allow to compare algorithmic improvements in state-of-the-art solvers.
5.2.1 TSPLIB
From an aggregative viewpoint we outperform the SCIP node selection by 20% in reward. However, the overall "win-rate" is only 50% as the mean-reward is dominated by instances where our solver has significant performance improvements: When our method loses, it loses by relatively little (e.g., g., att48: ours 0.287 vs. base 0.286), while when it wins, it usually does so by larger margin.
Qualitatively, it is particularly interesting to study the problems our method still loses significantly against SCIP (in four cases). A possible reason why our method significantly underperforms on Dantzig42 is that our implementation is just too slow, considering that the baseline manages to evaluate 40% more nodes. A similar observation can be made e1151 where the baseline manages to complete 5x more nodes. rd100 is also similar to Dantzig and ei151 the baseline is able to explore 60% more nodes. KroE100 is the first instance our method loses against SCIP, despite exploring a roughly equal amount of nodes. We believe that this is because our method commits to the wrong subtree early and never manages to correct into the proper subtree. Ignoring these four failure cases, our mothod either on par (up to stochasticity of the algorithm) or exceeds the baseline significantly.
It is also worthwhile to study the cases where both the baseline and our method hit optimality gap. Both algorithms reaching zero optimality gap can be seen somewhat of a special case, since soley looking at the solution value is insufficient to figure out which method performs better in practice. A quick glance at instances like bayg29, fri26, swiss42 or u1ysses16 shows that our method tends to finish these problems with significantly fewer nodes explored. This is not captured by any of our metrics since those only look at solution quality, not the efficiency of reaching that solution. If the quality of the baseline and ours is the same, it makes sense to look at solution efficiency instead. Qualitatively, instances like bayg29 manage reach the optimum in only 1 the number of explored nodes, which showcases significant improvement in 3 node-selection quality. It is worthh noting that, due to the different optimization costs for different nodes, it
9

---

Published in Transactions on Machine Learning Research (12/2024)
not always true that evaluating fewer nodes is faster in wall-clock time. In practice, "fewer nodes is better" seems to be a good rule-of-thumb to check algorithmic efficiency.
5.3 UFLP
The UFLP benchmark designed by Kochetov & Ivanenko (2005) spocifically built to be hard to solve by branch-and- aannch---d--ouudd solvers due to its large duality gap. Despite this, our method manages to outperform the baseline significantly. This is meaningful since this benchmark a specially designed worst-case scenario: The fact that our method still outperforms the baseline provides good evidence of the efficacy of the method.
5.3.1 MINLPLIB
We consider MINLPs. To solve these, SCIP and other solvers branching techniques that cut nonlinear (often convex) problems from a relaxed master-relaxation towards true solutions. We consider MINLPLib (Bussieck et al. 2003), a meta- benchmark consisting of hundreds of diverse synthetic and real-world MINLP instances of varying different types and sizes. As some instances take hours to solve even a single node, we filter out all problems with fewer than 5 nodes, as the performance in those cases is independent of the node-selectors performance (Full results Appendix L.4].
Our method still manages outperform SCIP, even on MINLPs, despite never having seen single MINLP problem before, see Table D Qualitatively, our method either outperforms is par with the vast majority of problems, but also loses significantly in some problems, greatly decreasing the average. Studying the cases our method loses convincingly (see Appendix 1.4] we find a similar case as in TSPLIB, where the baseline implementation is so much more optimized that significantly more nodes can get explored. We suspect the reason our method has the biggest relative improvements on MINLPs due to the fact that existing e.g. tasks.
pseudocost. based selection methods do not perform as well on spatial--rannc--ndd-bool
We expect features specifically tuned for nonlinear problems to increase performance by additional percentage points, but as feature selection is orthogonal to the actual algorithm design, we leave more thorough discussion of this to future work
5.3.2 MIPLIB
Last, but not least we consider the meta-benchmark MIPLIB (Gleixner et al. 2021 , which consists of hundreds of real-world mixed-integer programming problems of varying size, complexity, and hardness. Our method either close to or exceeds the performance of SCIP, see Table [
Considering per-instance results, we see similar patterns as previous failure cases: Often we underperform on instances that need to close many nodes, as our method's throughput lacks behind that of SCIP. We expect that more efficient implementation alleviates the issues in those cases.
We also see challenges in problems that are far from the training distribution, specifically satisfaction problems. Consider hanw-binpack44443 were the baseline yields an optimality gap of 0 while we end at toc. This is due to the design the problem: Instead of a classical optimization problem, this a satisfaction problem, where not an optimal value, but any feasible value is searched, i.e., we either yield a gap of (solution found), or gap of +oo (solution not found), as no other gap is possible. Notably, these kinds of problems may pose challenge for our algorithm, as the node-pruning dynamics of satisfying MIPs are different than the one for optimizing MIPs: Satisfying MIPs can only rarely prune nodes since, by definition, no intermediary primally valid solutions are ever found.
5.4 Comparison against "Learning to compare nodes"
Aside from comparisons against SCIP, we also compare against the previous state-of-the-art method by Labassi et al. (2022). One complication when benchmarking against Labassi et al. (2022) is that they assume
We aware learned BuB node-selection hearistic used MINLPs, so guidance towards feature selection doesn't 't. exist yet. Taking advantage of them presumably also requires train on nonlinear problems.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Table 2: Comparison against (Labassi et al. 2022). Note that we use a single network, evaluated out-of- distribution, while (Labassi et al. 2022) uses different networks, all trained on that specific type of mixed integer linear program. For all metrics, lower better.
FMONF
GISP
WPMS
Nodes
Runtime
Nodes
Runtime
Nodes
Runtime
Labassi FMCNF
339.53
5.90
29.45 1 2.13
Labassi GISP
1219
1.73
26.50 + 1.55
Labassi WPMS
215.26 + 1.97
10.46 + 1.56
Ours
187.33 3.67 19.99 + 2.25
1216.16
1.91
16.94 + 1.49
221.73
1.78
8.04
1.72
separate model for each problem type, while our method is already flexible enough to handle all problem types within single model. Since Labassi et al. (2022) needs to re-train for each instance type and only works for linear problems, we cannot. test it against, MIPLIB and MINLPIIBB. Instead, we reproduce all benchmarks used by Labassi et al. (022) (each with their own separate models), and compare against them against our single model.
Labassi et al. (2022) considers the problem of minimizing time-to-solution and minimizing the number of nodes explored over set of synthetic problems. This means that rather than the problem of minimizing the gap that can be reached within given time limit (Table D. here we always optimize completion and track the runtime elapsed until the problem is solved. We use the "transfer" instances and best performing models provided by Labassi et al. 2022) and re-run the benchmarks on our hardware.
As we report in Table 2 we convincingly beat the prior work on every single benchmark (aside of WPMS node count), despite our method never having seen any of these problem types during training. This is surprising because Labassi et al. (2022) should have a convincing advantage due to the fact they not only have a dedicated agents for every single one of their problems, they also use the same generator for their training and lesting instances. This implies that your single solver, evaluated out-of-distribution, manages to outperform the specialized agents proposed by Labassi et al. (2022) evaluated in-distribution. In general, our method improves upon Labassi et al. (2022) by between 30% and 56% with respect to runtime.
5.5 Ablations
We ablate the importance of the individual features used in our node selector using the SHAP (Lundberg & Lee 2017) interpretability algorithm (see Appendix H We find that our node selector automatically discovers best-practices from the classical node selection community, such as preferentially selecting nodes with lower lower-bound, balanced by greedy "best node" selection. Specifically interesting, we find that our selector significantly incorporates the amount of cutting planes applied to each node, hinting at a stronger than expected connection between node-utility and cutting planes.
In addition to the feature importance analysis done above, we also investigate rumning the model without GNN: We find that when removing the GNN, the model tends to become very noisy and produce unreprodueible experiments. Considering only the cases where the GNN-free model does well, we still find the model needs roughly 30% more nodes than the SCIP or our model with a GNN. More importantly, we notice the GNN-free model diverges during training: starting with a reward of roughly zero, the model diverges down to a reward of -0.2, which amounts to a score roughly 20% worse than SCIP. We therefore conclude that, al least. for our architecture, the GNN is necessary for both robustness and performance.
6 Limitations
There are still many open questions that give rise to future research or further investigation. First, while we report initial results in our ablation study (see Sec. 5.5 and Appendix HD on the importance of features, feature selection remains an area where we expect significant improvements, especially for nonlinear programming, which contemporary methods do not account for.
11

---

Published in Transactions on Machine Learning Research (12/2024)
Second, one possible limitation is the limited runtime during training. Unfortunately, it is not computationally tractable for us to train on such large fime-frames. However, we demonstrate in Sec. 5 that our model trained on a 45s time limit generalizes flawlessly to larger time limits of 5min. Hence we also expect our method to work on considcrably larger problem sets.
Third, we also expect significant. improvements performance through code optimization. important area for research lies in generalized instance generation: Instead of focusing on single domain instances for training (e.g. from TSP), instance generator should create problem instances with consistent, but varying levels of difficulty across different problem domains. Further, the number of nodes used before switching to classical node selectors is only done heuristically. Finding optimal switching points between different node selectors is still an open problem even beyond learned solutions and represents an interesting place for further research.
7 Conclusion
We have proposed a novel approach to branch-and-bound node selection, that uses the structure of the aranch-and-bound process and reinforcement learning to convincingly beat classical SCIP and learnt node selectors. By aligning our model with the branch-and-bout potential to develop a versatile heuristic that can be applied across various optimization problem domains, despite being trained on narrow set of instances. To our knowledge, this is the first demonstration of learned node selection to mixed-intege (nonlinear) programming.
tree structure, we have demonstrated the
Acknowledgments
This work was supported by the Bavarian Ministry for Economic Affairs, Infrastructure, Transport and Technology through the Center for Analytics-Data- Dapa-Appiiiaiions (ADA-Center) within the framework of "BAYERN DIGITAL II
References
Marcin Andrychowicz, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphael Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study, June 2020.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprinl orXiv:6607.000 500.00640,.00 2016.
Thomas C. Bachlechner, Bodhisatiwa Prasad Majumder, Huanru Henry Mao, G. Cottrell, and Julian McAuley. Rezero is all you need: Fast convergence at large depth. In Conference on Uncertainty in Arlificial Intelligence, 2020. CRL https://api. www.nticacoollee.e.o.....ocoo..e hta.choolaaarrr//roosssD::::: :1:224462 212644626
Christopher Bayliss, Geert De Maere, Jason Adam David Atkin, and Marc Paelinck. A simulation scenario based mixed integer programming approach to airline reserve crew scheduling under uncertainty. Annals of Operations Research, 252:335 363, 2017.
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dicter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. Technical report, Optimization Online, December 2021.
Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller, Felipe Serrano, Stefan Vigerske, and Fabian Wegschei- der. Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8, January 2023.
Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. Evolving diverse tsp instances by means of novel and creative mutation operators. In Proceedings of the 15th
12

---

Published in Transactions on Machine Learning Research (12/2024)
ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA '19, pp. 58-71, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362544 doi: 10.1145/3299904334033077
Michael R. Bussieck, Arne Stolbjerg Drud, and Alexander Mceraus. MINLPLib-a collection of test models for mixed-integer nonlinear programming. INFORMS Journal on Computing, 15(1):114 119, February 2003. doi:
William J Cook, David L Applegate, Robert E Bixby, and Vasek Chvatal. The traveling salesman problem: computational study. Princcton university press, 2011.
George B. Dantzig, Reminiscences about the origins of linear programming. Operations Reseorch Letters, / 10.1000
(2):43-44 48, 1982. ISSN 0167-6377. doi: http::///daooooo//oo/////o//1110
Aveen Dayal, Linga Reddy Cenkcramaddi, and Ajit Jha. Reward criteria impact the performance of reinforcement learning agent for autonomous navigation. Applied Soft Compuling, 126:109241, 2022. ISSN 1568-4946. doi:
sccecce/arriceeep1////6666666663 2092..2111222222211 URL
Mare Etheve, Zacharie Ales, Côme Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Reinforcement learning for variable selection in a branch and bound algorithm. ArXiv, abs abs/2005.10026, 2020. URL https
//api. sam...ssmanticscholll.. BrcelarrrrrrCrorore Drgg/orrpsID::11100 211551730
Christodoulos A. Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Anmals of Operalions Research, 139:131-160 2005.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Neural Information Processing Systems, 2019.
URL htttps///pp..ennnttcccccooo...r
semanticacholar org/Corpus ID: D. 174797778
Maxime Gasse, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Ch' Ch'etelat, Antonia Chmiela, Justin Dumouchelle, Ambros M. Gleixner, Aleksandr M. Kazachkov, Elias Boutros Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Christopher Morris, Dimitri J. Papageorgion, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yangm, Sha Lai, Akang Wang, Xiaodong Luo, Xiang Zhou, Haohan Huang, Sheng Cheng Shao, Yuanming Zhu, Dong Zhang, Tao Manh Quan, Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou, Cheng Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, and Mao Kun. The machine learning for combinatorial optimization competition (ml4co): Results and insights. ArXio, Abs//200..rr /20//220300433,, 2022. URL https semppntimmtiii orgo hes//Coruuss... 24724445014
Alan E. Gelfand and Adrian F. M. Smith. Sampling-based approaches to calculating marginal densities. Journal of the American Statistical Association, 85(410):398 409, 1990. ISSN 01621459. URL http:
wwww.jstor
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Mathematicul Programming Compulation, (3):443 490, September 2021. ISSN 1867-2957. doi: 10.1007/s125322-00-
He He, Hal Daume III, and Jason M Eisner. Learning to search branch and bound algorithms. Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, and Jeff Braga. Cleanrl: High-quality single- file implementations of deep reinforcement learning algorithms. ArXiv, abs/2111.08819, 2021. URL
attpss//aap semanticacholar http:/oco...aooooopoppp/////aa/a
13

---

Published in Transactions on Machine Learning Research (12/2024)
Shengyi Huang, Rousslan Fernand Julien Dossa, Antonin Raffin, Anssi Kanervisto, and Weixun Wang.
The 37 implementation details of proximal policy optimization. In ICLR Blog Track, 2022. URL http://cw....rrrrrccc..g.i..../p
https://iclr-blog
Diederik P. Kingma and Max Welling. Auto--ncodding variational bayes. CoRR, abs/1312.6114, 2013. URL
https://api. aetaaniciicoolar...oooorrraaaaaa
Yuri Kochetov and Dmitry Ivanenko. Compulalionnlly Difficult Instances for the Uncapncilated Facility Location Problem, pp. 351 367. Springer US, Boston, MA, 2005. ISBN 978-0-387-25383--1 doi: 10.1007 0-387-25383-11 1197-25383-1__6. 16.
Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. In Advances in Newral Information Processing Systems 35, 2022.
Nya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. ArXiv, fbs//171..05100 2017. URL / www.raamniicccclooaa.oororoo/plp :3319944
Scott M. Lundberg and Su-In Lee, unified approach to interpreting model predictions. In Neural Information Processing Systems, 2017. URL http:://app..emmaatcccheee org.aaaatt.cccolllooooo/oooo///p :128899700 21889700
Govind Menon, M. Nabil, and Sridharakumar Narasimhan. Branch and bound algorithm for optimal sensor network design. IFAC Proceedings Volumes, 46(32):690 -95599 2013. ISSN 1474-6670. doi: hitps:
//doi.org/10.33 10.3122/// 220111218-3-N-220555 Control of Process Systems.
10th IFAC International Symposium on Dynamics and
C. E. Miller, A. W. Tucker, and R. A. Zemlin. Integer programming formulation of traveling salesman problems. ACM, 7(4):326-33) 22922 oct 1960. ISSN 0004-5411. doi: 10.1145/3210433321044
Hans D. Mittelmann. Decison Tree for Optimization Software. 2021. Accessed: 2023-09-02.
Volodymyr Mnih, Koray Kavukeuoglı David Silver, Alex Graves, Toannis Antonoglon, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. ArXiv, abs/ 1bs/1332,5602, 2013. URL https://api. semanticscholar. : 15238391
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540))529 -33,3 February 2015. doi: 10. natuneeutue66. URL stttps://dot org/10. 1ww///aatuee///eeeeeeeaeeee natp/ee4uureee
Volodymyr Mnih, Adrià Puigdloènech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, 2016. URL http://app..emaanniccccccoooal
David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, and Edward C. Sewell. Branch-and- bound algorithms: survey of recent advances in scarching, branching, and pruning. Discrete Optimization, 19: 79 102, 2016. ISSN 1572-5286. doi:
Lars Otten and Rina Dechter. A Case Study in Complexity Estimation: Towards Parallel Branch-andd-ound over Graphical Models. Uncertainty in Artificial Intelligence Proceedings of the 28th Conference, UAI 2012, October 2012.
Christopher W. Parsonson, Alexandre Laterre, and Thomas D. Barrett. Reinforcement learning for branch- and-bound optimisation using retrospective trajectories. In AAAI Conference on Artificial Intelligence, 2022. URT. wet.eeemteecccoolla...ooorrrrore
14

---

Published in Transactions on Machine Learning Research (12/2024)
Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris J. Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International Conference on Machine Learning, 2022. URL https://app...... http::://pp...eeeaaaaccccoo www.ppp....mmattcccccclleee..
org/CorpusID ott.aaaaaiaacc.o....ooooo////rap :500772884
Ronald L. Rardin, Craig A. Tovey, and Martha G. Pilcher. Analysis of Random Cut Test Instance Generator for the TSP. In Complerity in Numerical Optimization, pp. 387-405. WORLD SCIENTIFIC, July 1993. ISBN 978-991-02-1415-9 doi:
0017.
Gerhard Reinelt. TSPLIB traveling salesman problem library. ORSA Journal on Computing, 344)3376-844 November 1991. doi: 10. 1287/1joc.3.43370
Christian P. Robert and Gareth O. Roberts. Reo-bbackwellizaiion in the meme era. 2021. URL https httprttttsssstaaaooooooooooooaaa wttp:/oopps1:::344775555
//api. remppeiaammicccholee. owg/
Lara Scavuzzo, F.
Chen, Didier Ch'etelat, Maxime Gasse, Andrea Lodi, N. Yorke-Smith, and Karen I. Aardal. Learning to branch with tree mdps. ArXiv, 22//22200..1117 2022. URL https://appl semanticschoolll o
org/Corpus 2489877888
J. Schulman, Philipp Moritz, S. Levine, Michael I. Jordan, and P. Abbeel. High-Dimensional Continuous Control Using Generalized Advantage Estimation. CoRR,, June 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization 2017.
algorithms. ArXiu,
David Silver, Thomas Hubert, Julian Schritlwieser, Ioannis Anlonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, L. Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. ArXio, abs/1712.01815, 2017. URL https://app. http:/ppp...omaanccccccccoooooes http:aaaiiiiiiaaaaooooooorra/paa wwwpaaooooo/oooor.33333e.0. :3308100
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning cut. ArXiv, abs/1906.048553 2019. URL http::://ppp...emaan..cccooooo.r wttp://aa.....aoooooooooooooooaa
Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. Open J. Math. Optim., 4:1-28, 2022. URL https://app..mmmmt.cccco... org
CorpusID::240026033
Eleonora Vercesi, Stefano Gualandi, Monaldo Mastrolilli, and Luca Maria Gambardella. On the generation metric TSP instances with a large integrality gap by branch-and-cut. Mathematical Programming Computation, 15(2):389-411 3869-466,9-6881111111 June 2023. ISSN 1867-2957. doi: N0.1007/s12533-023-0000
Zhihai Wang, Xijun Li, Jic Wang, Yufci Kuang, Min jic Yuan, Jianguo Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. ArXio,
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. ArXiv, has/1505.00853 2015. URL http:/ccoooo.o.oooooorrrrii.....
www.nticscoollet.ee..eooecccccee abs/ abs//230.000244, 2023. URL http:://ppp...mmmiiioooo.ooooooo
org/CorpusID htg//oorpusID:256555555 256459559
www.aaatiicccool....ooroo//aoppp :4008330
Kaan Yilmaz and Neil Yorke-Smith. A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP. AI, 2(2):150-178, April 2021. ISSN 2673-2688. doi: 10.3390/a12020010.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Appendix
A
Features
Table B lists the features used on every individual node. The features split into two different types: One being "model" features, the other being "node" features. Model features describe the state of the entire model at the currently explored node, while node features are specific to the yet-to-be-solved added node. We aim to normalize all features with respect problem size, as c. e.g., just giving the lower-bound to a problem is prone to numerical domain shifts. For instance a problem with objective c² P is inherently the same from solver point-of-view generally nonlinear estimators, we need to make sure such changes do not induce huge distribution shifts. We also clamp the feature values between [-10, 10] which represent "infinite" values, which can occur, for example in the optimality gap. Last but not least, we standardize features using empirical mean and standard deviation. These fcatures are inspired by prior work, such as Labassi et al. (2022): |; Yilmaz & Yorke-Smith
problem 10c" x, P, but would give different lower-bounds. Since NNs are
Table 3: Features used per individual node.
mode foatures model Featurrss
Number of cuts applied
normalised by total number of constraints
Numher separation rounds optimality gap Ip iterations
integrality gap
percentage of variables already integral histogram fractional part variables
evenly sized buckets
depth of node mode lowerbound node estimate
normalized by total number of nodes
normaliseed by min of primal and dual bound normalized min of primal and dual bound
(2021] but adapted to the fact that we do not need e. e.g., explicit entries for the left or right child's optimality gap, as these (and more general K-step versions of these) can be handled by the GNN.
Further, to make batching tractable, we aim to have constant size features. This is different from e. g.g. Labassi ct al. (2022), who utilize flexibly sized graphs to represent each node. The upside of this approach is that certain connections between variables and constraints may bocome more apparent, with the downside being the increased complexity of batching these structures and large amounts of nodes used. This isn't problem for them, as they only consider pairwise comparisons between nodes, rather than the entire saanch-and-buun graph, but for would induce great deal of complexity and computational overhcad, especially in the larger instances. For this reason, we represent flexibly sized inputs, such as the values of variables, as histograms: i.e, instead of having & nodes for variables and wiring them together, we produce once distribution of variable values with 10-buckets, and feed this into the network. This looses a bit of detail the representation, but allows us to scale much larger instances than ordinarily possible.
In general, these features not optimized, and we would expect significant improvements from more well-tuned features. Extracting generally meaningful features from branch-and-bound is a nontrivial task and is left as task for future work.
B Theoretical Derivation
One naive way of parameterizing actions is selecting probabilistically by training the probability of going to the left or right child any node. This effectively gives a hierarchical Bernoulli description of finding a path in the tree. A path is simply sequence of left ("zero direction") and right (*one direction") choices, with the total probability of observing path being the likelihood of observing specific chain
p(leaf) =
II Pi:
iEP(root,
16

---

Published in Transactions on Machine Learning Research (12/2024)
N1
P1
P1
N₂
N₂
P2
1 - P2
ps
1 ps
N
N;
No
N7
PI(1 p:)
Figure 2:
Naive approach using recursive selection. The probabilities are computed based on which "fork" of the tree is traveled. Sampling this can be done by sampling left or right based on pi
with p: being the i'th decision in the graph (scc Fig 2 Node selection can now be phrased as the likelihood of a random (weighted) walk landing at the specified node. However, using this parametrization directly would yield a significant number of problems:
Removing illegal paths from the model is quite challenging to do with sufficiently high performance. If node gets pruned or fully solved, the probability to select this node has to be set zero. This information has be propagated upward the tree to make but turns out to be rather expensive to compute since it needs to evaluate the entire tree from leaves to root.
that the selection never reaches "dead-end". This is possible,
From a theoretical point of view, the hierarchical Bernoulli representation also has a strong prior towards making selections close to the root, as the probability of reaching a node a depth consists of p1 P2 ......... PK selections. Since all p; are set to an uninformative prior < Pt < 1, the model at initialization has an increased likelihood select higher nodes in the tree. Considering that classical methods specifically mix plunging heuristics into their selection to get increased depth exploration (see Sec. 3). this "breadth over depth" initialization is expected to give low performance. Therefore, would need to find a proper initialization that allows the model to g., uniformly select nodes independent of depth to get good initialization.
The fact that multiple sampling sites exist in this method also poses issues with RL, as small errors early in the tree can have catastrophic effects later. This means the tree based model is a significantly higher variance estimator than the estimator we propose Sec [.3. which yields much worse optimization characteristics. It. is well established in existing deep learning (e.g.. g., (Kingma & Welling 2013) and general Bayesian Inference (e. g.: (Robert & Roberts 2021 Gelfand & Smith 1990)) literature, that isolating or removing sampling sites can lead to lower variance, and therefore much more performant, statistical estimators.
Using those insights, we can now rewrite this naive approach into the one we propose in Sec. First, instead of sampling just one path, we can sample all possible paths and compute the likelihood for each. The result will be a probability p at every possible leaf. If one parameterizes this as a logarithmic probability the likelihood of sampling any individual leaf, can be written as
log Pleaf
Σ
log P:-
(13)
iEP(root,leaf
We can further assume that the logp's are given as unmormalized logils W and only normalize them at the end such that to likelihood of all leaves together is 1.
This already gives an increase performance, as the paths can be computed in parallel without needing iterated random sampling, which tends to be a very expensive operation. One also has fewer discrete choices,
17

---

Published in Transactions on Machine Learning Research (12/2024)
meaning fewer backpropagation graph-breaks, which improves overall stability. The change to unnormalized logits acts essentially as a reparametrization trick (for other examples of reparametrization, see (Kingma. & Welling 2013)).
If one considers unnormalized log- bog-prbbabilitis, which have a range (-oc, oo); this scheme becomes very
similar to the one we ended up using Sec. 4.3 Tet f'node, tree) denote the unnormalized probabilities such that p(node, tree) = ((node.tree)
One can compute the likelihood of selecting specific node as:
z
f(Icaf, tree)
p(leaf(tree)
normalization
Eee's fc, tree)
exp(log(f (leaf, tree))
log are unnormalized logits
Ener exp(log( tree)
(lcaF)()caa)
delinition W as unnormalized logit
Eeer exp(W"(c)) = softmaxiea ( (c) &
definition softmax,
where softmaxieat refers to the sollmax-entry associated with leaf. The resulting decomposition ion is, while not the same, equivalent to the original Bernoulli decomposition (in the sense that for any Bernoulli decomposition there exists softmax-based docomposition). Beyond the massive reduction in sampling sites from (depth) to a single sampling site, phrasing the problem using unnormlized-log representations gives rise to additional optimizations:
Firstly, to achieve uniform likelihood for all nodes at the beginming of training, we simply have initialize ((n) = 0 for all nodes, which can be done by setting the output weights and binses to zero (in practice we set bias to zero and weights to small random value).
Secondly to account for pruned or solved nodes, we do not need to change the unnormalized probabilities. Instead, we simply only sample the paths associated with selectable nodes, as we know the likelihood of selecting a pruned or solved node is zero. This means we can restrict ourselves to only evaluating the candidate paths E, rather than all paths (see Eq.
The last modification made in our likelihood computation (see Eq. is to normalize the weights based on depth. This is done mainly for numerical stability, but in our Bayesian framework is equivalent to computing Eq. g using weights inversely proportional to depth. The resulting algorithm is much more stable and performant than the naive parametrization. In early inplementations we used the recursive-sampling approach to compute likelihoods, but the resulting scheme did not manage to reach above random results on the training sct, presumably due the higher computational burden and worse initialization. There are also other advantages to our parametrization, such the fact that one can easily inchude sampling temperatur I into the process
the
node (oflmax(WW()))TWe E8)
which can be nice to tune the model more into the dircction "exploitation" during testing. For our later benchmarking (Sec 5 we keep
(i.e., no temperature), as it would introduce further tunable hyperparameter, but this could be interesting for future work.
This construction has interesting parallels to Monte-Carke Tree Search (MCTS) Silver et al. 2017) based reinforcement learning methods. The difference in our method is that we consider iterative updates to a policy distribution т rather than a Q-function, and therefore can be seen as a policy- tree search scheme: While traditional MCTS uses variants of UCB-scores to guide the search, our method can be thought of variants of Thompson sampling to facilitate the exploration-cxploitatiio tradeoff. We leave a more thorough investigation of this to future work.
18

---

Published in Transactions on Machine Learning Research (12/2024)
Table 4: Performance across benchmarks (the policy only saw TSP instances during training). runs use the same model, evaluated for the first 650 nodes, and processed according Sec. 5.1
The 5min
Benchmark
Reward
Uuliiy
Utilty/Nood
Win-rate
geo-mean Ours
geo-mean SCIP
TSPLIB (Reinclt. 1991
0.184
0.030
0.193
0.50
0.931
0.957
UPLP (Kocheoov & Ivanenko 2005
0.078
0.093
-0.064
0.636
0.491
0.520
MINIPI. (Hussieck et al. 2003
0.487
0.000
0.114
0.852
28.783
31.185
MIPLIB (Geixxnr et al. 2021
0.140
-0.013
0.208
0.769
545.879
848.628
ISPLIBa5min
0.192
0.056
0.336
0.600
1.615
2.000
MINLPhbb5mmin
0.486
-0.012
0,078
0.840
17.409
20.460
MiPlibašmin
0.150
-0.075
0.113
0.671
66.861
106.400
C
Additional metrics
Aside from the previously discussed Reward in Section 4.1 the quality of our method compared to SCIP. While both of these have theoretical problems, we still find them interesting to consider as they act as additional reference points for the behavior of the policies.
also considered two different ways of mcasuring
Utility defines the difference between both methods normalized using the maximum of both gaps:
Utility ( (ap(scci))-gpppnneeee selector)
(max max (gap(node selector), gap gap(scip))
(14)
The reason we do not use this as a reward measure is because we empirically found it to produce worse models. This is presumably because some of the negative attributes of our reward, e.g., the asymmetry of the reward signal, lead to more robust policies. when both models hit zero optimality gap. This is because utility implicitly defines reward, which defines it g =. In sense the utility measurement is accurate, in that method does not improve upon the basclinc. On the other hand, method is already provably optimal soon it reaches gap of 0%. In general, utility compresses the differences more than reward which may may not be beneficial in practice.
addition, the utility metric gives erroneous measurements
O, rather than
Utility per Node normalizes Utility by the number of nodes used during exploration:
scip selector
Utility/Nodk max (selector, (selector,scip))
(15a)
where selector = wodes/node selector] and scip = modes(seip)' The per-node utility gives a proxy for the total amount of "work" done by each method. However, it ignores the individual node costs, solving the different LPs may take different amounts of resources (a model with higher "utility/ne /nor/"/ is not necessarily more efficient as our learner might pick cheap but lower expected utility nodes on purpose). Further, the metric is underdefined: comparing two ratios, a method may become better by increasing the number nodes processed, but keeping the achieved gap constant.. In practice the number of nodes processed by our node selector is dominated by the implementation rather than the node choices, meaning we can assume is invariant to changes in policy. Another downside arises if both methods reach zero optimality gap, the resulting efficiency will also be zero regardless of how many nodes processed. As our method tend to reach optimality much faster (sce Sec. 5 and Appendix [. all ntility/node results can be seen as lower-bound for the actual efficiency.
gop(node sefector)
gep(scip)
D Comparisons of Runtime to completion
We also compare the runtime of our selector against the SCIP baseline on TSPLIB. For this we set a maximum time limit of 30min and run both methods. is worth noting that due to the inherent difficulty of TSPLIB, a significant number of problems are still unsolved after 30min, in which case these models are simply assigned the maximum time as their overall completion time. Note that this also implics that the SCIP solver itself not capable of solving these problems due to their scale. We reckon that this is also the reason why e.g., Labassi
19

---

Published in Transactions on Machine Learning Research (12/2024)
Method
Runtime shifted geometric mean
Nodes Processed geometric mean
SCIP
1016.61s
4122.67
Ours
1003.03s
2735.33
Table 5: The shifted geometric mean (shifted by +10) of runtime and number of nodes processed.
ct al. (2022) does not even attempt to benchmark on these large scale problems. Our method outperforms the baseline, however due to the fact that our method aims to improve the quality of early selections in particular, the amount of improvement is rather small. Further, our method fundamentally undertrained to adequately deal with longer time horizons and we would assume the effect our method is larger the longer the model trained. Despite this being worst-case evaluation scenario, our method manages oulperform the baseline in both runtime and number of nodes needed.
Interestingly, we also manage to reach this superior performance while utilizing only about half the number of nodes. This discrepancy cannot be explained by just considering the slowdown due to our policy needing to be evaluated, as, while it is a significant overhead due to the Python implementation, it is very far from being large enough to justify 50% slowdown over the course of 30min. This also shows more generally that even if one restricts themselves to only processing the beginning of the branch-and-bound tree, one can reach superior performance to the standard node-selection schemes.
E
Architecture
Our network consists of two subsystems: First, we have the feature embedder that transforms the raw features into embeddings, without considering other nodes this network consists of one linear layer [dfeaturesl - |dmodet
with LeakyReLU (Xu et al.) 2015) activation followed by two |dmodell |dmoder] linear layers (activated by LcakyReLU) with skip connections. We finally normalize the outputs using Layernorm (Ba et al. 2016) withoul Irainable paramelers ei. just shifting and scaling the feature dimension to a normal distribution)
Second, we consider the GNN model, whose objective is the aggregation across nodes according to the tree topology. This consists single LeakyReLU activated layer with skip-conncctions. We use ReZero (Bach lechner et al., 2020) initialization to improve the convergence properties of the network. Both the weight and value heads simple linear projections from the embedding space. Following the guidance in (Andrychowicz) et al. 2020), we make sure the value and weight networks independent by detaching the value head's gradient from the embedding network.
For this work we choose |dmodet = 512, but we did not find significant differences between different model sizes past a width of 256. For training we use AdamW Loshchilov & Hutter (2017) with a standard learning rate of 3- 10-4 and default PPO parameters.
F TSP-as-MILP Formulation
In general, due the fact that TSP is amongst the most studied problems in discrete optimization, we can expect existing mixed-integer programming systems have rich heuristics that provide strong baseline for
20

---

Published in Transactions on Machine Learning Research (12/2024)
our method. Mathematically, choose the Hiller-TTukke Zemlin (MTZ) formulation Millerr et al.
1960
min
Cijttj
jæij==1
1
subject to
Σ
Vij =1
Vi = I....,n
J }=1,
Σ Tij =1
Vj = ,,....
1=
U1 Uj + (n 1) n 2 25i
14 S
2 25isn
", E my E (),1)
Effectively this formulation keeps two buffers: one being the actual (ddges travelled Ziji the other being a node-order variable u, that makes sure that u, < u; if' such the Dantzig Fulkerson Johnnson (DFJ) formulation, which are used in modern purpose-buit TSP solvers, but those are less useful for general problem generation: The MTZ formulation essentially relaxes the edge-assignmentt and order constraints, which then are branch-and-bounded into hard assigmments during the solving process. This is different to DFJ, which instead relaxes the "has to pass through all nodes" constraint. DFJ allows for subtours (e. g., only contain node A, B, C' but not D, E)) which then get slowly eliminated via the on-the-fly generation of additional constraints. To generate these constraints one needs specialised row-generators which, while very powerful from an optimization point-of-view, make the algorithm less general as custom row-generator has intervene into every single node. However, in our usecase also do not really care about the ultimate performance of individual algorithms as the reinforcement learner only looks for improvements to the existing node selections. This means that as long the degree of improvement can be adequately judged, we do not need state-of-the-art solver implementations to give the learner a meaningful improvement signal.
is visited before j. There are alternative formulations,
G Uncapacitated facility location Problem
Mathematically, the uncapacitated facility location problem can be seen as sending a product 2y from facility to consumer with cost Cij and demand dy. One can only send from i to j if facility i was built in the first. place, which incurs cost f.. The overall problem therefore is
m
min
ΣΣ
cyddzay +
Σ fez 1=0
subject to
Rig =
Vi = I,...,m
j=1,
Σ
24g S Mx;
Vj 1, ......7
(=1,
Zij E (0, 1}
Vi,j = 1,...,
x E 10,
Vi 1,...,
where M is a suitably large constant representing the infinite-capacity one has when constructing 2; = 1. One can always choose M 2 m since that, for the purposes of the polytop is equivalent to setting M to literal infinity. This is also sometimes referred to as the "big M method.
The instance generator by Kochetov & Ivanenko (2005) works by sotting m 100 and sctting all opening costs at 3000. Every city has 10 "cheap" connections sampled from 2,,3, 4) and the rest have cost 3000, which represents infinity (i.e., also invoking the big M method).
21

---

Published in Transactions on Machine Learning Research (12/2024)
H Feature Importance
We try to interpret the learned node-selection heuristic by applying the KernelSHAP (Lundberg & Lee 2017] method. SHAP methods try to estimate the feature importance by measuring the performance of an estimator where some portion of the features are replaced with a "neutral" element. Doing this with a large enough set, one is able extract the feature importance the form of the magnitude of the change between the expected value of the estimator and the value the estimator would have had if a specific feature were absent.
Analyzing our RL method with SHAP has two significant limitations: Firstly, we ignore the impact of message passing on the model and instead analyze every node as a leaf node. This is of relatively small impact as the time where a node was selected it. had to have been a leaf node anyways so the plots faithfully show the model output at selection time.
The second limitation is that we do not have an iid. dataset, but instead have to build one from the environment first. To build that dataset, we could sample random BnB trees and evaluate on the nodes, but this would mean evaluate our model completely out-of-distribution, as random randomselection will most likely lead to states the model would never want to reach and is therefore ill equipped to handle. Therefore, we instead build our dataset by rumming our node-selector on a subset of MIPLIB to gather our importance-evallattoo data. This has the downside that the expected value of our selection network is higher than in random selection, since the model is guided towards selecting higher value nodes.
With these caveats in mind, one can see in fig, 3 that our node selector relies significantly on the node lowerbound for setting its weight. This makes sense: in node-selcction there is a fundamental tension between raising the lower bound and opportunistically searching for new primal solutions. The current SCIP default "hybrid best bound search" " does exactly that, just using hand-made heuristics where nodes are selected based on a mixture of following the currently best bound nodes, and plunging depth-first search to find better solutions. However, as can be seen in our benchmarks (tab I we beat SCIP's default selector quite significantly, which implies a nontrivial interaction in the remaining features.
Looking at the beeswarm plot 4 we observe that our model preferentially picks nodes which, in addition to a low node lowerbound, also uses nodes which have few variables with an integrality gap of 0.2 and 0.3, has lot of cuts applied, and has a high expected integrality gap. If we considered node with all of these features (and assume there would not be any nonlinear value-dampening effects), such a node would be a prime candidate for having good child nodes: A node with low lowerbound means that the node still has significant room for improvement, while having a lot of cuts applied means that the node's solution is sufficiently close to existing integral points to make feasible to find better values. Looking further into the fcatures, one can also see that the model dislikes nodes that already have a significant number of "already integral" variables. This makes sense nodes with significant number of integral variables that are not solved already (i. e., they have children to split on), can be quite hard to complete while not giving a significant improvement in solution quality. This is because most likely a primal hcuristic has already found the optimal value of that node, but branch-and-bound still needs a significant number of trials to prove that the found value is optimal in that subtree.
In short, our solver picks the nodes with the highest dogree of possible improvement (low lowerbound), while also favoring nodes that have more information (more cuts applied) and presumably are nontrivial to solve via heuristics (high mean to integral gap/low "already integral" ratio).
In general, interpreting dynamic RL policies is highly nontrivial, especially if the estimator is nonlinear, but the interactions we can clearly see in the SHAP plots indicates that the learned policy is reasonably well grounded in existing best-practices for node selectors.
Full Results
The following two scctions contain the per-instance results on the two "named" benchmarks TSPLIB (Reinelt) 1991h and MINLPLIB (Bussiock al., [2003). We test against the strong SCIP 8.0.4 baseline. Due compatibility issues, we decided not. to test against (Labassi et al.] 2022 or (He et al., 2014]:
These
22

---

Published in Transactions on Machine Learning Research (12/2024)
node bound
holpp
not 0.3,0.4
+0.09
hist 0.0,0.1
-0.00
atready intvgral
node estimane
hist o.a
hist
+0.00
Not
10.00
hist 0.5,0.6
+0.00
has 0.8,0.9
16..9.1.
10.04
Neepa
g9p
depth_normed
00.02
0.2
2A
meanifpast value))
Figure 3: Barplot showing feature importance of individual nodes using the KernelSHAP 2017 method.
Lundberg & Lee
his 2.7.0. 8.%
NcutsApp
moan to intogral
hist
hist 0.0
hist 0.6, 0.6.
Pesture
hist 0.4_0.5
0.1_0.2
hist 0.5 0.6
hist D.6.
hist 0.9.
Nsepa
qap
1pl
depth_nomes
-25
-20
-15
-100
LoW
model output)
Figure 4: Beeswarm plot showing feature importance of individual nodes using the KernelSHAP Lundberg &
Lee
2017
method.
23

---

Published in Transactions on Machine Learning Research (12/2024)
methods were trained against older versions of SCIP, which not only made running them challenging, but also would not give valid comparisons as cannot, properly account for changes between SCIP versions. Labassi et al. (2022) specifically relies on changes to the SCIP interface, which makes porting to SCIP 8.0.4 intractable. In general, this shouldn't matter too much, as SCIP is still demonstrably the state-of-tho-art non-commercial mixed-integer solver, which frequently outperforms even closed-source commercial solvers (see Mittelmann (2021) for thorough benchmarks against other solvers), meaning outperforming SCIP can be seen as outperforming the state-of-the-art.
Kochetov-UFLP
To demonstrate the generalizability of the learned heuristics, we test our method on the Uncapacitated Facility Location Problem (see Appendix G without further finetuning, i.e, we only train on TSP instances and never show the algorithm any other linear nonlinear problem. For testing, generate 1000 instances using the well-known problem generator by Kochetov & Ivanenko (2005), which was designed to have large optimality gaps, making these problems particularly challenging.
Our method performs very similar to the highly optimized bascline, despite never having seen the UFL problem, see Table [ We argue that this is specifically because our method relies on tree-wide behaviour, rather than individual features to make decisions. We further hypothesize that the reason for the advantage over the baseline being so small is due to the fact that UFLP consists of "adversarial examples" the branch-and-bound method where cuts have reduced effectiveness. This means clever node-selection strategics have limited impact overall performance.
An interesting aspect is that our method processes more nodes than the baseline, which also leads to the loss in node-efficiency. This implics that our method selects significantly casier nodes, as ordinarily our solver is slower just. due to the additional overhead. Considering that this benchmark was specifically designed produce high optimality gaps, makes sense that our solver favours node quantity over quality, which an interesting emergent behaviour of solver.
1.2 TSPLIB results
24

---

Published in Transactions on Machine Learning Research (12/2024)
Table 6: Results on TSPLIB (Reinelt 1991 after 45s runtime. Note that we filter out problems in which less than nodes were explored those problems cannol gain meaningful advantages even with perfect node selection. "Name" refers to the instances name, "Gap Base/Ours" corresponds to the optimization gap achieved by the bascling and our method respectively (lower is better), "Nodes Base/Ours" to the number of explored Nodes by each method, and "Reward", "Utility" and "Utility Node" to the different performance measures as described in Section
Name
Cap Ours
Cap Base
Nodes Ours
Nodes Base
Roward
Utility
Utility/Node
att448
0.287
0,286
1086
2670
-0.002
-0.002
0.593
bayg29
0.000
0.000
2317
7201
1.000
0.000
0.000
bays29
0.000
0.036
11351
10150
1.000
1.000
0.997
berlin52
0.000
0.000
777
1634
1.000
0.000
0.000
bier127
2.795
2.777
23
25
-0.007
-0.007
0.074
braxi158
0.328
0.644
1432
2182
0.491
0.491
0.666
burma144
0.000
0.000
96
65
1.000
0.000
0.000
ch130
8.801
8.783
48
43
-0.002
-0.002
-0110
ch150
7.803
7,802
18
18
-0.000
-0.000
-0.000
d198
0.582
0.582
10
11
-0.000
-0.000
0.091
dantxig42
0.185
0.100
2498
3469
-0.847
-0.459
0.248
eil101
2.434
2.430
31
61
-0.002
-0.002
0.491
cil51
0.178
0.017
828
4306
-1 -1.000
-0.907
-0514
cil76
0.432
1.099
309
709
0.607
0.607
0.829
fri26
0. 0.000
0.000
1470
6721
1,000
0.000
0,000
gr120
7.078
7.083
41
43
0.001
0.001
0.047
gr137
0.606
0.603
30
25
0,,06
-0.006
-0.111
gr17
0.000
0.000
92
123
1.000
0.000
0.000
gr24
0.000
0.000
110
207
1.000
0.000
0.000
gr48
0.192
0.340
586
2479
0.435
0.435
0.866
gr96
0.569
0.552
93
182
0.032
0.031
0.472
hl448
0.071
0.106
2571
2990
0.324
0.324
0.419
kroA100
8.937
8.945
102
233
0.001
0.001
0.563
kroA150
11.343
11.340
23
-0.000
-0.000
-0.087
kro0
13.726
13.723
-0.000
-0.000
0.286
kroB100
7.164
7,082
83
109
-0.011
-0.011
0.230
kroB150
10.965
10,965
16
0.000
0.000
-0.125
kroB200
11.740
11.740
0.000
0.000
-0.143
kroC100
8.721
8.754
118
133
0.004
0.004
0.116
kroD100
7.959
7.938
70
111
0.003
-0.003
0.368
kroE100
8.573
2.952
105
108
1.000
-0656
0.646
1mm105
2.003
149
0.001
-0.001
0.341
pr107
1.336
217
0.024
-0.033
0.396
pr124
0.935
-0.011
-0.001
pr136
2.351
2.350
-0.000
-0.000
pr144
2,200
47
-0.012
-0.012
-0,222
pr152
2.683
14
-0.002
-0.002
0.658
pr226
1.091
1.092
0.001
0.001
0.001
pr76
0.534
0.476
201
855
-0.123
-0.109
0.736
ra199
0.853
0.849
-0.005
-0.005
0.485
rd100
5.948
4.462
100
166
-0.33
-0.250
0.197
xi175
0.270
0.270
0.000
0.000
0.125
s170
0.586
3.018
379
1068
0.806
0.806
0.931
swiss42
0.000
0.000
1075
1133
1.000
0.000
0.000
u
0.000
0.000
18322
19553
1.000
0.000
0.000
ulysscs22
0.103
0.127
13911
13313
0.191
0.191
0.154
Mean
1321
1799
0.184
0.030
0.193
25

---

Published in Transactions on Machine Learning Research (12/2024)
1.3 MIPLIB results
Table 7: Results on MIPLIB Gleeixer et al., 2021) after 45s runtime. Note that we filter out problems in which less than nodes were explored as those problems cannot gain meaningful advantages even with perfect node selection. "Name" refers to the instances name, "Gap Base/Ours" corresponds to the optimization gap achieved by the baseline and our method respectively (lower better), "Nodes Base/Ours" to the number of explored Nodes by each method, and "Reward", "Utility" and "Utility Node" the different performance measures as described in Section
Note that all results where achieved with policy only trained on TSP
instances
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
UtilityNNode
30a20b8
2.602
00
141
301
1.000
1.000
1.000
50v-10
0.101
1091
0.103
CMS750
0.100
0.072
68
281
-0.399
-0.280
0.664
air05
0.000
0.000
248
523
1.000
0. 0.000
0.000
assigu1-5-8
0.085
0.087
17466
23589
0,030
0,030
0.282
b0nkarl0
0.000
0.000
2843
2270
1.000
0.000
0.000
blp-ic98
0.127
0.127
26
43
0.001
0.001
0.396
bnatt-100
00
00
5:17
1568
0.000
0.000
0.651
bnact500
0.842
bppc4-08
0.038
0.038
1318
3277
0.000
0.000
0.598
cost266-UUE
0.130
0.143
468
770
U.094
0.094
0.449
esched007
558
1770
0.000
0.000
0.685
esched008
0.070
00
910
1179
1.000
1.000
1.000
cvs16r128-89
0.500
0.601
6
0.068
0.068
0.202
drayage-25-23
0.000
0.000
105
267
1.000
0.000
0.000
dws008-01
eil33-2
0.194
0.189
191
171
-0.025
-0.024
-0.127
fast0507
0.027
0.027
11
-0.003
-0 003
-0.66
fastxgemmm-n2r66012
18.519
18.519
785
2531
0.000
0.000
0.690
fhow-binpack4-4
00
140002
152608
0.000
0.000
0.083
ftux-binpackd-18
0.000
15019
24619
-1.000
-1,000
fiball
0.029
0.036
442
610
U.200
0,200
0.420
gen-ip002
125319
0.197
gen-ip054
0.008
0.010
157950
179874
0.207
0.207
0.263
glass-sc
0.580
0.495
200
328
-0.133
0.148
0,285
glass4
1.123
1.033
37424
35671
-0.087
-0.080
-0.123
gmm-35-40
0.001
0.001
28534
27077
0.402
0.398
0.276
gmu-35-50
22333
0.176
0.341
graph20-20-1rand
0.000
0.000
416
283
1.000
0.000
0.000
graphdraw-domain
56798
ie97_potential
0.023
0.040
39316
30633
0.415
0.415
0.247
icir97 _tensio
0.011
0.006
6697
7943
-0.882
-0 00.68
-0.667
irp
0.000
0.000
6
1.000
0.000
0.000
istanbul-no-cutoff
0.514
0.393
37
28
-0.309
-0 0.236
-0.122
lectsched-S-obj
1192
11.000
lcal
0.118
0.113
34
108
-0.049
-0.046
0.670
0.345
-1.000
00514
mad
78783
81277
0.000
0.000
0.031
markshare2
00
00
91135
127265
0.000
0.000
0.284
markshare
070277
682069
0.000
0.000
0.164
maa74
0.079
0.081
32005
26180
0.060
0.060
-0.129
mas76
0.014
mcll
0.008
0.009
333
1989
0.139
0.138
0.855
mesched
0.090
0.086
1526
-0.049
-0.046
0.698
mik-250-20-75-4
0.000
0.000
10067
10120
1.000
0.000
0,000
milo-v12-6-r2-4411
0.038
0.031
340
514
-0.242
0.195
0.179
momentuml
2,568
2,868
-0.000
-0.100
u2seq36g
0.665
0.665
5
U.000
0.000
0.167
n5-3
nens-1 1171737
0.032
0.032
7
13
0.000
0.000
0.462
neos-1-44
ne08-11445655
0.000
0.000
190
1,000
0.000
0.000
115979
0.341
201
405
-1.000
-1.000
-1.000
mecss-1882222
0.016
0.016
11
11
0.000
0.000
0.000
220022657525-cr
45188
0.052
meos-2978193-iiude
0.013
0.013
964
2178
0.000
0.000
0.557
Sans-3004026-krkka
1163
2oos-30249552looue
246
377
0.000
0.000
0.347
ueos-3010615-mmin
2.515
2.631
66921
79117
0.044
0.044
0.191
moos=90038199auubu
0.000
0.000
1683
1687
1.000
0.000
0.000
ncns-3381206-uwhhe
0.000
0.000
969
230
1.000
0.000
0.000
meos=3102222-bbbiia
24
0.583
(ann-3627168-kaasse
0.003
0.008
6269
3338
0.577
0.577
0.205
Contimued next page
26

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
mons-3754480-nicdla
87703
106632
0.000
0.000
0.178
mcus-45356004-soww
0.024
0.028
37447
36741
0.125
0.125
0.107
noos-4387887-taavu
0.005
0.005
0.016
0,006
529
1064
-1.000
-0.034
-0.265
2809-1951672-bette
0.265
0.254
454
775
-0.0413
-0.041
0.389
Mecs=5009552--nssaumm
0.539
0.559
5
0,036
0.036
0.197
mccs=51107997kcaakpp
2,639
5.077
1885
2332
0.480
0.480
0.380
1800-5588808-nattal
106
0.000
0.000
0.848
neo=-5195221-nieme
106-117
106.117
11
12
0.000
0.000
0.083
nens-91
0.000
3905
1.000
0.000
Deos17
0,000
0.000
2151
3346
1,000
0.000
0.000
neos5
0.062
0.059
66231
91449
-U.033
0.050
0,235
neus859080
0.000
0.000
990
1227
1.000
0.000
0.000
net.1
2.592
2.114
56
29
-0. 222
185
-0.578
os1208400
82
0.000
0.000
0.453
us 1e18830633
2.831
1.242
331
686
-1.000
-0 40.611
-0.099
ns1952007
62
0.000
0.000
-0.480
nu25-pr12
0.000
0.000
119
153
1,000
0.000
0.000
mursesched-spriutt2
0,000
0.000
9
1.000
0.000
0.000
nw04
0.000
0.000
6
1,000
0.000
0.000
Pg
0.000
0.000
460
491
1.000
0. 0.000
0.000
pg5 31
0.001
0.004
275
0.321
piperout-U8
0,000
0.000
223
309
1.000
0.000
0.000
piperout-27
0.000
0.000
47
28
1.000
0.000
pkl
1.244
1.117
102268
120685
-0.113
-0.102
0.057
audiationm18-12.1
0.057
0.167
886
2569
0.661
0.661
0.883
rai1507
0.033
0.033
0.000
0.000
10.000
ran ran11x
0.115
0.092
458
975
-0.251
-0 0.200
0.412
rd-rplusc-21
35412
0.961
reblock115
0.106
0.139
80
731
0.238
0.238
0.917
rmatr100-p10
0,216
0.326
71
0.337
0.337
0.615
roci-4-11
0.671
0.837
12054
7909
U.198
0.198
-0.181
rocII-5-11
3.479
1.568
164
287
-1.000
-0549
-0.211
10-00oBB1-00 10-01:0000 1000
1.244
1,258
26
0.012
0.012
0.544
rococoC10-001000
0.337
0.153
135
860
-1.000
-0 -0.516
0.656
rol13000
sct2
0.001
0.002
2117
1215
0.619
0.615
0.332
seymour
0.014
0.035
176
563
-0.243
0.1955
0.611
seymourl
0.003
0.003
329
885
0.146
0.145
0.682
sp150x300d
0.000
0.000
148
124
1.000
0.000
0.000
supporteasel8
0.081
0.081
178
1372
0.000
-0.000
0.870
supportcase26
0.224
0.231
11191
20287
0.031
0.031
0.165
supporicase33
27.788
28
-0.955
supportcase40
0.086
0.094
50
111
0.087
0.087
0.589
supporicase42
0.033
0.050
76
256
U.340
0.340
0.804
swathl
0.000
0.000
311
372
1,000
0.000
0.000
swath3
0.1
0.113
1442
2800
0.020
0.020
0.495
timtabl
0.126
0.094
25367
-0.333
-0,250
-0.139
tr12-30
0.002
0.002
8941
14896
0.019
0.019
0.394
traininstance2
traininstancedi
29.355
2549
6376
1.000
1.000
1.000
trentol
3.885
3.885
4
-0.000
-0.000
0.429
uct-subprob
0.249
0.195
225
263
-0.276
-0.216
-0.084
var-smallemery-m6jo
0.062
0.062
95
224
-0.002
-0.002
0.575
wachplan
0.125
0.000
0.407
16538
19673
0.140
-0.013
0.208
1.4 MINLPLIB results
Table 8: Results on MINLPLIB Bussieck et al. 2003) after 45s runtime. Note that we filter out problems in which less than nodes were explored as those problems cannot gain meaningful advantages even with perfect node selection. "Name" refers to the instances name, "Gap Base/Ours" corresponds to the optimization gap achieved by the baseline and our method respectively (lower better), "Nodes Base/ Base/Ours" to the number of explored Nodes by each method, and "Reward", "Utility" and "Utility Node" the different performance measures as described in Section For all three measures, higher is better.
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Nodde
ball mk4 05
0.000
0.000
1819
1869
1.000
0.000
0.000
Continued next page
27

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
hall ____m_44_00 10
31684
37656
0.000
0.000
0.159
ball mk4 15
1773
2415
0.000
0.000
0.266
hayes2 20
00
3171
2719
0.000
0.000
-0.143
bayes2_30 _0000000__
4462
4992
0.000
0.000
0.106
bayes2 50
00
00
2931
2530
0.000
0.000
-0.138
blend029
0,000
0,000
812
804
1,000
0.000
0.000
blend146
0.097
0.105
12390
18066
0.075
0.075
0.365
blend480
0.071
0.000
4878
6312
-1.000
-1.000
-0.999
blend531
0.000
0.000
3150
7161
1.000
0.000
0.000
18
0.808
0.796
22652
26060
127
-0.113
0.020
blend721
0.000
0.000
4650
2708
1,000
0,000
0,000
blend852
0.021
0.000
7726
5113
-1,000
-1.000
+0,997
c0m
0.076
0.074
18839
22205
-0.027
-0.026
0.128
camshape200
0.145
0.147
8199
9921
0.012
0.012
0.183
camshape400
0.198
0.195
4324
5275
-0,016
-0.016
0.167
camshape800
0.222
0.226
1501
1627
0.019
0.019
0.093
cardap_inlp
1.436
1.660
4316
7232
0.135
0.135
0.484
cardqp_igp
1,089
1.660
1766
7285
0.341
0.311
0.571
carton?
0.000
0.000
55
73
1.000
0.000
0.000
carton9
0.000
0.000
9848
7406
1,000
0.000
0.000
catmix
00
00
186
8750
0.000
0.000
0.979
catmix200
123
3870
0.000
0.000
0,968
catmixduu
146
3498
0.000
0.000
0.958
catmix800
00
00
75
333
0.000
0.000
0.775
celar6-sub0
1
0,000
0.000
0.333
chimera k64ising-01
0.701
16.469
18
21
0.937
0.957
0.964
chimera_ -
0.523
0.199
57
198
-1,000
-0.618
2,246
chimera ké-Imaxeut-02
0.368
0.239
72
381
-0.536
-0.349
0.710
chimera Iga-02
0.893
0.893
0,000
0.000
0.167
chimera sew-cc8-49--onck
0.045
0.021
127
521
-1.000
-0.529
0.482
chimera
0.067
0.016
72
526
-0.449
-0.310
0.802
chimera ngw-ce--577-onc8
0.232
0.233
26
99
0,003
0.003
0.738
chimera mgw-ce-557-onnck
0.188
0.346
25
0.455
0.455
0.695
chimera_mis-01
0.000
0.000
7
1.000
0.000
0.000
chimera_ mis-02
0.000
0,000
7
7
1.000
0.000
0.000
chimera :fr-01
1.029
0.108
0.108
+0.023
chimera rfr-02
1.148
1.061
74
63
-0.082
-0.076
-0.213
chimera selby-c8-omes-01
0.136
0.221
31
111
-0.941
-0.485
0,406
chimera selby-c8-onc5-02
0.439
0.232
92
-0.995
-0.472
0.176
clay0203m
0.000
0.000
19
30
1.000
0.000
0.000
clay0204m
0.000
0.000
266
1.000
0.000
0.000
clay0205m
0.000
0.000
1058
3908
1.000
0.000
0.000
clay0308m
0.000
45
1,000
0.000
clay0304m
0.000
0.000
337
897
1.000
0.000
0.000
clay0305m
0.000
0.000
4057
4204
1.000
0.000
0.000
color color_lab3, 3x0
1.445
1.725
320
576
0.162
0.162
0.534
@alor_labs3_00 4x0
5. 5.581
5.455
265
434
-0.033
-0.023
0.375
crossdock_115
4.457
8,216
654
1080
0.458
0.458
0.672
crossdock 15x8
8.578
84,148
391
717
0.898
0.898
0.941
crudeoil
0.000
57
1.000
0.000
crudenil lenl 00
0.000
0.000
57
92
1.000
0.000
0.000
crudeoil Jeel
0.000
0.000
161
121
1.000
0. 0.000
0.000
crudenil lenl 09
0.000
0.000
107
99
1,000
0.000
0.000
crudeoil leel
0.000
0.000
78
109
1.000
0.000
0.000
crudeoil lee2
0.000
0.000
11
1,000
0.000
0.000
crudeoil lee2 06
0.000
0.000
45
109
1.000
0.000
0.000
crudenil lee2_
0.000
81
1.000
0.000
0.000
0.000
0.000
150
308
1.000
0.000
0.000
crudeoil Jee2
0.142
0.015
41
41
-1.000
-0 897
-0,901
crudenil Baciiil__een______ len3_05
0.000
0.000
1435
1820
1.000
0.000
0.000
crudeoil lee3 06
0.057
0.013
352
1349
-1.000
-0.764
-0.095
crudeoil lee1
0.000
1,000
0.000
crudeoil lee4 06
0.000
0.000
129
60
1.000
0.000
0.000
crudenil les4_07
0.000
0.000
193
89
1.000
0.000
0.000
erudeoil 1ee4__08
0.000
0.001
41
53
0.187
0.184
0.371
crudeoil 1i01
0.049
0.017
16819
11797
-1.000
-0 637
-0.758
crudeoil__ion 1102
0.013
0.013
12172
10426
-0.027
-0.027
16.
crudeoil li03
80
00
198
899
0.000
0.000
0.780
crudeoil lios
0.157
1031
0.408
crudeoil lio6
41
322
0.000
0.000
0.873
crudeoil_ lill
70
0.000
0.000
0.714
erudeoil_ poollllo__poogo_ooooo ct1
0.913
0.988
2-15
6356
0.046
0.046
0.638
crudeoil pooling et2
0.000
0.000
1480
1589
1.000
0.000
0.000
erudeoil_ poolllgooooonng_ooo ct3
42.222
120.618
101
0.650
0.650
0.650
crudeoil pooling ct4
0.000
0.000
7631
9217
0.365
0.153
0.041
du-apt
0.000
14174
1.000
0.000
du-opt5
0.000
0.000
83
60
1.000
0.000
0.000
Continued next page
28

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
edgecross 10-030
0.000
0.000
7
7
1.000
0.000
0.000
edgecross 10-040
0.000
0.000
30
39
1,000
0.000
0.000
edgecross 10-050
0.000
0.000
1,000
0.000
0.000
edgecross
10-060 10-060
0.000
0.000
2058
2138
1.000
0.000
0.000
edgecroes10-070
0.321
0.220
255
329
-0.437
-0.311
-0.115
edgecross 18-
0.077
0.077
352
668
0.001
0.001
0.474
odgecross 10-090
0.000
0.000
7
6
1.000
0.000
0.000
adgecross|44033 (4-039
0.000
0.000
624
731
1.000
0.000
0.000
edgecross
1.251
0.519
81
157
-1.000
-0.561
-0,180
edgecross
14-078 14-078
1.843
1.865
0.012
0.012
0.153
edgecross114-0g
1.120
1.129
21
31
0.007
0.007
0,232
edgecroe=111111
0.963
0.947
9
17
-0.017
-0.017
0.462
edgecross144115
0.537
0.552
20
30
0.028
0.028
0.352
odgreross 14-166
0.338
0.353
13
13
0.042
0.042
0.042
Algecross14-170
0.089
0,080
37
135
-0.117
-0.105
0.694
edgecrons20-010
0.000
0.000
71
57
1.000
0.000
0.000
edgecross20-080
3 3.943
3.943
7
0.000
0.000
0.000
edgecroes22-018
0.615
0.000
56
81
-1,000
-1,000
-1.000
edgecrons24-U57
5.219
5.219
7
6
0.000
0.000
-0.143
clf
0.000
0.000
115
112 1.000
0.000
0.000
ex2
0.000
0.000
17
17 1.000
0.000
0.000
ex2
0.000
0,000
1,000
0.000
0.000
ex2 1 5
0,000
0.000
17
19 1.000
0.000
0.000
ex2
0.000
0.000
13
13
1,000
0.000
0.000
ex2 1 7
0,000
0.000
1523
1831
1,000
0,000
0.000
ex2
0.000
0.000
75
93
1.000
0.000
0.000
ex2
0.000
0.000
3735
3947
1,000
0.000
0.000
ex3
0.000
0.000
405
271
1.000
0.000
0.000
0.000
0.000
27
1,000
0.000
0.000
ex3 1 4
0,000
0.000
23
23
1.000
0.000
0.000
ex1
0. 0.000
0.000
23
29
1,000
0.000
0,000
ex3 2 2 casel
0,000
0,000
39
19
1,000
0,000
0.000
ex5 2 2
case2
0.000
0.000
57
31
1.000
0.000
0.000
ex5_ 2 4
0.000
0.000
251
227
1,000
0.000
0.000
ex5 2 5
0.359
0.316
30-103
331922
-0.038
-0.036
0.058
0.000
31
1.000
0.000
ex5 3 3
0.339
0.331
29464
31558
-0.024
-0.024
0.044
ex3 4 2
0.000
0.000
41
35
1.000
0.000
0,000
ex8 3 2
23. 252
23.608
8907
8680
0,015
0.015
-0.011
ex8 3 3
23.004
23.004
9636
10365
0.000
0.000
0.070
3 4
1.817
1.793
9447
9563
-0.013
-0.013
-0.001
ex8 3 5
143 677
143.677
9-127
9699
0.000
0.000
0.028
8
2.071
2.071
2293
3677
0.000
0.000
0.376
ex8 3 9
12.106
12.106
14272
17310
0.000
-0.000
0.176
ex8 4 1
0.000
0.000
670
650
1.000
0.000
0,000
ex9_ 2
0.000
0.000
25
31
1,000
0.000
0.000
ex9 2_5
0.000
0.000
27
29
1.000
0.000
0.000
2_7
0.000
0.000
1.000
0.000
0.000
faclay20h
1.727
1.727
16
15
0.000
0.000
-0.062
faclay25
2.468
2.468
0.000
0.000
0.000
forest
0.003
0.020
29002
25913
0.860
0.859
0.831
gabriel01
0.139
0.139
6753
9744
-0.000
-0.000
0.307
gahricl02
0.556
0.585
1107
1675
0.050
0.050
0.372
gabriel04
00
1.308
129
285
-1.000
-1.000
-1.000
gabriel05
326
0,000
0.000
0.567
gasprod sarawak01
0,000
0.000
11
6
1.000
0.000
0.000
gasprod sarawak66
0.004
0.009
1052
0.585
0.585
0.800
gonpooling_leel
0.000
0.000
690
676
1.000
0.000
0.000
genpooling lee2
0.000
0.000
1299
2989
1.000
0. 0.000
0.000
gonpooling
0.957
0.691
12855
17889
-0.385
-0.278
0.005
=mppooling__eee100
1.276
1.385
1910
2815
0.078
0.078
0.375
genpooling meyer15
6.080
0.691
-0.516
graphpart 2g-0099-9211
0.000
0.000
18
14
1.000
0.000
0.000
graphpart 2pm-0077--777
0.000
0.000
5
1.000
0.000
0.000
0.000
0.000
9
7
1.000
0.000
0.000
graphpart 2pm-0099-0099
0.000
0.000
16
12 1.000
0.000
0.000
1aabpart__3g0034--000
0.000
0.000
21
41
1.000
0.000
0.000
graphpart 3g-03-1100311
0.000
0.000
61
19 1.000
0.000
0.000
graphpart 3g-0444-0444
0.000
424
1,000
0.000
0.000
graphpart snaphprrt_Spm-02444 -pm-0244-000044404-
0.000
0.000
21
15
1.000
0.000
0.000
gaaphartt_Apm-O255
0.000
0.000
20
38
1.000
0.000
0.000
Sephpartt_3pm-03---11
0.000
0.000
590
619
1.000
0.000
0.000
graphpart 3pm-0444-0411
0.058
0.000
755
1348
-1.000
-1.000
-1.000
maappartt_ellquee
0.000
0.000
22
24
1.000
0.000
0.000
0.000
0.000
421
337
1.000
0.000
0.000
graphpart clique-40
1.018
0.920
-0.106
-0.096
0.461
paappart__llquo--1
5.638
6.032
97
191
0.065
0.065
0.525
Continued next page
29

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
graphpart_cliqueee
17.434
9.335
109
204
-0.868
-0.465
0.002
graphpart clique-70
30.409
35.053
16
27
0.132
0.132
0.486
haverly
0.000
0.000
57
1,000
0.000
0.000
bimmel16
0.000
0.000
2193
2089
1.000
0.000
0.000
house
0.000
0.000
58675
58399
1.000
0.000
0,000
hybll
0.018
0.182
19172
15631
0.899
0.899
0.875
hydroenergyl
0.007
0.007
15060
18149
-0.088
-0.081
0.095
hydroenergy2
0.016
0.016
4834
6712
0.038
0.038
0.306
hydroeuergy3
0.022
0.023
565
1060
0.006
0.006
0.470
0.508
0.407
220
-0.248
-0. 1.9
0.677
Geil_circlee_eeGa
3.180
2,091
42813
16497
-0.519
-0.341
-0,285
kall circles c6b
2.635
1.452
38722
45596
-0.815
-0.419
-0.351
kall circles_cee c6c
33357
36374
0,000
0.000
0.083
kall ciil___rreee____
1.482
1.376
38682
43723
-0.077
-0.072
0.047
cill__eiclee__8a
32114
36202
0,000
0.000
0.114
kall hitcoleppooyooos_cpppp
0.000
0.000
44439
61102
-1.000
-0.733
-0.106
kall _
0.000
0.000
8621
7914
1,000
0.000
0.000
kall circlespolygonss_eppps
12369
13200
0,000
0.000
0.063
kall circlespolygous clp6a
80
80
404
628
0.000
0.000
0.357
kall cirrlessrostanglss_chhe c1r12
0.000
0.000
42587
48285
0.121
0.114
0.061
kall _ccrclerrettanglls_stttt
0.000
0.000
4372
3739
1.000
0.000
0.000
kall circlesrectanglle c6rl
5850
7908
0,000
0.000
0.260
kall circlesrectangles
c6r29
4181
$220
0.000
0.000
0.199
kall circlesrectangles.
.Gr39
00
00
2570
2966
0.000
0.000
0.134
kall congruenteircles
c31
0,000
0.000
101
95
1,000
0.000
0.000
kall congruenteircles c32
0.000
0.000
133
139
1.000
0.000
0.000
kall _ompgrenttcircles_.cl
0.000
0.000
27
31
1.000
0.000
0.000
kall _congruentcirrles_.t.
0.000
0.000
205
125
1.000
0.000
0.000
kall congruenteircles. c51
0.000
0,000
1197
1987
1,000
0.000
0.000
kall congruenteircles
c52
0,000
0.000
1767
1446
1.000
0.000
0.000
kall congruentciroles.
c61
0.000
0.000
27338
35199
1,000
0. 0.000
0.000
kall congruenteircles
c62
0,000
0,000
2879
6037
1,000
0,000
0.000
kall congruenteircles c63
0.000
0.000
2043
1729
1.000
0.000
0.000
kall _comgruenteiicles___
39102
43349
0.000
0.000
0.098
kall congruentccrrole__cr
0.000
0.000
141686
14089
1.000
0.000
0.000
kall diffcircles 10
2.276
4.054
32475
41241
U.439
0.439
0.558
kall
diffcircles 5a
0.000
0.000
2020
1218
1.000
0.000
0.000
kall diffcircles 5b
0.000
0.000
6360
5774
1.000
0.000
0,000
kall diffcircles
0,000
0,000
2827
2383
1,000
0.000
0.000
kall diffcireles
0.000
0.000
9408
9518
1.000
0.000
0.000
kall diffoireles__
0-406
0,219
48924
57747
-0.851
-0.460
-0.362
kall diffcircles
1.676
1.052
12056
18915
-0.59-
-0.373
-0,270
kup3-12
1.846
1.963
1987
2132
0.060
0.060
0.124
1op97ic
19
33
0.000
0.000
0.424
lop89Tcc
0.008
0.000
3041
1711
-1.000
-0.999
-0,995
muxcep-langford.3-1
1356
4038
0,000
0.000
0.664
ndre12
00
00
1394
3975
0.000
0.000
0.649
ndee12perap
1092
2994
0.000
0.000
0.635
ndee18
298
787
0.000
0.000
0.621
ndee13persp
0.536
0.546
2982
5662
0.018
0.018
0.483
ndee14
1.030
1.048
234
499
0.018
0.018
0.539
ndec14persp
1.044
1.080
572
1052
0.033
0.033
0.474
ndre15
1293
21
0.000
0.000
0.390
ndeelppersp
00
3227
6549
0.000
0.000
0.202
ndce16
107
0.000
0.000
-0.027
adce16persp
1035
2183
0,000
0.000
0.526
notmodd dol2
0.047
0.000
112
-1.000
-1.000
-1.000
netmod_kan karl
0.000
0.000
425
285
1.000
0.000
0.000
netmod kar2
0.000
0.000
275
285
1.000
0. 0.000
0.000
nous!
0.000
0.000
3092
2816
1.000
0.000
0.000
nous2
0.000
0.000
81
71
1.000
0.000
0.000
nuclearvb
1821
3817
0.000
0.000
0.523
nuclearve
1905
15:30
0.000
0.000
-0.197
nuclearvd
DO
3781
0.000
0.000
-0.333
nuclearve
877
5464
0.000
0.000
0.839
nuclearvf
80
00
256
3596
0.000
0.000
0.929
nvs13
0.000
0.000
9
1.000
0.000
0.000
nvs17
0.000
0.000
89
78
1.000
0.000
0.000
nys18
0.000
75
1.000
0.000
0.000
nvs19
0.000
0.000
161
154
1.000
0.000
0.000
nvs23
0.000
0.000
465
1.000
0.000
0.000
nvs21
0.000
0.000
2060
1914
1.000
0.000
0.000
p ball 10b
5p
2d m
0.000
0.000
353
326
1.000
0.000
0.000
p ballll__000 10b_0001000 _p_3d_
m
0.000
0.000
1204
1032
1.000
0.000
0.000
ball 10b 5p
4d
m
0.000
0.000
1424
1765
1.000
0.000
0.000
p ball 10b 7p
m
0.000
0.000
6178
6151
1.000
0.000
0.000
baal 15b
5p
2d
m
0.000
0.000
1377
2068
1.000
0.000
0.000
Continued next page
30

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
D p_ball_ _0p__pp_________________________
2d_m
0.000
0.000
1610
2039
1.000
0.000
0.000
ball 20b 5p 3d m
0.000
0.000
10647
11510
1.000
0.000
0,000
P hallll_ a0b 10p 2d
00
3795
4965
0.000
0.000
0.236
o_ball_a0b__ _p__p_ 10p_______ 2d_
0.000
0.000
2827
3275
1.000
0.000
0.000
p ball 30b 5p
m
0.000
0.000
10150
11489
1.000
0.000
0.000
p ball 30b Tp 2d
8511
11906
0,000
0.000
0.285
p P_hall 40b 5p 3d m
00
80
9620
13718
0.000
0.000
0.299
"_ball_00 40b 5p 100_4d__
8100
1182
0.000
0.000
0.315
pedigree_exte ex185
0.019
0.019
315
962
0.030
0.030
0.682
pedigree_ox443
0.000
0.000
1.000
0.000
0.000
valigree_sim-100
0.061
0.053
1091
1533
-0.156
-0.135
0.175
pedigree sp top1 250
0.053
0.036
61
173
-0.482
-0.325
0.477
pedigree sp top4 300
0.014
0.015
294
670
0.014
0.014
0.567
pedigree sp_______________ _tppgree____tpp__________ 21___to4_3330000 350tr
0.000
0.014
365
1096
1,000
0.999
1.000
_p____________________ pedigree_sp__opp___
0.050
0.057
28
39
0.125
0.125
0.372
pinene200
8C
00
12
12
0.000
0.000
0.000
pointpack06
0.000
0.000
2009
2051
1,000
0.000
0.000
pointpack08
0.015
0.000
35620
31315
-1,000
-0.999
-0,978
pointpack10
0.612
0.613
18366
22179
0.001
0.001
0.173
pointpack12
0.854
0.839
15197
17796
-0.018
-0.018
0.131
1ointpack14
1.535
1.537
8919
9550
0.001
0.001
0.067
pooling_sshyaapp
sdhyalpg
0.000
0,000
383
365
1,000
0.000
0.000
pooling adhyalstp
0,000
0.000
737
638
1.000
0.000
0.000
sacllingsdhylltpppp
0.000
0.000
611
806
1,000
0.000
0.000
pooling adhya2pg
0,000
0.000
569
588
1,000
0,000
0.000
pooling adlya2stp
0.000
0.000
832
934
1.000
0.000
0.000
0.000
0.000
345
288
1.000
0.000
0.000
0.000
0.000
377
289
1.000
0.000
0.000
pooling sdhyyasttp
0.000
0,000
1078
1,000
0.000
0.000
pouling adhyaštp
0,000
0.000
675
585
1.000
0.000
0.000
pooling sdhyadpp
0. 0.000
0.000
271
150
1,000
0.000
0,000
pooling adhyadstp
0,000
0.000
385
686
1,000
0,000
0.000
pooling adhyadtp
0.000
0.000
317
387
1.000
0.000
0.000
booling_benttaliet
0.000
0.000
2818
4434
1.000
0.000
0.000
pooling_digaabedd digabel16
0.000
0.000
27577
35207
-1.000
-0.715
-0, 160
pooling digabell8
0.013
4109
5110
-0.496
-0.168
pooling digabel19
0
0.001
14953
18095
0.168
0.166
0.267
pooling foulds2stp
0. 0.000
0.000
36
25
1,000
0.000
0,000
pooling foulds3stp
0,000
0.000
1084
416
1,000
0.000
0.000
pooling_foulddet foulds4stp
0.000
0.000
717
339
1,000
0.000
0.000
0.019
0.000
1808
2741
-1,000
-0.999
-0.999
pooling haverly2stp
0.000
0.000
10
12
1.000
0.000
0.000
pooling r12pq
0.000
237
1,000
0.000
pooling_rt2stp
0.000
0.000
109
195
1.000
0.000
0.000
pooling r12tp
0.000
0.000
53
57
1.000
0.000
0,000
pooling_sppadpe
0.038
0.031
2424
3666
-0,230
-0.187
0.187
popling_sppaampp
2.829
2.865
2577
3068
0.012
0.012
0.0
poollog_sapaaug
0.179
0.183
2804
3623
0.021
0.021
0,242
pooling #ppašpq
0.037
0.018
709
781
-0.995
-0.499
-0.448
pooling sppa5stp
3.959
3.959
0.000
0.000
0.209
pooling_sppaatp
1.579
1.579
299
448
0.000
0.000
0.333
poollog__ppaapp
0.007
0.007
222
295
0.000
0.000
0.247
pooling_spphOy
0.098
0.098
223
301
0.000
-0.000
0.259
popdynm100
00
00
7556
11105
0.000
0.000
0.320
popdynm25
1/1627
19016
0.000
0.000
0.232
popdyum50
12085
15262
0,000
0.000
0.208
portfol classical000
0.000
0.000
1.000
0.000
0.141
0.125
396
491
104
-0.
0.086
portfol rofffooooouus000___ 31
0.000
0.000
91
49
1.000
0.000
0.000
0.000
0.000
489
361
1,000
0.000
0.000
03
0.182
0.189
95
75
0.034
0.034
-0.183
portfol shortfall050
0.000
1.000
0.000
0.000
portfol shortfalllo 04
0.010
0.010
595
1398
-0.055
-0.052
0.551
portfol_shore satfol_shortfal/20000000
0.033
0.028
224
10.169
-0.145
-0.114
powerflow0009r
0.000
0.000
13230
13141
-1.000
-0.037
-0.003
powerflow001dr
0.001
0.001
8052
8011
0.368
0.366
0.316
powerflow00030r
0.023
0.034
369
403
0.328
0.328
0.384
powerflow0039r
0.017
0.016
212
224
-0.038
-0.05-1
-0.001
product
0.028
0.034
0.197
0.197
0.708
198.418
709
3352
1.000
1.000
1.000
qapw
351.271
874
2437
1.000
1.000
1.000
qp3
29875
32155
0.000
0.000
0.071
qspp
0
10
0
1
10
0.849
1.238
3860
3982
0.314
0.314
0.335
qspp__.
1.071
1.886
1314
3036
0.432
0.432
0.754
qppp
0
12
0
10
1.674
2.102
791
1817
0.204
0.203
0.658
qspp__
0
10
1.893
1380
0.394
0.594
0.725
qspp_
0
14
3.038
3.200
299
1081
0.050
0.050
0.737
Continued next page
31

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
/ullity/Node
qspp_ 15
1_1_10_1
4.356
4.293
229
544
-0.015
-0.015
0.573
ringpack 10 1
0.082
1.000
5346
6348
0.918
0.918
0.931
ringpack
2
0.082
0.811
5402
6366
0.899
0.899
0.914
ringpack 20_1
1.661
3.527
525
492
0.560
0.560
0.531
ringpack 20 2
9.000
9.000
239
183
0.000
0.000
-0,231
ringpack 20 3
6.251
6,251
272
243
0,000
0,000
-0.107
ringpack_30 30_2
14.000
14.000
36
49
0.000
0.000
0.265
sepl
0.000
0.000
39
29
1.000
0.000
0.000
slay0th
0.000
0.000
8
8
1.000
0.000
0.000
slay04m
0.000
0.000
1.000
0.000
0.000
slay05h
0,000
0.000
61
119
1,000
0.000
0,000
slay06h
0.000
0.000
120
208
1,000
0.000
0.000
slay06m
0.000
0.000
8
1.000
0.000
0.000
slay07h
0.000
0.000
420
952
1.000
0.000
0.000
slay07m
0.000
0.000
218
501
1,000
0.000
0.000
elay08h
0.000
0.000
513
1181
1.000
0.000
0.000
slay08m
0.000
0.000
193
564
1.000
0.000
0.000
slay09h
0.104
0.135
612
188
0.229
0.229
0.033
slay09m
0.000
0.000
324
212
1.000
0.000
0.000
slay10h
0.103
0.407
703
451
0.746
0.745
0.603
slay|0m
0.000
0.000
3933
4138
1.000
0.000
0.000
smslllavDAAx1101000001
0.000
0,000
321
264
1,000
0.000
0.000
smaallaayDDAx111122--0p
0,000
0.000
657
9U6
1.000
0.000
0.000
0. 0.000
0.000
6083
4430
1,000
0. 0.000
0.000
sutallivvDDAXx1110001100
0,000
0.000
13366
31917
1,000
0,000
0.000
smaillaay/DAAxx1155000.66
0.000
0.001
26952
40900
1.000
0.986
0.730
smaallin//DAXx1112000020
0.000
0.001
38238
46021
0.348
0.342
0.269
sma/llnvD44X:2b0000001
0.000
0.000
254
3G8
1.000
0.000
0.000
0.000
0,000
1201
2016
1,000
0.000
0.000
smailllayDDAXxr2a55000006
0.000
0.000
7868
6682
1.000
0.000
0.000
SmnalllavDDAAXxx2000-11100
0. 0.000
0.000
12971
14333
1,000
0.000
0.000
smialllayDDDAXr225500
0,000
0,000
39670
68543
1,000
0.966
0.421
smaillin/DDAXx2222000222
0.000
0.000
712
651
1.000
0.000
0.000
smallinn/D44r3hh010000
0.000
0.000
260
358
1.000
0.000
0.000
smalllayDAA:::3002222
0.000
0.000
1676
906
1.000
0.000
0.000
smislllav.DDAXr33a5555555
0.000
0,000
5716
5024
1,000
0.000
0.000
smaillinyDDA:r331000000
0.000
0.000
39948
13726
1.000
0.000
0.000
0. 0.000
0.000
3/1009
22132
1.000
0.000
0,000
smaalllayy-DAXr3322000000
0.000
0.000
1078
433
1,000
0.000
0.000
smailliny/A4Xxr4010000000
0.000
0.000
272
202
1.000
0.000
0.000
smaallln/DDAx::1h0000-0
0.000
0.000
1078
990
1,000
0.000
0.000
sma.llayy
0.000
0.000
3098
2666
1.000
0.000
0.000
0.000
0.000
26316
1.000
0.000
smaallin/DAAXx4-1550---11
0.000
0.000
32042
56419
1.000
0.000
0.000
smaalllayyDAAXrrrzzooo0-2
D. 0.000
0.000
935
612
1.000
0.000
0,000
smaillinw/DAArr5h11100000
0.000
0.000
242
381
1,000
0.000
0.000
smallinn/DAAXxtth22000022
0.000
0.000
1798
884
1.000
0.000
0.000
smalllav/DAAx:3b050--00
0.000
0.000
4276
3312
1,000
0.000
0.000
smaillaayDAAXxrsi100011000
0,000
0.000
37028
72501
1.000
0.980
0.570
smailian-DAAArri1500011
0.000
40757
78031
1.000
0.966
0.414
Smallin/DAANx:h220-220
0.000
0.000
783
585
1.000
0.000
0.000
sonet22v5
3.752
2.911
105
356
-0 08289
-0.224
0.620
sonct23y4
1.407
1.366
181
-0.030
-0.029
0.550
sonet24v5
4.070
3.914
21
212
-0.040
-0.038
0.897
sonet25v6
5.161
1.812
45
-0.072
-0.068
0.762
sonetgr17
2,252
2.602
400
1247
0.134
0.134
0.722
space25
154
0.000
0.000
-0.071
spectra2
0.000
0.000
8
8
1.000
0.000
0.000
squf1010-025
0.000
0.000
71985
75945
0.692
0. 0.000
0.000
squff010-040
0.000
0.000
18478
20101
0.529
0.000
0.000
squft010-080
0.000
0.000
4509
$339
0.568
-0.000
0.000
squuB011-0080persp
0.000
0.000
6
1,000
0.000
squff015-060
0.000
0.000
7372
10223
0.608
-0.000
0.000
squft0155000perrsp
0.000
0.000
1.000
0.000
0.000
squff015-080
0.000
0.001
3-175
6667
1.000
0.993
0.976
squfl020-040
0. 0.000
0.000
8358
10679
0.370
0. 0.000
0.000
squff020-050
0.000
0.000
4094
8025
0.365
-0.000
0.000
squfl020-150
0.014
0.011
9
7
0.000
0.000
-0.222
scuuft220-150persp
0.000
0.000
1.000
0.000
0.000
squfl025-025
0.000
0.000
15093
11992
0.997
-0.000
-0.000
squff0225-025persp
0.000
0.000
12
1.000
0.000
0.000
squfl025-330
0.000
0.000
5523
14798
1.000
0.000
0.000
=qufl0255-33persp
0.000
0.000
6
6
1.000
0.000
0.000
squfl025-040
0.000
0.000
64138
7800
0.519
0.000
0.000
#qufl025-040persp
0.000
0.000
12
12
1.000
0.000
0.000
squft030-100
0.000
1291
1402
0.289
0.000
squft040-080
0.000
0.001
1034
1477
1.000
0.983
0.983
Continued next page
32

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility/Node
squft0-40-050persp
0.000
0.000
8
8
1.000
0.000
0.000
assd08-04petsp
0.000
0.000
20080
17359
1.000
0.000
0.000
seed 12-05persp
0.131
0.133
63030
73358
0.016
0.016
0.154
sesd 13-04persp
0.188
0.181
76121
77773
-0.041
-0.039
-0.018
sesd 15-06ppers
0.285
0.260
43387
17623
-0.095
-0.087
0.002
sed 13-U8perpp
0.235
0.234
30374
41340
-0,005
-0.005
0.261
sed sed16607persp
0.232
0.214
41858
46101
-0.086
-0.079
0.014
ssed 118-06perep
0.200
0.188
40346
48551
-0.063
-0.059
0.117
ses11--8ppess
0.383
0.372
31676
41811
-0.028
-0.027
0.221
sed22-00persp
0.202
0.202
63012
69887
0.002
0.002
0.100
ss<d20-08perap
0.202
0.195
27951
34670
-0.036
-0.035
0.161
sss222-0peesa
0.228
0.212
31593
33795
-0.077
-0.071
-0,007
0.178
0.172
27400
33837
-0.038
-0.037
0.159
st baj2
0.000
0.000
17
15
1,000
0.000
0.000
e0
0.000
0.000
59
75
1,000
0.000
0.000
st e21
0.000
0.000
7
7
1.000
0.000
0.000
st e2
0.000
0.000
15
1,000
0.000
0.000
e30
0,000
0.000
17
61
1,000
0.000
0.000
st e31
0.000
0.000
393
490
1,000
0.000
0.000
fp70
0.000
0.000
297
345
1,000
0.000
0.000
st fp7b
0.000
0.000
349
341
1.000
0.000
0.000
fpTe
0.000
0,000
253
1,000
0.000
0.000
st fp7d fp7e
0,000
0.000
277
355
1.000
0.000
0.000
0.000
0.000
1605
1831
1,000
0.000
0.000
fp8
0,000
0.000
69
63
1,000
0,000
0.000
st ghup _s1
0.000
0.000
23
25
1.000
0.000
0.000
0.000
0.000
11
1,000
0.000
0.000
st iqpbkl
0.000
0.000
37
37
1.000
0.000
0.000
1qpbk2 st jebpaf2
0.000
0,000
37
1,000
0.000
0.000
0,000
0.000
9
13
1.000
0.000
0.000
st. ml m2
0. 0.000
0.000
783
383
1,000
0.000
0,000
0,000
0,000
637
619
1,000
0,000
0.000
st. 1_panl
0.000
0.000
11
11
1.000
0.000
0.000
st_ph1
0.000
0.000
11 1.000
0.000
0.000
st ph12
0.000
0.000
13
13
1.000
0.000
0.000
ph13
0,000
0,000
9
1,000
0.000
0.000
st qpe-ml qpe-m3a
0.000
0.000
15
17 1.000
0.000
0.000
0. 0.000
0.000
1269
1291
1.000
0.000
0,000
qpkl
0,000
0.000
1,000
0.000
0.000
st qpk2
0.000
0.000
27
27
1,000
0.000
0.000
0.000
0.000
137
133
1,000
0.000
0.000
st rvl
0.000
0.000
107
81
1.000
0.000
0.000
rv2
0.000
0.000
133
1,000
0.000
0.000
st st_rv3
0.000
0.000
511
629
1.000
0.000
0.000
st IV7 __rv8
0.000
0.000
1143
1153
1.000
0.000
0,000
0.000
0.000
1047
1269
1,000
0.000
0.000
st st_rv9 rv9
0.000
0.000
3349
1875
1.000
0.000
0.000
testgr1 st 2
0.000
0.000
21
1,000
0.000
0.000
0,000
0.000
9
9
1.000
0.000
0.000
supplychain
0.000
0.000
95
1.000
0.000
0.000
12
0.295
0.217
20517
22042
-0.362
-0.266
-0.
tln4
0.000
0.000
13
25
1.000
0.000
0.000
tln6
0.000
0.000
40
38
1.000
0.000
0.000
thn?
0.075
0.121
52425
60523
0.375
0.375
0.457
toroidal3g7_660
0.200
0.117
-0.706
-0.414
0.592
tricp
275
356
0,000
0.000
0.228
0.000
0.000
38
1.000
0.000
0.000
wastewater02m1
0.000
0.000
43
43
1.000
0.000
0.000
wastewater02m2
0.000
0.000
35
31
1.000
0. 0.000
0.000
wastewater04mm
0.000
0.000
117
81
1.000
0.000
0.000
w wastewaterOdmm
0.000
0.000
25
25
1.000
0.000
0.000
wastewatertSmi
0.000
0.000
2561
3017
1,000
0.000
0.000
0.000
4068
7429
1.000
0.000
0.000
waste waterttrr
0.116
0.131
40219
43385
0.113
0.113
0.1
waste water 1m2
0.385
0.431
15161
15304
0.106
0.106
0.114
waste watteattr12m1
0. 0.099
0.015
23070
25082
-1.000
-0.3/11
-0.110
12m2
0-460
0.654
7232
7822
0.296
0.296
0.349
w
wastewaterr133
0. 0.146
0.370
12150
16381
-0 -0.207
-0.171
0.105
wastewater113m2
0.538
0.538
6204
6129
0.000
0.000
-0.012
wastewater14mm1
0.151
0.122
38064
42510
-0.236
-0.191
-0.096
wastewater 14m2
0.191
0.200
11743
13355
0.084
0.084
0.194
wastewster15m1
0.000
0.000
7735
$130
1.000
0.000
0.000
wastewater15m2
0.000
0.000
34228
59163
0.982
-0.000
-0.000
waterrontaamllnntion0003
0.000
0.000
9
1.000
0.000
0.000
watercoutaamiaatiouuuS0ss
00
22
37
0.000
0.000
0.405
waterund01
0.000
0.000
49001
57176
-0.021
0.056
waterund08
0.000
0.000
38355
41489
0.335
0.083
0.003
Continged next page
33

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Gap Ours
Gap Base
Nodes Ours
Nodes Base
Reward
Utility
Utility /Node
waterund!1
0.001
0.001
35021
40695
-0.736
-0.420
-0.241
waterund14
0.009
0.009
9789
10684
-0.012
-0.012
0.072
waterund17
0.545
waterund
0.001
0.001
34080
36286
0.049
0.048
0.085
vaterund22
0.016
0.017
10195
10702
0.016
0.016
0.062
waterund25
0,080
0.094
11100
10382
0.154
0.153
0.095
waterund27
0.089
0.089
2253
2835
0.001
0.001
0.206
waterund28
0.080
0.080
17
0.000
0.000
-0.056
waterund36
0.100
0.082
1811
2143
-0.217
-0.178
0.083
Mean
6315
7463
0.487
0.000
0.114
J Alternative value function estimation
Benchmark
Reward
Win-rate
geo-mean Ours
geo-mean SCIP
TSPLIB (Reinelt, 1991
0.150
0.68
0.86
0.957
UFLP Kochetov & Ivanenko, 2005
-0.071
0.39
0.569
0.552
MINLPLIS (Bussieck et al.. 2003
0.497
0.84
32.5
31.185
MIPLIB (Gleixner et al. 2021
0.038
0.61
789.31
848.628
TSPLIB@5mm
0.173
0.63
1.73
2.000
MINL.Pib@5min
0.507
0.82
18.04
20.460
MIPLIB@5min
0.282
0.77
44.892
106.400
We compare different value function (s)) parametrization, which be interpreted the value function as on-policy q-values V(s) ((ass)((ss a) da and the fact that our actions correspond to individual nodes:
Q(1ls) (n)ss)
(18)
[P(r, n)l
@([(s)) Q(left(s) (right|s) (n)(()))s))
(19)
V(s) Σ (nl)dd)
(20)
VNES
where (lhn)) the learned per-node estimator, Q the unnormalized Q-value, and & the set of open nodes
proposed by the branch-and- interpret the path estimates Q as the on-policy q-values for each path. Having access to the q-values may be necessary for different actor-critic methods or the use of Deep Q-learning (Mnih et al. 2013)
method. The advantage of this interpretation is that it allows one to
K
Pseudocode
A Algorithm Pseudocode for node selection using our policy
1: procedure NODE SELECTOR
Apply message passing over tree T using Eq.
Compute root-to-leaf paths using Eq. g
Compute policy over selectable leaves using Eq.
9
The value-function is only needed for training
Sample selected node n
6: run SCIP on n to get new children 61
7: append and C2 as children to in tree T
8: (if necessary) prune T according to SCIP pruning rules
For training, we set Nuer 16, K 128, and 0.1, and the weight of the entropy regularization Aent = 0.01. In general, the policy improvement the original PPO loss proposed in (Schulman et al. 2017), combined with implementation improvements provided in (Huang al. 2021
20221.
34

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Pseudocode for training our policy
1:
procedure POLICY DALLIY_EVALLATIONNE
sample random instance according to Section 4.4
Solve using SCIP for 45s and node selector Alg. 2
record all trees {T;)0 selected nodes {a:b0' and
final optimality gap
Solve using SCIP for 45s without our node selector and record the final gap
5:
compute the reward r using Eq. B
6:
compute the returns R(ss;) = 7
7:
Compute Advantage {A.)) using GAE Schulman et al. 2015) for all {T:10 using value from Eq. 12
return (T:)0' {a 1. (Ar), R(s{)
procedure POLICY IMPROVEMENT copy policy function π to Told copy value function V to Vold for iteration=i... Nater do
SCHULMAN ET AL, (T, (a.oo (A,) R(s)))
10:
11:
12:
Optimize PPO-clip loss
(a,(TT))
(T(T) min (ola(a;(T)) (T)
A, clip
2, A. (o,
dent ((x)
13:
using minibatch of size K sampled from the exploration data. Optimize Value estimate using clippe value-estimation
14:
mean (R(s:) V(s)))
clipped = (st) + clip(V.ta (5t) - V(s)), -,, +e)
L, max(mean, (tippeee
15: using minibatch of size K sampled from the exploration data. return n,
16: procedure TRAIN(T V) for Iterations do (T:)d, {ar)o' {A.)), R(x)) + Policy Evaluation(T))
17:
18:
π, V + Policy [atto____looveee(([1333 (adl'' (AJ)., R(s:))
19:
return म,
35


Reviews:
[{"review_id": "Al9J8olmMx", "reviewer": "Reviewer_EJge", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. Clear motivation and good presentation.\n2. The idea of the proposed method is intuitive and simple, and the experimental results fully demonstrate the proposed method's promising performance.\n\nWeaknesses:\n1. More learning-based methods can be included for comparison.\n2. The feature selection for the model input can be optimized.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work uses (Reinforcement Learning) RL to train a Graph Neural Network (GNN) to learn the policy for branch-and-bound (BnB) node selection for solving mixed-integer (nonlinear) programming problems. The GNN captures the features inside the BnB tree structure and produces the probability of selecting nodes. The experiments demonstrate the superior performance of the proposed method compared to classical solver SCIP and a state-of-the-art learning method on multiple benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. There are abbreviations (e.g., GNN) but no full names, please check the paper to correct it.\n2. A summary of contributions in the introduction may help the reader get the points better. \n3. It is recommended to include a pseudocode for the whole framework to help the reader understand the proposed method easier.\n4. The tenses of the articles need to be consistent. For example, in Section 5.5 Ablations, the first and second paragraphs use inconsistent tenses.\n5. \"4.1 Reward definition\" -> \"4.1 Reward Definition\".", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "P1P78iPIqr", "reviewer": "Reviewer_4fth", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The method is well-designed, improving upon previously existing methods in terms of its ability to utilize information about the branch-and-bound tree, and specifics of the algorithm such as reward functions or the setup for applying reinforcement learning are well thought out, addressing some of the challenges remaining in previous works.\n- The experiments are thorough in terms of the variety of the benchmarks used, convincingly proving that the algorithm generalizes well beyond the TSP instances it was trained on.\n- The paper includes an interesting discussion of the insights drawn from the trained model, which, on the one hand, are in line with what is already known by the optimization community, and, on the other hand, provide new information on what node and tree properties may be relevant.\n\nWeaknesses:\n- The short time limits impose a limitation on the conclusions one can make regarding the method's performance for solving challenging instances to optimality or small gaps, which is one of the main tasks in optimization research, as improvements on such instances mean pushing the boundaries of what problems algorithms can solve. The paper does mention this weakness, and it attempts to somewhat alleviate it by arguing that the results generalize well from 45s to 5min. However, with longer runtimes solvers may shift into different 'modes' of solving, for instance, when a good feasible solution is found and what remains is proving optimality, and what works well for the initial few minutes might not perform well when the solver is run for an hour or two. I understand, however, that learning, and learning in the context of branch-and-bound, is a very computationally expensive task, and these limitations are out of the authors' control.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel application of reinforcement learning to the problem of node selection in branch-and-bound algorithms. The proposed method builds a graph neural network that is similar in graph structure to the branch-and-bound tree, capturing the properties of individual nodes as well as the tree structure. The model is trained on a carefully constructed set of intermediate-difficulty traveling salesman problems and then tested on multiple different benchmarks, including benchmarks comprised of different instances of the same problem, and heterogeneous benchmarks containing mixed-integer linear and nonlinear problems. Within the time limits used in the paper, the proposed method demonstrates considerable improvements and good capabilities for generalization to adjacent problem classes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- While the paper states its limitations (that stem from limited computational resources) quite clearly, I would suggest that they are also mentioned in the introduction and/or abstract, for example the fact that the training and tests are conducted with small time limits.\n- Figure 1: acronym MLP undefined.\n- Page 3, second to last paragraph: another paper proposing an ML-based cut selection method is \"Adaptive Cut Selection in Mixed-Integer Linear Programming\" by Turner et al.\n- Equation 5: a full definition of the notation used in the equation would help readability, especially for readers not used to this notation.\n- Equation 6: does gap(scip) denote the gap achieved by default SCIP after making one node selection decision from the same state of the tree? A clarification of the definition would be helpful here.\n- In Section 5.2.1 and below, there are a few misspellings of the word 'lose'.\n- Page 10, third to last paragraph: 'seperate' should be 'separate'.\n- What was the exact setup of the experiments in Section 5.4?", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cscNftfEkj", "reviewer": "Reviewer_W5VF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe technique is novel and well-designed as far as I can assess.\n\nThe authors obtain a consistently high performance on a variety of problem instances without the need to retrain. \n\n\nWeaknesses:\n\nThe writing can be improved in some cases, primarily in terms of better introducing terms (see requested changes for concrete suggestions).\n\nThere is an error in the definition of the advantage function in the experiments. That is, the value used for its computation is using the maximal Q-value rather than the Q-value expected under the policy. This is not on-policy and is not in so it seems like experiments may need to be rerun with the correct definition. On the positive side, that means that the results obtained might be even better after rerunning them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present a work using reinforcement learning to learn policies for node selection in branch-and-bound algorithms for Mixed Integer Programming problems. Their technique improves on existing baselines, including the common software package SCIP as well as the baseline of Labassi et al. Rather than requiring a new optimisation for each problem instance, the technique allows pre-training and out-of-distribution performance that goes beyond other techniques that are problem-specific. It also allows for incorporating time consumption as an objective due to allowing rewarding low computational cost.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Section 1 to 2\n\n“For simplicity, we focus our explanation to the case of mixed integer linear programs (MILP) while our method theoretically works for any type of constraint allowed in SCIP” \n\n--> This is a comment about theory but refers to a software package. It would be more suitable to describe what kind of constraints are allowed. \n\n“If a node has an upper bound larger than a currently found integral solution, no\nnode in that subtree has to be processed.”\n\nI believe this should be the lower bound rather than the upper bound. If a node has a lower bound larger than a previously found solution, there is no point in checking that node (in a minimisation problem) since it cannot be the optimum.\n\n\nThe optimal diving oracle is mentioned many times but is never introduced or even paraphrased.\n\nSection 3\n\n “Another frequently learned heuristic are cut-selection methods” --> Other frequently learned heuristics are cut-selection methods\n\n“Cut selection is part of an extension of branch-and-bound\nknown as branch-and-cut, which additionally adds constraints to sub-problems.”\n\nI think you should mention what kind of constraints and what their purpose is.\n\n\nSection 4\n\nThe graph, and the corresponding actions, are dynamically changing. This approach may be computationally prohibitive for large graphs. \n\nSection 4.1\n\nThe use of text in eq. 6 and 14  in Section 4.1 is not particularly, aesthetic, and scip should be capitalised.\n\nSection 4.2, \n“For processing the tree T , we use message-passing from the children to the parent.”\n\n--> from parent to its children\n\n\nSection 4.3:\nThe description of PPO does not seem correct and is incomplete. Since PPO formulates stochastic policies, the value function is typically the expected Q-value over the policy (not the maximum Q-value over states). Also there is no mention of the typically used generalized advantage estimation (GAE) scheme.  Looking at the code, the TreeList.py file includes the line \nvds.append(max(vdict.values()))\n\nso I believe the mistake is also in the experiments and the evaluation is actually not on-policy. \nConsequently, the authors may get a better performance if they redo the experiments with V_pi rather than V*. I see that the code uses GAE (which is standard in PPO) so the authors can also mention this in the text.\n\nSection 5\n\nIn Table 1, the authors choose to evaluate based on a particular time limit. Is there no way to evaluate this in terms of a more hardware and software independent manner? The number of nodes for instance. However, I understand that one of the claimed benefits of the RL technique is also allowing time optimisation.\n\nthe caption of Table 1 can be improved. The last two columns represent comparisons of the geometric mean of your method vs SCIP. However, the mean of what? And what do the other columns represent? A little bit more info can be found in the text but tables should be self-contained.\n\nSection 5.4: the authors find that their method allows improved performance with a single network trained out-of-distribution, while Labassi et al.  use different networks train on the specific problem instance.\n\nlabassi --> Labassi\n\n\nSection 5.5 presents results for interpreting the policies, and use an interpretability algorithm to this end.\n\nGeneral comment: the results do not contain any statistics for the spread (e.g. standard deviation).\n\n\nReferences \nBestuzheva 2021a and Bestuzheva 2021b are identical references.\n\n\nAppendix B:\nEq. 13 seems to be somewhat out of place. It is written just below a text where the authors talk about evaluating all paths, but actually refers to a single path. It may be more suitable to give the equation for log probabilities below the equation for p(leaf). \n\n\nAppendix G:\nMathmatically --> Mathematically", "broader_impact_concerns": "No ethical conerns raised.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find the proposed method is novel, well motivated and well-designed, and they also appreciate the thorough experiments that clearly show the promising performance of the proposed method. After rebuttal, most of the raised concerns were properly addressed, and one reviewer voted to accept this paper while two reviewers leaned toward accepting. 

I read the paper in detail and totally agree with all reviewers that this work clearly meets the TMLR acceptance criteria (solid and well-supported claims, potential audience). In particular, it is promising to see a fixed policy pretrained on synthetic TSP instances can perform well on the heterogeneous instances in MINLPLib and MIPLIB. Therefore, I am happy to accept this work as is.
Decision: Accept (poster)