Learning to Select Nodes in Branch and Bound with Sufficient Tree Representation
Authors: Sijia Zhang
Shuli Zeng
Shaoang Li
Feng Wu
Xiangyang Li
Venue: ICLR 2025 Poster (2025)
Keywords: branch and bound; mixed integer linear programming
Primary area: optimization

Abstract: Branch-and-bound methods are pivotal in solving Mixed Integer Linear Programming (MILP), where the challenge of node selection arises, necessitating the prioritization of different regions of the space for subsequent exploration. While machine learning techniques have been proposed to address this, two crucial problems concerning \textbf{(P1)} how to sufficiently extract features from the branch-and-bound tree, and \textbf{(P2)} how to assess the node quality comprehensively based on the features remain open. To tackle these challenges, we propose to tackle the node selection problem employing a novel Tripartite graph representation and Reinforcement learning with a Graph Neural Network model (TRGNN). The tripartite graph is theoretically proved to encompass sufficient information for tree representation in information theory. We learn node selection via reinforcement learning for learning delay rewards and give more comprehensive node metrics. Experiments show that TRGNN significantly improves the efficiency of solving MILPs compared to human-designed and learning-based node selection methods on both synthetic and large-scale real-world MILPs. Moreover, experiments demonstrate that TRGNN well generalizes to MILPs that are significantly larger than those seen during training.

Published as a conference paper at ICLR 2025
LEARNING TO SELECT NODES IN BRANCH AND BOUND WITH SUFFICIENT TREE REPRESENTATION
Sijia Zhang, Shuli Zeng, Shaoang Li, Feng Wu " Xiang-Yanng Li School of Computer Science and Technology, University of Science and Technology of China {sxzsj, zengshuli0130, l sishaoa @@mai 1. .sstccc..... edu. [wufeng02, xi angyangl settyyannggggutc....ommm
Jesstc. edu.
ABSTRACT
Branch-and methods pivotal in solving Mixed Integer Linear Program- ming (MILP), where the challenge of node selection arises, necessitating the pri- oritization of different regions of the space for subsequent exploration. While chine learning techniques have been proposed to address this, two crucial prob- lems concerning (P1) how sufficiently extract features from the branch-and- bound tree, and (P2) how to assess the node quality comprehensively based on the features remain open. To tackle these challenges, we propose to tackle the node selection problem employing novel Tripartite graph representation and Rein- forcement learning with Graph Neural Network model (TRGNN). The tripartite graph is theoretically proved to encompass sufficient information for tree repre- sentation in information theory. We learn node selection via reinforcement learn- ing for learning delay rewards and give more comprehensive node metrics. Exper- iments show that TRGNN significantly improves the efficiency solving MILPs compared to human- designed and learning- based node selection methods both synthetic and large-scale real-world MILPs. Moreover, experiments demonstrate that TRGNN well generalizes to MILPs that significantly larger than those seen during training.
INTRODUCTION
Mixed-integer linear programming (MILP) is general optimization formulation for wide range of important real-world applications (Zhang et al.] (023), such as industrial process schedul- ing (Floudas& & Lin 2005), resources allocation (Ren & Gao 2010), and logistic operations (Paschos) 2014), etc. Modern MILP solvers (Gurobi Optimization, LLC (023) Bestuzheva et al. (202)) rely on the branch-and-bouu
(B&B) algorithm (Land Doig 1960). which recursively divides the search space into a tree, solving relaxations of the problem until an integral solution is found and proven optimal. Throughout this procedure, numerous decisions must be repeatedly made (Linderoth & Savelsbergh]] (199)), including node selection, and branching variable selection, etc. These decisions often dramatically impact the overall performance (Kianfar) 2010). Traditionally, these would be made according to hard-coded expert heuristics implemented in solvers. To further improve the efficiency of MILP solvers, more and more attention is given to statistical learning approaches for replacing and improving upon those heuristics (Bengio et al. 2021).
Here, we focus on the node selection problem, which has a significant impact on the overall solver performance (Achterberg) 2007). Current machine learning-based node selection methods (He et al, 2014 Song et al. 2018; Yilmaz & Yorke-Smith 2020 Labassi et al.] 2022) predominantly extract features from subset of candidate nodes, supplemented by manually extracted global tree features such as global upper and lower bounds. These methods primarily employ imitation learning to mimic an oracle which prioritizes node if contains the optimal solution.
However, the existing learning-be bearning-based node selection methods (Labassi et al. 2022 Yilmaz & Yorke- Smith 2020 He al., 2014; [Song et al., 2018) suffer from two limitations. Firstly. while indi- vidual MILP problems can be effectively represented using bipartite graphs (Gasse et al. 2019
"Corresponding author.

---

Published as a conference paper at ICLR 2025
Ding al. 2020: Nair al., 2020: Gupta et al. 2020 Paulus et al. 2022 Khalil al. 2022
Shen et al. ing single MILP problem. It necessitates the representation of the entire branch-and-Be which includes numerous nodes, each of which can be considered an individual MILP problem. However, representing all nodes in the tree bi- partite graph is not feasible for large-scale problems due to the exponential increase in node count. For in- stance. the "Anonymous" dataset, rooted in large- scale industrial context (Gasse al. 2022), necessi- tates that SCIP handle upwards of 50,000 nodes. The previous work compares the nodes among the candi- date nodes two by two to select the optimal node. They only represent the two currently selected nodes to be compared as a bipartite graph, supple- mented by manually extracted global features, such global upper and lower bounds and the depth of nodes. However, these manually extracted features do not fully capture the solving process of the branch-and-bout bound tree. Secondly, the recent work (Labassi et al.) [222] Yilmaz & Yorke-Smith, 2020 He et al.) 2014; [Song et al.] 2018)) which is based on the imitation learning approach, is limited by the performance of the expert itself. However, the oracle sometimes fails to outperform
2021: | Labassi et al. 2022). node selection problem requires more than just represent-
tree,
Table 1:
Comparison between the expert strategies and SCIP in GISP(n E [70, 80)).
Method
Time(s)
Wins
Nodes
SCIP
7.54 # 1.39
26/50
397.46 + 2.59
Expert
7.82 1.44
24/50
276.71 2.82
SCIP, as observed in datasets like GISP (Colombi et al.) (2017). as shown in Table 1 does not beat a baseline, imitating it is unlikely to bring gains.
If the expert
To overcome the aforementioned challenges, we propose to tackle the node selection problem em- ploying a Tripartite graph representation and Reinforcement learning with a Graph Neural Network model (TRGNN). Firstly, we propose a tripartite graph to represent the maanch-and-bound tree, which theoretically proved to be sufficient in information theory. Secondly, we introduce a re- inforcement learning framework for learning delay rewards in the branch-and-boumd process and give more comprehensive node metrics. These metrics include the global gap, the node potential and the overhead of path switching, which is the transition between the current node and the subse- quent selected one.
We evaluate our approach six NP-hard MILP problem benchmarks, which consist of three clas- sical synthetic MILP problems and three real-world MILP problems from diverse application ar- eas. Experiments show that TRGNN significantly outperforms desinnd and learning- based node selection methods in terms of solving time. We achieve up to 31.44% reduction on synthetic instances and up to 59.42% reduction on real-world instances. Notably, TRGNN the only known learning-basse based node selection method to surpass the default SCIP across all of the six datasets in terms of solving time. Moreover, experiments show that TRGNN can well generalize to MILPs that are significantly larger than those seen during training.
2 RELATED WORK
by applying imitation learning. They trained support vector machine (SVM) replicate the decisions of acle that selects nodes along the optimal solution path. Their model leveraged hand-crafted features, including node-specific attributes and global metrics like the number of solutions found and the cur- rent global bounds. However, their approach primarily focused on combining node selection with a learned pruning model, which aimed to cut off unpromising branches in the branch-and-bow baund tree. Their strategy was more akin to a primal heuristic, emphasizing the quick discovery of feasible solutions rather than guaranteeing optimality. They reported improvements in the optimality gap against SCIP under time limit and Gurobi under node limit four benchmarks.
He et al. (2014) were the first to explore node selection heuristics in
Song et al. 2018) proposed RankNet model combined with a novel retrospective imitation learn- ing method. In contrast to He et al. (2014), they focused solely on node selection without an additional pruning operator. They retrospectively correct the node selection trajectory into a short- est path to the best solution found. When the solver runs until optimality, the trajectory mirrors those generated by a diving oracle. They generated these trajectories using Gurobi and trained the model with the DAGGER (Ross et al., (011) and SMILe (Ross & Bagnell (010) imitation learn- ing algorithms. Their method demonstrated significant improvements in the optimality gap under node limit on path planning integer programs. However, they reported less favorable results on
2

---

Published as a conference paper at ICLR 2025
more challenging benchmarks, such as combinatorial auctions, indicating limitations in the model's generalizability to more complex problems.
Yilmaz& & Yorth-Smith 2020) extended the work of He et al. (2014) by proposing neural network- Their method can be viewed as a refinement of (Song al. (2018)'s 's neural network node selector, with the key difference being that it only evaluates children of the current node and defaults to depth-first search otherwise. Using the state encoding from Gasse et al. (2019), they trained their model mimic an oracle that prioritizes nodes leading to one of the top k solutions, essentially generalizing [He et al. (2014)ss oracle. On three benchmarks, they reported improvements in both time and number of nodes, and in some cases, reduced node counts compared to SCIP. However, their approach still lagged behind SCIP in terms of solving time, showing limitations in overall efficiency despite the node count improvements.
based node selection operator for
Inspired by the work of [asss et al. (2019) for variable selection in branch-and-bouud al.] (2022) considered a node selection strategy that compared nodes in the candidate queue pair by pair to identify the optimal node. They represented only the two currently selected nodes as bipartite graphs, supplemented by manually extracted global features such as the global upper and lower bounds and the nodes' depth. On three benchmarks, they reported reductions in the node counts of the branch-and- bound tree and demonstrated time improvements over SCIP on one dataset. However, like earlier efforts, their method underperformed on other datasets in terms of solving time. Notably, even the oracle failed to outperform SCIP's default rule on certain datasets. Consequently, it is unsurprising that no other machine learning approach was able to surpass SCIP in these cases.
Labassi
Some works have sought to provide a full tree representation. Scavuzzo et al. (0022) address the variable selection problem by proposing tree Markov Decision Processes that offers a more suitable framework for learning to branch. On the other hand, Mattick & Mutschler (2023) focus on
node selection, addressing the complexity of batching variable and constraint structures. Instead of creating & vertices for & variables, they represent variable values as distribution with 10 buckets. This method allows for scaling to much larger instances than typically possible, although it sacrifices some detail in representation, thus leaving room for optimization and fine-tuning.
PRELIMINARIES
3.1 MIXED INTEGER LINEAR PROGRAMMING
A general MILP problem is defined by a set of decision variables, where a subset or all variables required be integers. The objective is to maximize linear function under series of linear constraints, as formulated below:
max C x, s.t. 2, ZzjZ,
(1)
For simplicity, we assume that the objective of our MILP problems to seek the maximum value.
An MILP problem can be effectively represented as a weighted bipartite graph G = (VUC, E) (Nair al. 2020 Gasse al. 2019). Each vertex in V corresponds to a variable of the MILP, and each vertex in C represents a constraint. An edge (V:, connects a variable vertex with a constraint vertex Cj if the variable is involved in the constraint. The edge set E E R/xmxe represents the edge features, where and m denote the number of variables and constraints, respectively, and indicates the dimension of the edge attributes.
3.2 BRANCH AND BOUND
The branch and bound (Land & Doig, 1960) algorithm can be described as follows. At every node, the linear program (LP) relaxation is solved, where all variables are treated as continuous. If the IPP relaxation solution IN, of the selected node N, violates the original integrality constraints, the problem "branches" into two sub-MILPs (child nodes) by adding constraints that force fractional variable to round up or down. Specifically, the leaf node added with constraints x; S [( )s] and x; > [I ): respectively, where z; denotes the i-th variable, (æN,,) ); denotes the i-th variable of the LP relaxation solution INN.. If the solution IN, is integer (and feasible for the original MILP as per Equation []. and its objective value surpasses the current best integer feasible solution, it is designated as the new global lower bound. If the objective value fx (i.c., the node upper bound) is lower than the global lower bound, if the IP problem is infeasible, the node is pruned.
3

---

Published as a conference paper at ICLR 2025
eepiored rode
Constraint ver Sicee
ureeppored
verlices
vertices
45 Cs
rOOG node
A6 CB 1w
max it 6t. Sp So
s 0,y0
Example of tripartite graph representation. The root node (red) conceptualized as bipartite graph, consisting of variable and constraint vertices, while the leaf nodes (grey) embody sets of added branching constraints. The features of the edges, which connect the variable vertices to the node constraint vertices, delineate the constraint space of the leaf nodes.
Figure 1:
3.3 INFORMATION THEORY
In information theory Reza 1994), mutual information / ((XY)) is the amount of uncertainty in X due to the knowledge of Y. Mathematically, mutual information is defined
(I; Epee, v) log( p(r, v)
(2)
p(z)p(y))
where p(x, y) is the joint probability distribution function of X and Y, and p(x) and p(y) are the marginal probability distribution functions for X and Y. We can also say
((; = ((X) (X
(3)
where (XX) is the marginal entropy, H(J the conditional entropy. ((X) represents the measure of uncertainty about random variable, then (xX measures what Y does not say about X. This is the amount of uncertainty in after knowing and this substantiates the intuitive meaning of mutual information as the amount of information that knowing either variable provides about the other.
4 TRIPARTITE GRAPH REPRESENTATION OF BRANCH AND BOUND TREE
While sufficient representation of every node within wranch-and-bound tree T would theoretically capture the entire scope tree information, such an approach not feasible for large-scale problems due to the exponential increase in node count. For instance, the Anonymous dataset (Gasse et al. 2022], rooted in a large-scale industrial context, necessitates that SCIP handle upwards of 50,000 nodes. We define the complete tree feature vector, F = ① NeT JN. by aggregating features JN T for each node N. This raises a critical question: Which node features within are essential and should be selectively represented effectively model the tree? Addressing this, introduce tripartite graph structure for tree representation in Section 4.1
In order judge whether tree representation effectively can capture all relevant node features necessary for node quality assessment, we first need to define what a sufficient tree representation is. Let Φ(-) denote feature extraction function, which depends on the specific methods employed for tree representation. The feature vector, o(F), is derived from the tree complete feature F. Shannon's 's information theory provides suitable formalism for quantifying the above concepts. The information about the quality vector Q contained in the feature vector of ()) is then T(Q; ø( F)). As a consequence of the data processing inequality, (Q; ((F)) S ((;:)) A feature vector (FF) is defined to be sufficient if the inequality above is equality.
Definition 4.1 (Definitoon of Sufficient Tree Representation). tree feature representation ((F) considered sufficient if:
I(Q;)(F) = I(;;F)
In Section 4.2 we theoretically demonstrate that the tree information captured within this graph is sufficient for node selection.
4.1 TREE REPRESENTATION
In this section, we introduce a tripartite graph for tree representation. An advantage of our rep-
resentation is that it is theoretically proved be sufficient in Section 4.2 This theoretical suffi-
4

---

Published as a conference paper at ICLR 2025
ciency ensures that our representation comprehensively capture the necessary features across the branch-and-bouu tree for effective node quality assessment. Additionally, to enhance practical applicability in machine learning, tailor the representation to facilitate feature learning. In- stead of directly representing each node with its variables and constraints, which would redundantly present at the root node, we focus on depicting the unique branch constraints that distinguish each node, This approach emphasizes the subtle, often overlooked differences among nodes, thereby facilitating machine learning algorithms to more effectively learn and discriminate node features.
We represent the branch-and-bound tree as a weighted tripartite graph G = (V U LN, E U ET.N). The vertex set V C' U LN is divided into three subsets: the variable vertex set V with [V] 1. the constraint vertex set C' with |C| = m and the leaf node vertex set LN with LN n. The vertex sets V. C. and LN are mutually exclusive: V VnC V n LN = C LN = 0. We denote the variable vertices as V = (vi, 22, ................................ m1 constraint vertices as C {ci, c2,.... ... Cm and leaf node vertices LN {In,, Ifn.......... .......... nodes for selection strategies within the wranch-and-boud and-bound algorithm divides it into two new leaf nodes, adding constraints of the form {a, S =] or {z; 2 z), where H; is the variable chosen for branching and E Z. The constraint edges E connect variable vertices V to constraint vertices and the branching edges E connect variable vertices V to leaf node vertices LN, indicating branching decisions. The edges are denoted as E 11.2....m., E L.2........ We denote the collection of all such weighted tripartite graphs G G= (VUCULN, E UEEN) with [ |C| m and |NN| = n as Gr.m.n-
Im,.)....I... The leaf node vertices represent candidate leaf tree. After node is selected, the branch-
E = ()) and F. = (cg, Inx), with EE <1; F = 62, for i E (1,2....,
Each vertex in the tripartite graph is associated with feature vector: vertices in V (variables), C' (constraints), and LN (leaf nodes) hold features hy E H², hf H., and h E H respectively. We define the feature spaces for the sets of all variable vertices, constraint vertices, and leaf node vertices as H. == (H H == (HC)m, and H == (HLNY) yr. Edges in the graph are imbued with specific attributes that detail the interactions between vertices. For constraint edges that connect constraint vertices c, to variable vertices uj each edge feature f E & is one-dimensional and directly represents the coefficient A.; of variable æj in constraint c₁. Branching edges connect variable vertices V/ to leaf node vertices Ing, and these edges carry two-dimensional features that specify the branching conditions for the variable Øj at the leaf node. Each branching edge feature encapsulates z 2 and zj S b, represented as ff, (a, FB, We detine FC := (FC) and F = yez, The exact features of the graph are described in Appendix C
We extract an MILP solving search tree's ' features via a tripartite graph de (F (V (VUCULN, E EB)e Gmm.n x H. H H x F x FB. where F denotes the aggregate of node features. In Figure [ we illustrate the process of converting a branch-and- bound tree from an MILP instance into a tripartite graph. The conversion begins with the root node, where variables and constraints are represented as "variable vertices" and "constraint vertices", respectively. As the branching process progresses, each step adds new constraints the leaf nodes, encapsulated as "leaf node vertices" in the graph. These additional constraints differentiate each leaf node's MILP problem from the root node's problem. Edges connect these Icaf node vertices to variable vertices, forming a path that represents the sequence of branching decisions made from the root node to each leaf node. For example, in Figure the candidate leaf node in the lower left undergoes two branching steps, adding constraints y < 1 and x < 1, represented by edges e and ea, respectively.
4.2 THEORETICAL PROOF OF SUFFICIENCY
In this section, we prove our main theorems and present a sketch of our proof lines. The full proof lines are presented in the Appendix A We first present with the following theorem that the tripartite graph is sufficient to represent an MILP search tree.
Theorem 4.1. Given the node N with features JN, the tripartite graph representation (F(F) sat- isfies: I(: (F)) I(Q; F), where F = Dir JN, and Q denotes the quality vector.
This theorem asserts that the information uncertainty in Q. when knowing the tripartite graph repre- sentation & (F), is equivalent to that when knowing the features of all nodes in the tree F.
Then, we analyze the relationship between the features of child nodes and their parent node:
5

---

Published as a conference paper at ICLR 2025
Tree Representation(54)
TRGNN Model ($5)
AvgPool
state
Layer Norm Linear
Graph Conv x3
Linear
AvgPool
Sigmoid
tripartite graph
AvgPool
nodes
action
heuristic algorithm
B&B tree
candidate nodes
first
Q-value vector
Figure 2: Illustration our proposed RL framework for learning node selection policies. In this framework, the search tree is represented as tripartite graph (see Section 4 serving as the environ- ment, and the TRGNN model as the agent(see Section 5). We first apply the heuristic algorithm "BestEstimate" to pre-select n candidate nodes and incorporate their estimate values into the node features. Subsequently, the TRGNN model processes these features and outputs a Q-value vector, from which the nodes with the highest Q-values are selected as the final choices.
Theorem 4.2. Given a node Ng and its two child nodes N₁ and Nr, holds that I(:; @ @JN, t JN,) T(Q @ JN.), where Ju denotes the extracted feature of the node N.
This theorem illustrates that the information provided by the features of the parent node can be completely represented by the features of its child nodes. The proof proceeds as follows: We start with the obvious inequality: JN; @ JN, @ JN.) ing to the data processing inequality. To establish the reverse inequality, we analyze the node features, encompassing both MILP characteristics, denoted by Jm. including the variables, con- straints and objective function, and the global attributes within the tree, denoted by Jg. Thus, we define: JN = (Jm)N + (Jg)N. We demonstrate that functions fm and fg exist such that (Jm)N, (mJmmm) + (Jm)N-) and (Jg)N, = fo((Jg)N @ (Jy)N.). This relationship estab- lishes a Markov chain: Q > JN, + JN, + JN, t JN, @ JN., allowing the use of the data processing inequality confirm T(Q; JN, JN, @ JN.) T(Q; JN, @ J..).
IN: @ JN,) accord-
By invoking Theorem 4.2 recursively, we illustrate that the features of all leaf nodes, denoted by L, encapsulate the necessary information represent the whole tree, thereby establishing that T(Q: L) = I(Q; F). This finding is pivotal for proving Theorem 4.1
In proving Theorem 4.1 is essential validate that the information flow Q dc(F) L holds. The tripartite graph representation (FF)) includes the root node's ' MILP features (Jm N, and each leaf node's branching constraints By and global features (J,) N. ensures that from (Jm N and By, the MILP features J, of the leaf node N can be deduced. Employing the data processing inequality again, we establish the sufficiency of de (F) representation, proving Theorem 4.1
5 LEARNING NODE SELECTION VIA TRIPARTITE GRAPH
Building upon the tripartite graph framework detailed in Section 4 for extracting observable features from the branch-and-bound tree (PI), this section delves into (P2): assessing node quality and selecting node based on the tripartite graph representation.
The challenges node selection are twofold. Firstly, the branch-and-bound process involves se- quential decision-making where each choice impacts subsequent decisions. This creates scenario of delayed rewards, where the consequences of early decisions may not become apparent until later stages. Secondly, there is distinct lack of comprehensive metrics for evaluating node quality.
To address these issues, we frame the node selection problem within a Markov Decision Process (MDP) framework and leverage Reinforcement Learning (RL) to learn node selection policies, as detailed Section Following this, we introduce three node quality metrics that assess the impact of nodes in the solving process, further discussed in Section 5.2

---

Published as a conference paper at ICLR 2025
5.1 REINFORCEMENT LEARNING FORMULATION
We formulate an MILP solver as the environment and the RL model as the agent. We consider an MDP defined by the tuple (S, A, r, T). Specifically, we specify the state space S, the action space A, the reward function r: S x A + R, the transition function т, and the terminal state in the following. (1) The state space S. As delineated in Section[4] the core information for node selection is represented by a tripartite graph. (2) The action space A. The action space is intended to include all nodes that are potentially selectable. However, the dynamic nature of the selection process means the number of selectable nodes is subject to change due to the addition of newly expanded nodes and the removal of pruned nodes. To address this variability, we employ the heuristic node selection algorithm called Estimate in modern solvers to pre-select nodes, choosing the top nodes, where n is a predetermined value, to form a set of node candidates. If the initial set of candidates is less than n, placeholders are used to fill the remaining slots, ensuring consistent set size. We define the action space as this set of node candidates with a size of n. (3) The reward function r. The reward function, as discussed in Section 5.2 encompasses the gap update reward, the optimal solution path reward, and the path switching penalty. (4) The transition function n. The transition function maps the current state s and the action a the next state s', representing the ensuing search tree post the expansion of node a. (5) The terminal state. The process reaches a terminal state when the gap attains zero or no remaining candidate nodes are in the set. Within this framework, the trajectory probability
(So...., .T) depends on the node selection policy π and the other solver components, formulated as (T) = p(so)
(idea((alss (a) (p55+11/),,
TRGNN Model. Figure 2 delineates the architecture of our proposed model. The features of the variable, constraint, and leaf node vertices on the tripartite graph undergo initial transformation via a 32-dimensional embedding layer. This layer is pivotal for normalizing and refining the input features before they traverse through three subsequent graph convolutional layers, each with dimen- sions 8, 4, and 4, and each utilizing a ReLU activation function to capture complex, non-linear relationships. Post convolution, the refined representations of the variable, constraint, and node constraint vectors are separately averaged, reducing dimensionality and mitigating overfitting risks. These averaged representations are then amalgamated with the global node features, creating com- prehensive feature vector encapsulating both localized and global information. This amalgamated feature vector is then processed through a linear layer and a sigmoid activation layer, culminating in a Q-value vector of predetermined dimension n. This vector quantitatively represents the value of each node in the pre-selected candidate node set, serving as a decisive metric for action selection. The action is determined by selecting the node corresponding the maximum Q-value, directing the model's focus towards the most promising regions of the search space.
A significant advantage of our model is higher learning efficiency for different node features. Ex- periments demonstrate that TRGNN requires far fewer training examples compared to conventional imitation learning models (Labassi et al.) 2022), thus conserving computational resources. For in- stance, with the GISP datasets, our model needs only 250 instances for training, whereas traditional imitation learning methods may require up 1000 instances.
5.2
REWARD FUNCTION
The reward function R for the selected node N is defined as:
(4) where Rg represents the updates to the global gap, R. represents the potential of node to lead to an optimal solution, and R. signifies the normalized reward for path-switching steps. Due to space constraints, the normalizing methods and parameters are detailed in the Appendix.
R(N) = w Rg (N) + w2 Ro(N) - wis R,)
In branch-and- hound algorithms, node selection is crucial for optimizing the solving process. The overarching goal is to efficiently converge to the optimal solution by narrowing the primal and dual bounds. Each node is critically evaluated for its potential to: (1) update the global lower bound, finding an improved feasible solution, (2) influence the global upper bound, reducing the gap between the current best known solution and the optimal solution, or (3) generate promising descendant nodes that might yield feasible solutions.
The updates to the global lower and upper bounds are quantitatively assessed by changes in the global gap. We denote the optimal solution reward R., methodology endorsed by prior
7

---

Published as a conference paper at ICLR 2025
search (He et al. 2014 Yilmaz& & Yorke-Smith 2020
Labassi al. 2022).
[N(N) {
if LBx x= S UBN,
(5)
otherwise.
where LBx and U B denotes the local lower and upper bound of node N, x denotes the optimal solution. Each node defines unique segment of the search space; If the optimal solution resides within the current node's ss domain, the reward R., 1. If the optimal solution is not within the domain of the current node, the reward for this component is zero. This method enables the model to learn from node features to discern which nodes are likely to lead to potentially promising solutions.
often-overlooked aspect of node selection is the time taken to transition from the last selected node to the newly chosen one. This transition time can signifi- cantly impact overall performance. For instance, in the MaxSAT dataset, where n ranges from 70 to 80, the path switching phase consumes, on average, 5.2% of the total solving process, solvers like SCIP (Bestuzheva et al., (202I) navi-
However,
time. In the branch-and-bae gate the path from the last selected node to the newly chosen one, known as path switching. Figure 3 illlustrates how each node traces back through the tree to find a common ancestor. Although this process might seem straightfor- ward, it introduces significant computational overhead. We employ the "Eventhdlr" from PySCIPOpt (Maher et al.] (2116). We utilize the "PY_SCIP SCII.EVENTTYPPE SOLVED" and "NODEFOCUSED" to track the time from when one node is completely solved ("NODESOLVED") shifts its focus to another node ("NODEFO- CUSED"). Since the path switch time posi- tively correlated with the number of path switch steps, we incorporate the steps required for path switch as a component of the reward func- tion in our reinforcement learning model. We calculate the number of steps between nodes by adding the number of steps each node takes to reach their nearest common ancestor.
Statts
Stade
Fork Node
Selected Node
states "NODE-
Selected Node
when the solver
(a)
(b)
Figure 3: Path switching process. Figure (a) de- picts the current state s; with node N, selected and figure (b) shows the subsequent state 5 with node No+1 chosen.
EXPERIMENTS
Table 2: Policy evaluation on the synthetic and real-world datasets, The best performance is marked in bold. We report the 1-shifted geometric mean (standard deviation) of the Time.
Methods
FCMENF
MaxSAT
GISP
Time(s)
wins
Im( %)
Time(s)
wins
Imt %
Time(s)
wins
Imi %
SCIP
21.15 2.42
20/100
0.00
8.22
1.90
23/100
0.00
3.88 1.32
27/100
0.00
SVM
22.17 + 2.44
14/100
-.82
8.15 1.76
8/100
+0.85
4.98 1.78
3/100
-28.35
RankNet
22.39 + 2,24
14/100
-5.86
8.29 + 1.83
9/100
-0.85
5.03 + 1.81
2/100
-29.64
GNN
17/100
4.19 11.79
13/100
TRGNN (Ours)
14.50 2.21
34/100
+31.44
7.60 + 1.86
43/100
+7.54
3.34 1.37
55/100
+13.92
Methods
MIK
CORLAT
Anonymous
Time(s)
wins
Im( %5)
Time(s)
wins
Innt %
Time(s)
wins
Imi %
SCIP
29.45 = 1.76
0/18
0.00
6.81 + 5.00
6150
0.00
215.28
37.90
0/20
0.00
SVM
39.60 1.79
0/18
-34.46
4.78 a 4.42
4/50
+28.81
1966.14 a: 25.06
0/20
-8.13
RankNet
48.00 + 1.95
0/18
-6.99
4.52 3.81
5/50
+33.63
1840.65 + 48.86
0/20
.7.55
GNN
40.08 1.69
2/18
-36.99
4.71 3.90
8/50
+30.84
271.40
15.38
0/20
-26.07
TRGNN (Ours)
4.10
19/50
105.68 20.87
+50.91
Our experiments have three main parts: Experiment (1) Evaluate our approach three classical MILP problems and three challenging MILP problem benchmarks from diverse application areas. Experiment (2) Perform carefully designed ablation studies provide further insight into TRGNN.
8

---

Published as a conference paper at ICLR 2025
Experiment (3) Test whether TRGNN can generalize instances significantlly larger than those seen during training. The codes are modified from Labassi et al. (2022).
6.1 SETUP
Benchmarks. We evaluate our approach on six NP-hard MILP problem benchmarks, which consist of three classical synthetic MILP problems and three real-world MILP problems from diverse application areas. (1) Syntheric datasets comprise three widely used synthetic MILP
problem benchmarks: Fixed Charge Multicommodity Network Flow (FCMCNF) (Hewitt et al.) 2010). Maximum Satisfiability (MAXSAT) (Ansótegui & Gabàs (017)) and Generalized Inde- pendent Set (GISP) (Colombi et al. 2017). We artificially generate instances following [Béjar (2) Real-world datasets comprise MIK Atammtrk] 2003), CORLAT (Gomes et al. 2008). and the Anonymous problem, inspired
et al. (2009); Chmiela et al. (2021); Labassi et al.] (2022).
by large-scale industrial application (Gasse al. 2022). Details of datasets are provided in the
Appendix D.I] Throughout all experiments, we use SCIP 8.0.4 (Bestuzheva et al. 2021) as the
backend solver, which the state-of-the art open source solver, and widely used research of
machine learning for combinatorial optimization (Chmiela et al.) [202]] Gasse et al.] 2019 Turnr jtt al. 2022 Wang al. 2023). We keep all the other SCIP parameters to default and emphasize that all of the SCIP solver's is advanced features, such presolve and heuristics, are open.
Baselines. We compare against the sfate-of-the-art best estimate node selection rule (Bénichou et al., 1971, Forrest et al.] 1974). This is the default method in SCIP (Bestuzheva et al. [021)) In addition, we compare against three machine learning approaches: the Support Vector Machine (SVM) approach (He et al., 2014), the RankNet feedforward neural network approach (Song et al., 2018). and the approach based on Graph Neural Networks (GNN) (Labassi et al., 2022).
Training. We generate extensive synthetic datasets, consisting of 10,000 training samples and 1,000 test samples. From these, we randomly select 1,000 samples for the SVM, RankNet, and GNN models training and 100 samples for testing within each problem. Additionally, larger-scale datasets, randomly selecting 50 samples from each to evaluate the transfer capability of our method. For the real-world dataset, each problem is split into training and test sets with 80% and 20% of the instances. Specifically, we train model with 1,000 samples for Corlat, 72 samples for MIK and 65 samples for Anonymous dataset. The model implemented in PyTorch (Paszke al.] 2019) and optimized using Adam (Kingma & Ba 2014) with training batch size of 16. The training process is conducted on a single machine that contains eight GPU devices(NVIDIA GeForce RTX 4090) and two AMD EPYC 7763 CPUs.
generate 1, 1,000
We observe that our model performs remarkably well even when trained with fewer samples, achiev- ing results comparable to those obtained with larger datasets. This demonstrates its efficiency and effectiveness utilizing limited data. The ability to maintain such performance with a reduced dataset size is particularly valuable, given the significant time and computational resources required to collect training samples by solving multiple MILP instances. For instance, collecting 90 sam- ples for the Anonymous problem alone took over 13.89 hours. In the Appendix [D.5] provide comparison between our TRGNN model and a GNN baseline trained with the same limited dataset, referred to as ENN_light.
Evaluation Metrics. We employ two widely recognized evaluation metrics: (1) Time: running times in seconds (lower better) and (2) Wins: number of times each node selection strategy re- sulted in the fastest solving time, over total number of solved instances. We limit the solution time for all problems to a maximum of 3600 seconds. Any time exceeding this limit recorded as 3600 seconds. We assess node selection methods in terms of the 1-shifted geometric mean over the in- stances, accompanied by the geometric standard deviation. Furthermore, evaluate different node selection methods compared to the default SCIP, we propose an (3) Improvement metric. Specifi- cally, we define the metric by Im T[SCIP)-2(M) where T(SCIP) represents the solving time T(SCTP) of SCIP, and T(M) represents the solving time of the compared method. Due to the space limits, report the size of the branch-and -nd-d tree (Nodes) in the Appendix D.4
6.2 COMPARATIVE EXPERIMENT
For each problem, machine learning models are trained on instances of the same size as the test instances. The results in Table suggest TRGNN significantly outperforms all baseline methods.
9

---

Published as a conference paper at ICLR 2025
Importantly, it the only known learning- caaning-based node selection method to consistently outperform the default SCIP in terms of solving time across all six datasets. Compared to SCIP, TRGNN demon- strates notable efficiency improvements across all tested problems, being 3 1.44% faster in FCMCNF, 7.54% in MaxSAT, 13.92% in GISP, 59.42% in MIK, 37.89% in CORLAT, 50.91 % in Anonymous.
6.3 ABLATION STUDY
We present an ablation study conducted to evaluate the contribution of different metrics in Sec. We report the performance of TRGNN, TRGNN-1 and TRGNN-2 with different reward strategies Table on FCMCNF, GISP, MIK, and Anonymous. TRGNN-1 utilizes our RI. framework with a reward function based on the optimal solution, as established in prior research (Labassi al. 2022
TRGNN-2 incorporates gap change into the node metrics, while TRGNN, our full model, additionally accounts for path switching over- head. The results in Table 3 reveal that both TRGNN-1 and TRGNN-2 outperform SCIP on GISP, MIK, and Anonymous datasets, high- lighting the benefits of integrating the rein- forcement learning model with our tripartite graph representation. Furthermore, TRGNN significantly surpasses TRGNN-1, TRGNN-2, and other baselines across all four datasets. The results demonstrate that both of the gap update and path switching overhead important for efficient
Table 3: Comparison between TRGNN, TRGNN with two metries (TRGNN-2) and TRGNN with one metric (TRGNN-1).
Methods
FCMCNF
GISP
MIK
Anonymaux
21,15
TRGNN-1 TRGNN-2
23.28
3.48
13.27 s
183.62
22.97
3.36
12,08
124.05
TRGNN((urs)
14.50
3.34
11.95
105.68
exploration in complex tasks.
6.4 GENERALIZATION
We evaluate the ability of TRGNN to generalize across larger sizes of MILPs. We evaluate the generalization ability on FCMCNF, MaxSAT and GISP datasets, as we can artificially generate the larger transfer instances.
Table 4: The generalization ability of TRGNN. The best performance is marked in bold. We report the I-shifted geometric mean (standard deviation) the Time.
Methods
FCMCNF
MaxSAT
GISP
Timets)
wins
Imi %
Timets)
wins
Im
Time(s)
wins
Imi %)
SCIP
1474.60 4.19
3/50
76.12 1.83
4/50
427.29 1.65
0/50
0.00
1857.29 +
84.78 2.66
2.39
RankNet
1560.22 = 4.18
1/50
-5.80
101.45 + 2.15
0/50
-33.27
701.62 + 2.02
0/50
-64.20
GNN
1503.83 +:: 3.90
11/50
-1.98
69.44 1.57
19/50
+8.78
534.72 + 1.90
0/50
-25.14
TRGNN (Ours)
1243.39 + 3.64
29/50
+15.68
48.20 1.55
26/50
+36.67
339.66 + 1.85 50/50
+20.51
The results in Table indicate that TRGNN significantly surpasses the baselines in terms of both solving time and number of wins, demonstrating superior generalization ability. Notably, TRGNN demonstrates an even more pronounced improvement in solving time on larger datasets compared smaller ones, underscoring the importance of effective node selection strategies, par- ticularly for large-scale MILP instances.
7 CONCLUSIONS
We addressed two pivotal problems in node selection including the sufficient tree representation and assessment of the node quality with delayed rewards. We introduce an innovative tripartite graph representation for the branch-and-bound search tree and provide theoretical evidence. Subse- quently, we introduce more comprehensive metrics for node selection and develop a novel TRGNN model. leveraging reinforeement learning to acquire node selection policies. Experiments show that TRGNN significantly outperforms human-desss -emanndesigned and learning- based baselines in terms of solving efficiency three synthetic MIL.P problems and three real-world MIL.P problems.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The research is partially supported by National Key R&D Program of China under Grant No. 202 IZD01 10400, Innovation Program for Quantum Science and Technology 20212D0302900 and China National Natural Science Foundation with No. 62132018, 62231015, "Pioneer" and "Leading Goose" R&D Program of Zhejiang, 2023C01029, and 2023C01143.
REFERENCES
Tobias Achterberg. Constraint integer programminng. PhD thesis, 2007.
Carlos Ansótegui and Joel Gabàs. Wpm3: an (in) complete algorithm for weighted partial maxsat. Artificial Intelligence, 250:37-57, 2017.
Alper Atamtürk. On the facets of the mixed-integer knapsack polyhedron. Mathematical Program- ming, 98(1 131--):455-175 2003.
Ramón Béjar, Alba Cabiscol, Felip Manyå, and Jordi Planes. Generating hard instances for maxsat. In 2009 39th International Symposium on Multiple-Vaile Valued Logic, pp. 191-195. IEEE, 2009.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Michel Bénichou, Jean-Michel Gauthier, Paul Girodet, Gerard Hentges, Gerard Ribière, and Olivier Vincent. Experiments in mixed-integer linear programming. Mathematical Programming, 1:
76-94, 1971.
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 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 Well- ner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. Technical report, Op- timization Online, December 2021. URL http://wwwwoppiiizziioooonnnnnne oww.ne.or./DDn.B...... DBB HTML/2021/ 12/8728.html
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear pro- grams by graph neural networks. arXiv preprint arXiv:2209. /2288, 2022.
Antonia Chmiela, Elias Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 14:24235-24244 2021.
Marco Colombi, Renata Mansini, and Martin Savelsbergh. The generalized independent set prob- lem: Polyhedral analysis and solution approaches. European Journal of Operational Research, 260(1):41-555 2017.
Jian Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang. Yinghui Xu, and Le Song. Ac- celerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference artificial intelligence, volume 34, pp. 1452-1459, 2020.
Christodoulos Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139:131-162, 2005.
JJH Forrest, JPH Hirst, and JOHN A Tomlin. Practical solution of large mixed integer programming problems with umpire. Management Science, 20(5):736-773, 1974.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
11

---

Published as a conference paper at ICLR 2025
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, et al. The machine learning for combinatorial optimization competition (ml4co)) Results and insights. In NewrlPS 2021 Competitions and Demonstrations Track, pp. 220-231. PMLR, 2022.
Carla P Gomes, Willem-Jan Van Hoeve, and Ashish Sabharwal. Connections in networks: A hybrid approach. In Integration of Al and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 5th International Conference, CPAIOR 2008 Paris, France, May 20-23, 2008 Proceedings 5, pp. 303-307. Springer, 2008
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https//www.gurobii com
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Mike Hewitt, George L Nemhauser, and Martin WP Savelsbergh. Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS Journal on Com- puling, 22(2):314-325, 2010.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guid- ing combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 19219-10227 2022.
Kiavash Kianfar. Branch-and-bound algorithms. Wiley Encyclopedia of Operations Research and Management Science, 2010.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. arXiv preprint arXiv:2210.169)) 2022.
AH Land and AG Doig. An automatic method of solving discrete programming problems. Econo- metrica, 28(3):497-520) 1960.
Jeff T Linderoth and Martin WP Savelsbergh. computational study of search strategies for mixed integer programming. INFORMS Journal on Computing, 11(2):133-187, 1999.
Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In Mathematical Software ICMS 2016, pp. 301-307. Springer International Publishing, 2016. doi: 10.
Alexander Mattick and Christopher Mutschler. Reinforcement learning for node selection in branch- and-hound. arXiv preprint arXiv:23 20203..
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012..1339, 2020.
Vangelis Th Paschos. Applications of combinatorial optimization, volume 3. John Wiley & Sons, 2014.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference machine learning, pp. 17584-17600 PMLR, 2022.
12

---

Published as a conference paper at ICLR 2025
Hongbo Ren and Weijun Gao. A milp model for integrated plan and evaluation of distributed energy systems. Applied energy, 1713):1001-011,, 2010.
Fazlollah M Reza. An introduction to information theory. Courier Corporation, 1994.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 661-6666 JMLR Workshop and Conference Proceedings, 2010.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the fourteenth international con- ference artificial intelligence and statistics, pp. 627-635. JMLR Workshop and Conference Proceedings, 2011.
Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree mdps. Advances in neural information processing systems, 35:18514-18526 2022.
Yunzhuang Shen, Yuan Sun, Andrew Eberhard, and Xiaodong Li. Learning primal heuristics for mixed integer programs. 2021 international joint conference on neural networks (ijenn), pp- 1-8. IEEE, 2021.
Jialin Song, Ravi Lanka, Albert Zhao, Aadyot Bhatnagar, Yisong Yue, and Masahiro Ono. Learning to search via retrospective imitation. arXiv preprint arXiv: 10X.v01804.000866, 2018.
Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed- integer linear programming. arXiv preprint arXiv:2202.10965 2022.
Zhihai Wang. Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng. Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. arXiv preprint arXiv:2302.00024, 2023.
Kaan Yilmaz and Neil Yorke-Smith. Learning efficient search approximation in mixed integer branch and bound. arXiv preprint arXiv:2007.03948, 2020.
Cong Zhang, Yaoxin Wu. Yining Ma. Wen Song, Zhang Le. Zhiguang Cao, and Jie Zhang. A review on learning to solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufacturing 5(1):e12072, 2023.
13

---

Published as a conference paper at ICLR 2025
A THEORETICAL ANALYSIS
We enumerate our theoretical findings and provide detailed proof' to substantiate them.
First, we list the definition of a Markov chain and the data processing inequality (Reza 1994) to aid the proof of the subsequent theorem.
Definition A.1. Consider three random variables X, Y, and Z. They form Markov chain X Z if it holds that:
p(z,y. p(z)p((llz)p(et)
where p(z, y, 2) is the joint probability density function of X, Y, and Z. Theorem A.1 (Data processing inequality). If X + Y + Z forms Markov chain, then: I(x 2 2):
Theorem A.2 (Restatement of Theorem 4.2 Given a node Np and its two child nodes N₁ and N,, it holds that [(; JN, @ JN, @ JN.) = TQQ JN, @ JN.). where JN denotes the extracted feature of the node N.
Proof of Theorem 4.2 First, note that JN, + JN, JN, e JN, @ JN., hence JN, + JN. JNp @ JN, ① JN. is a Markov chain. According to the data processing inequality (Theorem A.1 we have:
JN; @ JN, @ JN.) JN @ Jx.).
To complete the proof, it is necessary show that:
I(Q; 1 JN, 2 JN.) I(Q; JN.).
Assuming JN, @ JN. + JN then Q + JN @ JN, @JN, + JN, @J,, also forms Markov chain. Thus, by applying the data processing inequality once again, we establish the desired equality.
To prove the Markov chain, we analyze the relationship between the parent node N, and the child nodes N2 and N,. The node features encompass both the MIIP characteristics, denoted by Jms including the variables, constraints and its objective function, and the global attributes within the tree, denoted by Jg. Thus, we have: JN= = -Jm)N N ① (Jz)N-
In order to prove JN. ① JN. + JNp, we only need to prove (Jm)N, ① (Jm)N. - (Jm),, N2. and (Jg),, @ (J,),, + (Jg)N,
We consider the MILP characteristies, which is only related to their problem structures. The vari- ables and objective function in the branch-and-boume tree the same as the root node (Jm)No- We denote the common variables and objective function feature CF, the variable set V {z, i E {0, .()., with [V] = L, and the constraint set of the node N as SN. Thus, we have (Jm. SN CF.
Because the constraints of both the child nodes Nj and child nodes N, is the constraint of the parent node Np added by the branching constraints. Denote Np 's LP relax solution NN,, and let = [(,,,) k.J, where (IN,)s denotes the value of variable x; in the LP relax solution NN,""
The branching constraints denoted x; < for N, and a; selected branch variable on the parent node Np-
for N,, where 2; E V is the
Consequently, the sets of constraints for N; and N, be represented as:
S Ni SN U {z, S 2},
and
SN, = SN, U 2 11
which leads to significant overlap: SN, n SSN. = SN This implies that the combined MILP characteristics Jm for N₁ and N, encapsulate the MILP characteristics of Np:
(Jm) O (Jm)N, (SN, @ CF) (Sx, CF)
=
(5N, n (Sx)) @ CF
(SN, CF)
(Jm)Nz
14

---

Published as a conference paper at ICLR 2025
Thus, we establish that function relationship fm exists such that: (Jm)N, fm((Jm)N + NJm)
Considering the mutual information equations:
JN, @ (JN, @ Jx.)) - I(Q; ((Jm)N, @ (J,)N,) @ (Jv, @ JN.))
I [m) @ ( @ (Jv, @ JN.))
E I(Q; ((Jm) @ (Jm)x,) (J,),, @ (JN, @ JN.)) I(: ((Jm),, 1 (Jm)N.. @ (Jg)N, ((Jm),, (Jg)N.)
((Jm)N, + (Jg)N.))
[(: (J,)N, @ (Jv, @ JN.)).
Next, we turn our attention the global attributes Jg. which contain the solving process character- istics of each node and the positional characteristics of each node to represent the whole tree.
The solving process characteristics originates from the an improved feasible integer solution or the IP relaxation solution, denoted as the update of the local upper and lower bounds. We denote the local upper and lower bounds on the node N U By and L. We denote the node N's positional characteristics pN. which can represent the position of the node N in the tree. Thus, have (J))N = (LBN, (B) + PN-
Given that the LP relaxation solutions of the child nodes, Nr and Ne. also solutions of the node Np. The local upper bound only updates when finding a tighter LP relaxation solution. Thus, established that UBN, I UU, and UB UN,, I U,, According to Lemma A.I it is inferred that the infeasible integer solution of the node Np is also a solution of either Ni or N,. Hence, we deduce that I.BN, I LBB,, and LBN, & I.BN,- This establishes that:
(LB,,, UB,)) S. (LBx,,UBM U (LBx,, UBN.).
Since child nodes are derived from the parent node, positional attributes pN, of the parent node can be deduced by the two child nodes' positional features PN, and pN.- We denote a function Sp such that
PN, fp(PN.PN.).
demonstrating that: (Jg)N, S
Considering the mutual information equations:
[(Q;N,, @ JN, e JN.) S I(Q; (Jg)N, @ (JN, @ (N.)))
= =T(Q; ((LBN,, UBN, e @NN,) + (JN, @ JN.))
S I(Q; (LBB,, ULBN,,
@ (pN...PN.))
() (JN, @ JN.))
< [(BB,
$ (LBN,, UBN,) PN, PN..
@ (JM, @ (NN)))
((Q:((J)) @ (J,)N.) @ (JN, ② JN.))
=I[Q; @ Jx.).
Lemma A.1. Given node Np and two child nodes N₁ and Ny. any infeasible integer solution of node N, is also infeasible solution of either Nt or N,.
Proof of Lemma A. Suppose there exists an infeasible integer solution x of node N, that not an infeasible solution of either child nodes, N, or N2.
Let SN SN and SN, represent the constraint spaces of nodes No. Ni. and N2. respectively. By assumption, SN, but SN, U UN,,
15

---

Published as a conference paper at ICLR 2025
Given that N1 and N2 are child nodes of No, we can express the constraint spaces of N1 and N₂
SN. = SNo n fo Cla; 2 2 1, 2}
and
ON₂ SNo for E Clui 2 2).
Thus, must belong to the set difference SNo \ (Sv, U USN,), which is equivalent to
SNo n E E < 24 < 1,
However, since x an integer solution, it cannot belong to the set {ar E C|2 < 84 <= 1, E Z). leading to contradiction. Therefore, any infeasible integer solution of node No must also be an infeasible solution of cither N1 or N2.
Theorem A.3 (Restatement of Theorem graph representation (F)F) satisfiex: (( = I(Q; F), where F
Given the node N; with features JN the tripartite
① ===
m+ JN.
Proof of Theorem 4.7 The leaf nodes are denoted N jas...., Nj.. The of the leaf nodes' features denoted as L Di= JN,
First, let us prove o()) = I(Q:)) where (F) = (Jm)N, @ O+_ Br @ (J),)())),, where JN denotes the extracted feature of the node N, Bx denotes the set of branching constraints added from the root node to the node N, and (Jg)N denotes the global fea- tures in the tree of the node N, include both the local upper and lower bounds and its positional characteristics.
Thus, we only need to prove Q + (F(F) - L. is a Markov chain.
We have JN,, (Jm),, (J,) and (Jm)N, =SN, CF = (S O i-1 BN OF = (Jm) No
U( BNN,) @ CF). Thus, L = + " JNH = ( U (1 BNN,) + CFF)) + (Jg)N,,'
From dh (F), we can deduce No. BNG and N,,, for 1, 1.., n. Due to (Jm) SN, DCF, where S SN, denotes the set of the root node's constraints, we can known CF from or Then, denote there exists function fi that fi (F)( = L, which shows Q (F - L a Markov chain.
At the same, representation L. Thus, there exists function fz that f2(L) (F.),, which shows T (F) is a Markov chain.
also known (Jg),,, (Jm)No- and BNG,> for all i 1,2,..., n, from the
Next, prove I(Q: IN, =)Q Because I(Q; L) S I(Q; obviously satisfies, only need to prove L(Q;T) 2 I(Q; We prove this step by mathematical induction. When expanding the root node for the first time, the conclusion holds according to Theorem 4.2
Suppose that the conclusion [(Q L) 2 I(Q; holds after the k-th selection of nodes. That is, we have Q + L + F' is a Markov chain. We denote the set of all of the nodes in the tree as Tu. When expanding the leaf nodes for the + 1-th time, we denote the selected leaf node as N We denote set of the other candidate nodes as N". Thus, we have Q + ( NEW Jx) ② JN. - θ NET. JN a Markov chain. We denote the selected node expanded into two child nodes. To simplity, we denote them N., and N.,r. The tree node set turns to be Tk+11
Tk U (N.., Ns.r). According to Theorem 4.2 we have Q - JN., ① JN... JN, @ JN., @ JN..- is a Markov chain. Thus, Q + NEA JN) @ JN.., ① JN.,, ONET, JN JN.,, ① JN.,, is Markov chain.
According to the Data processing inequality (wweoorttyToorem//mmmmmm A.I we can prove I(Q; L): I(Q;F).
16

---

Published as a conference paper at ICLR 2025
B MORE DETAILS OF NODE SELECTION PROCESS
Node selection process. Algorithm details a general procedure for node selection within this MDP formulation. describes the primary operations carried by the node selector in the B&B process. The specific implementation details may vary depending on the chosen node selection strategy, but the fundamental concept remains consistent. Initially, node is chosen based on the branching strategy. After selection, the node is evaluated, which involves updating its bounds and assessing whether it should be pruned. If the node not pruned, the is branched enable further exploration.
Algorithm General Node Selection Procedure
Require: Node list L, parent node bounds, probability Prob of heuristic integer solution calculation
1: for each node P in L do
2: Select node P according to the node selection strategy.
3: Update the lower bound of P. LB(P) pappent where 1pparent is the lower bound of parent node of P.
4:
Solve the LP relaxation of node P. getting the solution Soll and objective function value Objl.
5:
Update the upper bound of P, UB(P) Obj1. Propagate the updated upper bound upward. if Obj1 < (B(P) then
6:
7:
Prune node
8:
else
9:
if Soll an integer solution then Update the lower bound of P. LB(P) Obj1. Propagate the updated lower bounds
10:
upward.
11:
end if
12:
Call the heuristic to calculate an integer solution with probability Prob, resulting in Sol2
and Obj2.
13:
if Obj2 > LB(P) is an integer solution then
Update the lower bound of P. LB(P) Obj2. Propagate the updated lower bounds
upward.
end
16:
Branch at node P and add the children nodes to list L.
end
18: end for
17

---

Published as a conference paper at ICLR 2025
C MORE DETAILS OF TRIPARTITE GRAPH.
Graph representation. Having sufficient information is crucial to infer the optimal node for se- lection. But what qualifies "sufficient" in this context? An ideal problem representation should be capable of incorporating information that affects node selection, which includes the inherent at- tributes the original problem (A, c) and the attributes of the explored space. Actually, such problem has a strong mathematical structure (Chen et al., [022). For instance, if we swap the positions of the i-t variable in [T elements in vectors b, and columns of matrix will be ordered. The reordered features (A, 6, è) actually represent an exactly equivalent MILP problem with the original one (A, b, c). Such property is named as permutation invariance. If we do not explicitly restrict ML models with a permutation invariant structure, the models may overfit to the variable/constrrintt orders of instances in the training set. Motivated by this point, we adopt the graph representation that are permutation invariant naturally in Section list of the features included in tripartite graph representation is given Table
Table 5: Description of the constraint, variable and leaf node vertex features, and edge features in our tripartite state representation.
Category
Feature ub
Description
lb
Lower bound.
Upper bound.
variable vertex
objective.coeff var_type
Objective coefficient.
Type (binary, integer and continuous) as a one-hot encoding.
constraint edge
coef
Constraint coefficient.
rhs
Right-hand side of the constraint.
constraint vertex
Constraint type feature (eq, geq) as one-hot encoding.
cons_type
leaf_lb
Lower bound of the leaf node.
leaf_ub
Upper bound of the leaf node.
leaf node vertex
depth
Depth of the leaf node.
estimate
Estimate value of the leaf node.
branching constraint
bc.lb
Lower bound of the variable.
edge
be ub
Upper bound of the variable.
18

---

Published as a conference paper at ICLR 2025
D MORE DETAILS OF EXPERIMENTS
The details of experiments are provided in this section.
D.I BENCHIARR
Synthetic datasets. We similarly employ three synthetic instance families, just like Labassi et al. (022) in the latest node selection work. The first benchmark is composed of Fixed Charge Multi- commodity Network Flow (FCMCNF) instances (Hewitt al. 2010), generated from the code of 1 x commodities, and also evaluate on larger transfer instances with n = 30 nodes. The second benchmark is composed of MaxSAT (Ansótegui & Gabàs 2017) instances, generated following the scheme of Béjar ct al. (2099) We train and test on instances with a uniformly sampled number of nodes n E S0, 100 and transfer instances with [120, 150]. Our third benchmark is composed of Generalized Independent Set (GISP) instances (Colombi et al. (017), generated from the code of CChiiela et al. 2021). We train and on instances with uniformly sampled number of nodes n E [60, 70] and transfer on instances with n E [120, 150]. All these families require an underlying graph: we use in each case Erdös-Rényi random graphs with the prescribed number of nodes, with edge probability 0.33 for FCMCNF and = 0.66 for MaxSAT and GISP.
Chmiela et (202T). We train and test instances with = 20 and
Table 6: Average value of the size variables and constraints for MILP problems (Train and Test).
Number
GISP
MaxSAT
FCMCNF
MIK
Corlat
Anonymous
Avg. Binary
65.0
1611.70
125.61
79.17
100.0
14747.35
Avg. 625.48
1268.35
Avg. Continuous
0.0
3185.67
18.33
366.0
21865.6
Avg. Cous
1249.78
1542.16
633.36
439.17
486.46
49603.6
Table 7: Average value of the size of variables and constraints for MILP problems (Transfer).
Number
GISP
MaxSAT
FCMCNF
Avg. Binary
134.14
3353.61
287.23
Avg. Int
0.0
0.0
0.0
Avg. Continuous
2690.61
0.0
10754.84
Avg.
5178.52
3218.40
1410.72
Real-world datasets. Following He et al. (2014); Nair et al. (2020), our dataset consists of the following components: MIK (Atamtürk] 2003). a set of MILP problems with knapsack constraints, and CORLAT (Gomes et al. 2008). real dataset used for the construction of wildlife corridor for grizzly bears the Northern Rockies region. In addition to these datasets, we have introduced a more challenging dataset into experiments: the Anonymous problem, sourced from the NeurIPS 2021 ML4CO competition (Gasse et al., 2022). Each problem set split into training and test sets with 80% and 20% of the instances.
D.2 BASELINES
The SVM and RankNet methods utilize a multilayer perceptron; the latter varies for one benchmark where they three hidden layers, while for simplicity, hidden layer of 32 neurons for all benchmarks (MLP). The GNN method uniquely leverages the structure of the graph to guide node selection. The features used in these papers are roughly similar; again, for simplicity, we adopt the fixed-dimensional features of He et al. (2014) for both the SVM and RankNet method.
multilayer perceptron with
D.3 PAPER-PRRAMETER SETTINGS
The hyperparameters primarily consist of those associated with the reward function and the prese- lection size determined by the "BestEstimate" heuristic algorithm. In our evaluation, set
19

---

Published as a conference paper at ICLR 2025
and more detailed analysis of how variations in affect the final node selection results is provided in Section D.7
Reward function parameees.msters. We denote parameter to normalize the path switching steps. The path switching steps are denoted as s, the normalized reward for path switching steps is Rg I. In this function, if the path switching steps less than m, R3 > O; otherwise, the model receives penalty. The value of m depends on the size of the problem. We use m = 15 for the FCMCNE, MaxSAT, GISP, MIK and CORLAT datasets and 50 for the Anonymous dataset. Moreover, we take the weight values W1 W2 W3 3
Additionally, we follow Labassi et al. (2022) limit the number of times the forming-basedd node selector is called. Consistent with the setup in Labassi et al. (2022). the learning- node selec- tion method is only called before the primal bound updated four times. After four updates, we switch to the Breadth- Search method.
D.4 MORE RESULTS OF NODES
Table 8: Policy evaluation on the synthetic and real-world datasets. The best performance is marked bold. We report the 1-shifted geometric mean (standard deviation) of the Nodes and Im_N (in percentage).
Methods
FCMONF
MaxSAT
Nodes
Im
Nodes
Im_N
Nodes
SCIP
105.58 + 5.50
0.00%
128.43 + 2.33
0.00%
100.77 + 3.32
0.00%
SVM
101.28 a 4.62
+3.01%
224.28 a 2.01
74.63%
127.15 = 3.09
26.17%
RankNet
92.48 1: 3.70
+12.40%
204.54 2.18
-59.26%
119.78 = 3.25
-18.86%
GNN
78.65 4.21
+25.50%
194.22 2.31
-51,22%
117.56 3.05
-16.66%
TRGNN (Ours)
230.74 1 4.50
-118.54%
78.31 3.48
+39.02%
101.7
=
-0.30%
Methods
CORLAT
Anony
Nodes
Im.
N
Nodes
SCIP
896.19 a 4.56
0.00%
273.81
35.66
0.00%
51037.30 a 31.49
0.00%
SVM
870.12 + 4.64
+2.90%
160.23 = 26.51
+41.8%
52369.21 297.75
-2.60%
RankNet
937.15
156.60
21.65
+42.80%%
32.55
-5.57%
GNN
757.99 +: 4.32
+15.42%
173.82 #: 22.73
+36.51%
16039.64 +: 39.03
+68.57%
TRGNN (Ours)
953.56
-6.38%
276.36 28.88
-0.93%
19445.26 + 36.45
+61 +61.89%
Table 9: The generalization ability of TRGNN. The best performance is marked in bold. We report the 1-shifted geometric mean (standard deviation) of the Time.
Methods
FCMCNF
MaxSAT
GISP
Nodes
Im_N
Nodes
Im_N
Nodes
Im_N
SCIP
2427.33 6.17
0.00%
390.92 2.66
0.00%
31552. 14 1.99
0.00%
SVM
3036.70 5.66
10%
582.88 88
.49. 49.10%
23675.73 + 2.26
+24.96%
RankNet
1766.20 5.66
+27.23%
591.18 2.50
-51.23%
31214.54
1.99
+1.07%
GNN
1710.77 + 5.21
+29.52%
503.43 2.07
-28.78%
27900.15
+ 2,01
+11.55%
TRGNN (Ours)
1812.40
2312.40 8.33
+25.33%
531.73 + 2.72
-36.02%
26386.49
2.21
+16.37%
Table 8 and Table 9 illustrate the results of various methods solving MILPs, with the number of nodes (Nodes) used as the evaluation metric. To evaluate different node selection methods com- pared to the default SCIP, we propose an Improvement metric. Specifically, we define the met- ric by Imx- Nodes(SCTP)-NNaeee (NddeP))) where Nodes(SCIP) represents the nodes of SCIP, and Nodes(SCIP))
N Nodes(M) represents the nodes of the compared method.
Due to the imposition of a 3600-second time limit, instances exceeding this duration were capped at 3600 seconds for statistical purposes. We provide the results which averaging the node counts at the point of interruption for instances. Some instances in Anonymous dataset could not be solved within
20

---

Published as a conference paper at ICLR 2025
this time frame, rendering comparisons of node counts less meaningful, as RankNet only completed 9/18 and SVM completed 8/18 instances within the time constraint.
Although TRGNN does not consistently yield the smallest tree size, it illustrates pivotal observa- tion: reduction in solving time does not invariably equate to a decrease in the number nodes in the search tree. This reinforces proposition that the influence of node selection solving efficiency is multifaceted, intertwining with elements like the cost of path switching, discussed in detail in Section 5.2
D.5 RESULTS WITH DIFFERENT SAMPLE SIZES
We conducted tests to assess the impact of training with an increased number of samples. The results demonstrate a consistent upward trend in performance.
Table 10: Comparison of Solving Time (s) for GNN and TRGNN with sample sizes.
GISP
MaxSAT
FCMONF
Method
Test
Transfer
Test
Transfer
Test
Transfer
SCIP
4.27 1.72
77.82 a 1,31
11.11 + 2.22
322.73 1.76
15.89 a 1.68
2102.49 1.99
GNN light (250 instances)
4.57 1,76
82.34 1,25
11.28 a 1.36
420.44 1.76
14.59 1.59
2311.61 1.83
GNN (1000 instances)
4.18 1.44
71.53 + 1.58
10.08 # 1.41
400.96 1.86
13.57 # 1.94
1968.54 2.19
TRGNN (250 instances)
2.89::11.4
62.02 a 1.46
8.63 a 1.47
300.00 1.72
11.62 1.63
1410,13 a: 1.74
TRGNN instances)
1.40
1.46
1.44
1.76
TRG NN (1000 instances)
2.81 1.42
62.01 1.46
8.51 1.40
306.80 1.71
11.63 + 1.62.
1406. 1.74
D.6 ABLATION STUDY ON TRIPARTITE AND BIPARTITE GRAPH REPRESENTATIONE
With the inclusion of leaf' nodes, the tripartite graph has a complexity of O(V) + +C|+ + |E| + [V][LN), compared the bipartite graph's 's O(IV] + |C| + [E|). While this increases the space overhead, the tripartite representation is more space-efficiene during node selection. For every candidate leaf node, the bipartite approach requires a complete graph representation. leading space complexity of O(LLNI(VV) + [CI + [E])). In problems where the number of constraints is similar or exceeds the number of variables, such as GISP and MaxSAT, the tripartite graph saves space by avoiding redundant representations of constraints and variables.
We conducted an ablation experiment on the bipartite graph approach. In this study, we used the BestEstimate heuristic to pre-filter candidate nodes and then represented each candidate node with bipartite graph within our reinforcement learning framework (BRGNN). The training times for the MaxSAT and GISP datasets are listed in Table 11] The results indicate that the computational over- head primarily arises from reinforcement learning rather than the tripartite graph itself. Moreover, the tripartite graph representation save 29.37% and 20.16% of training time MaxSAT and GISP, respectively.
Table 11: Comparison of training time (s) for GNN, BRGNN and TRGNN.
Method
MaxSAT
GISP
GNN (IL)
62.64
54.07
BRGNN 14391.13
3658.54
TRGNN (Ours)
10164.75
2921.07
We added tests for the average graph construction time, and inference time per instance the MaxSAT and GISP datasets. Although we acknowledged that reinforcement learning required more time during the training phase compared to imitation learning (IL., it did not add to inference time. Additionally, the tripartite graph approach did not increase additional time overhead compared to the bipartite method.
To demonstrate the impact of the tripartite graph representation on solving efficiency compared to bipartite graphs, conducted tests the GISP and MaxSAT datasets. Table 16 shows that
21

---

Published as a conference paper at ICLR 2025
Table 12: Comparison of graph construction time (s) for GNN, BRGNN and TRGNN.
Method
MaxSAT
GISP
GNN (IL.
0.02
0.01
BRGNN
0.01
0.00
TRGNN (Ours)
0.01
0.00
Table 13: Comparison of inference time(s) for GNN, BRGNN and TRGNN.
Method
MaxSAT
GISP
GNN (IL)
0.16
0.05
BRGNN
0.13
0.01
TRGNN (Ours)
0.20
0.01
the "BestEstimate" method performs similarly to the default SCIP settings. Our tripartite graph approach (TRGNN) improves over SCIP and BestEstimate. Notably, the tripartite graph method outperforms the bipartite method, achieving improvements of 19.4% on the MaxSAT dataset and 2.5% on the GISP dataset.
Table 14: Comparison of TRGNN and BRGNN GISP and MaxSAT datasets.
MaxSAT in E [80, 100))
GISP [60, 70)
Method
Time (s)
Wins
Nodes
Time (s)
Wins
Nodes
SCIP
8.13 1.64
3/50
147.51 a 2.02
3.35 a 1,30
6/50
94.81 # 3.67
BestEstimate
7.98 1.68
11/50
177 17,644x 2.13
3,53 + 1,30
8/50
102.99 3.18
BRGNN
7.92 =: 1.67
5/50
200.68
2.05
3.20 + 1.32
17/50
97.27 : 3.59
TRGNN (Ours)
6,38 1.85
31/50
134.93 2.83
3.03 1.27
19/50
83.72 3,51
D.7 ANALYSIS OF PRE-SELECTION SIZE USING THE HEURISTIC ALGORITIIM
In our work, we initially use the heuristic algorithm "BestEstimate" to pre-select a fixed candidate set of size n. To determine the potential impact of the heuristic algorithm on solution quality, increased n from 5 to 10. We recorded the position of the nodes selected by our TRGNN within the rankings provided by the heuristic.
80
80
Percentage (%)
Percentage (%)
40
40
20
20
Position
Position
Figure 4: Histograms showing the distribution of positions picked by TRGNN "BestEstimate," with GISP on the left and MaxSAT on the right.
The results show that in MaxSAT and GISP, nodes ranked higher than 5 by "BestEstimate" are never chosen by TRGNN. This indicates that nodes not ranked among the top by "BestEstimate" have
22

---

Published as a conference paper at ICLR 2025
very low probability of being selected. This is because "BestEstimate" primarily relies the node estimate value which represents an optimistic prediction of the best feasible solution that can be found within the subtree of that node. Nodes ranked toward the end generally have poorer estimates, indicating a smaller probability of leading to optimal solutions.
D.8 ANALYSIS OF THE IMPACT OF THE HEURISTIC ALGORITHM ON THE SOLVING RESULTS
To ensure fair comparisons, we tested GNN algorithm based on imitation learning with heuristic pre-selection CGNN=BestFstimate to eliminate the impact of "BestEstimate" on the solving results. We found that the filtered results were consistent with the original ones because nodes ranked lower by the heuristic "BestEstimate" were seldom chosen by the GNN (see Appendix D.7.
Table 15: Comparison of TRGNN and GNN+BesdEstimate on GISP and MaxSAT datasets.
MaxSAT (n [80, 100))
GISP (n [60, 70))
Method
Time (s)
Nodes
Time (s)
Nodes
SC1P
8.15 1.64
147.51 + 2,02
3.12 = 1,30
77.10 + 3.79
GNN+ BestEsstttt
7.71 1.93
230,72 + 3.30
3.26 1.35
96.99 3.66
TRGNN (Ours)
6.38 1.85
134.93 + 2.83
2.88 1.28
80.50 3.39
D.9 RESULTS WITH THE PURE BRANCH-AND-BOUT FRAMEWORK
While our TRGNN demonstrates significant improvements over the modern solver SCIP, our tri- partite graph representation is specifically tailored for the branch-and-bound framework. Our graph does not account for external solver features, such as restarts or cut pools. An intriguing area for future research lies in designing enhanced representations for cutting planes within branch-and-cut algorithms. We believe this a promising direction.
To better evaluate our node selection method in sancchand-boundee context, tested SCIP with cutting planes and restarts disabled to better evaluate our node selection method within branch- and-bound. The results showed further improvements for both the GNN and our TRGNN methods compared to SCIP. For example, on MaxSAT, the improvement in solving time for TRGNN over SCIP increased from 7.54% 12.71 %, and on GISP from 13.92% 18.67%.
Table 16: Comparison of TRGNN and GNN in branch-and- bound context.
MaxSAT (n E [80, 100))
GISP (n E [60, 70))
Method
Time
Nodes
Time (s)
Nodes
SCIP
4,56 + 1.65
78.48 + 2.66
3.16 1.30
1119.03 + 3.90
GNN
4.42 a: 1.70
205.15 3.01
2.72 + 1.18
1753.04 # 1.52
TRGNN (Ours)
3,98 1.70
156,42 3.24
2.57 1.17
1334.94 1.62
23


Reviews:
[{"review_id": "2LOxSkB8LJ", "reviewer": "Reviewer_6B24", "summary": "In this paper, the authors propose solving the node selection problem using a novel tripartite graph representation combined with reinforcement learning and a Graph Neural Network model. Additionally, the authors have theoretically proven that the tripartite graph representation is sufficient in information theory. The authors used a MDP to model the node selection problem and the reward function consists of three parts, including the updates to the global gap, the potential of a node to lead to an optimal solution and the normalized reward for path-switching steps. The experimental results show that the proposed TRGNN outperforms existing baselines that use learning-based methods on six NP-hard MILP problem benchmarks. Moreover, the trained model demonstrates a certain level of generalization.", "questions": "（1）Please address the issues raised in the weaknesses section.\n\n（2）The paper uses a heuristic algorithm to initially select a subset of nodes, and then employs the model to choose one node from this subset. How do the results of this approach compare to the experimental results of directly using the heuristic algorithm to select nodes without employing the model?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "（1）The paper is well organized. First, the tripartite graph representation of the branch-and-bound tree is explained, and it is proven that this representation can capture sufficient information. Then, the overall algorithm framework is presented, and the components of the MDP are described.\n\n（2）The method of converting the branch-and-bound tree into a tripartite graph presented in the paper is worth learning, especially since the authors prove that the information obtained through the GNN on this graph captures sufficient information contained in the tree.\n\n（3）The experimental results are promising, demonstrating that the approach outperforms recent machine learning algorithms as well as the state-of-the-art best estimate node selection rule.", "weaknesses": "（1）The presentation in the paper is not clear enough and lacks some necessary definitions, such as what a leaf node vertex is. I struggled to understand what the LN set represents until I re-read the paper and carefully examined Figure 1.\n\n（2）For the branch-and-bound tree conversion method, there is a lack of concrete examples. Although a simple conversion is provided in Figure 1, it lacks an explanation of how each step is derived, and there is no description of the features on the edges.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Imf2EZOgQl", "reviewer": "Reviewer_c3Ua", "summary": "The paper addresses challenges in node selection within the branch-and-bound (B&B) algorithm for Mixed Integer Linear Programming (MILP). It introduces two key contributions to improve node selection effectiveness: (1) a novel tripartite graph representation of B&B trees, and (2) a deep reinforcement learning approach that treats node selection as a learning-based strategy, enabling the model to optimize node selection by training on a set of instances.", "questions": "(1) Please analyze the time complexity of the TRGNN and other baseline methods.\n(2) The reinforcement learning framework claims improved node selection by minimizing delayed rewards; however, how are potential biases in the reward function, such as those from pre-selecting candidate nodes, accounted for to ensure fair comparisons with existing machine learning baselines?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper introduces a novel tripartite graph representation of B&B trees, theoretically proven to contain sufficient data for optimal node selection. This representation integrates the problem structure of MILP, typically represented as a bipartite graph, with the global information of the B&B algorithm.\n\n(2) This paper analyzes the shortcomings of prior works, framing node selection as a learning-based strategy and employing reinforcement learning to identify an optimal node selection heuristic that surpasses expert-designed heuristics.", "weaknesses": "(1) It is well-known that B&B trees inherently contain both the detailed information of the B&B algorithm and the problem structure of MILP. This raises the question of whether it is necessary to construct a tripartite graph to represent B&B trees, given that this approach increases the graph scale, resulting in greater storage and computational complexity. The authors should analyze how the advantages of the tripartite representation compensate for these increased demands. Additionally, it would be helpful to assess the specific contributions of the MILP bipartite graph within the tripartite structure and quantify its impact on the representation's effectiveness.\n\n(2) In the MDP process, each action requires a heuristic algorithm to generate candidate nodes. It would be helpful to know the time complexity of this heuristic algorithm and whether its solution quality is affected by the increased scale of MILP instances.\n\n(3) When selecting a specialized solver for MILP, it is advisable to consider higher-performance options like Gurobi, as this can enhance the credibility of the results. Additionally, the baseline methods used are not the most recent; the latest state-of-the-art approaches for solving MILP should be considered, rather than limiting the focus solely to node selection. Other strategic methods should also be included in the evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "rHqGuuEmbn", "reviewer": "Reviewer_bpuZ", "summary": "This work presents a novel way of selecting nodes in the Branch-and-Bound algorithm, by constructing a sufficient representation that splits the features into “global” features containing information of the root MILP, and “leaf” features containing information on each individual leaves. This allows them to represent the entire tree, while keeping the representation compact by bundeling all features of the principal relaxation into a common bipartite graphs and only representing the changes towards one of the leaf nodes.", "questions": "- Can you re-run the experiments with a single node selector for all tasks?\n- Regarding experiments in table 2: In line 466 you say you use geometric means and standard deviations, while table 2 claims it uses arithmetic means. Which one is used in the table? \n- Do you have an ablation of the impact of your path-switching reward?\n- What are the effects of the truncation to the top-n “best estimate” nodes?\n\nSee \"weaknesses\" for more details.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n-\tWell motivated representation via Mutual information\n-\tCompact representation\n-\tHigh benchmark performance\n-\tThe reward function involving path switching is generally interesting for all node selection methods\n\nI also want to commend the authors for noting the difference in performance of different SCIP versions which is often neglected in comparisons between methods.", "weaknesses": "One notable issue in the sufficiency argument of the tripartite representation is the assumption of a Markov mapping between parent and child, which is not generally true: For instance, restarts or cut pools may add arbitrary external information that is not located in the parent into the child. This means that in modern Branch-and-Bound solvers such as SCIP, one can generally not get the decompositions shown in appendix B. \nIn fact, the method seems to have no way of dealing with cutting planes (it does not even contain features to explain cutting planes).\n\nI recommend qualifying the sufficiency conditions with conditions making clear that these representations are only valid for traditional Branch-and-Bound methods, not more modern restarting Branch-and-Cut methods such as SCIP.\n\nA more general problem is found in the benchmarking: This work trains a node selector on some problem XYZ and then benchmarks on different instances of the same problem XYZ. This is a flawed way of doing benchmarking: If you want to compare a _general_ node selector (SCIP) against your node selector, you also have to use a general problem set. \n\nAs is, the quality of the heuristic is not really meaningful: Generally, humans can also develop better heuristics if the type of problem is known. To show that your method leads to superior performance in one of these tasks (e.g. MAXSAT) you would need to compare against an exact MAXSAT solver. Alternatively, you could also benchmark a single selector on all domains, to show that your method can indeed compete against the general node selectors developed in e.g. SCIP.\n\nThe statement “Experiments show that TRGNN significantly outperforms human-designed and learning-based baselines” is therefore not supported, since both methods are evaluated under different standards (SCIP “one size fits all” vs. learned ones for every instance type).\n\nCan you re-run the experiments with a single node selector for all tasks?\n\n\nFigure 2. is hard to read due to the apparent circular dependency of “n nodes”, TRGNN and the “Q-values”. The figure only makes sense if taken in context with the main text: My recommendation: Remove the arrow from the Q-value vector to the “n nodes” bubble, add numbers to the arrows, and explain the figure step-by-step in the description (the figure should be understandable without needing additional context).\n\n\nFor related work, there are two papers that already include a full tree representation “Learning to branch with Tree MDPs “ https://arxiv.org/pdf/2205.11107 uses a tree-like MDP to do branching, and “Reinforcement Learning for Node Selection in Branch-and-Bound” https://arxiv.org/abs/2310.00112 uses a tree-like state representation fornode selection.\n\nDo you have an ablation of the impact of your path-switching reward? While path switching is a measurable effect in node selection. There are many other aspects as well, like the complexity of a node is not being constant: Depending on how many (dual) simplex iterations you need to restore optimality under the new constraints, and which heuristics are run for how long (e.g. diving heuristics) the cost of exploring a node can vary significantly.\n\nWhat are the effects of the truncation to only the top-n “best estimate” nodes? I understand you can’t test this hyperparameter extensively, but you could give a distribution over which position in the \"best node list\" is picked by your selector. If you record this on a histogram, you could estimate the impact of truncating the top-n to a k<n.\nThis would also show how much your method depends on the quality of the \"best estimate\" node selector.\n\nI generally like this work, with the one big holdup being the lack of generalization of a learned node selector to different problem sets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "RxKcReoOSh", "reviewer": "Reviewer_zdY7", "summary": "The paper presents a novel approach to node selection in Branch-and-Bound (B&B) algorithms for Mixed Integer Linear Programming (MILP). It proposes using a Tripartite Graph Neural Network (TRGNN) combined with reinforcement learning to address two major challenges: sufficient representation of the B&B tree and comprehensive node quality assessment. The tripartite graph representation effectively captures tree information, while the reinforcement learning framework uses delayed rewards to optimize node selection. Experiments show that TRGNN significantly outperforms traditional human-designed and learning-based approaches in solving efficiency, achieving notable improvements across a variety of MILP benchmarks.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### 1. **Innovative Representation Approach**:\n   - The use of a tripartite graph representation to capture information about the entire branch-and-bound (B&B) tree is an original contribution. The approach is theoretically proven to be sufficient, ensuring that the representation fully captures the relevant information needed for effective node quality assessment.\n\n### 2. **Reinforcement Learning for Node Selection**:\n   - The paper employs reinforcement learning (RL) to learn an effective node selection policy, which is a significant improvement over traditional imitation learning methods. By incorporating delayed rewards, the RL-based approach captures the long-term impact of node selection decisions, leading to better outcomes.\n\n### 3. **Comprehensive Evaluation Metrics**:\n   - The introduction of three metrics—global gap updates, potential for optimality, and path-switching overhead—provides a more comprehensive assessment of node quality. This helps the TRGNN model make more informed decisions during the B&B process.\n\n### 4. **Strong Experimental Results**:\n   - Experiments demonstrate that TRGNN significantly outperforms both human-designed heuristics and other learning-based methods, including GNN-based models and traditional SVM approaches. TRGNN achieves up to 59.42% reduction in solving time, indicating its practical impact on MILP problem-solving efficiency.\n\n### 5. **Generalization Capability**:\n   - TRGNN's ability to generalize to larger MILP instances beyond those used in training is a key strength. The model outperforms existing solvers on significantly larger problem sizes, which underscores the scalability and robustness of the proposed approach.\n\n### 6. **Theoretical Grounding**:\n   - The paper provides solid theoretical foundations for its approach, including proofs that the tripartite graph representation is sufficient in information theory. This enhances the credibility of the methodology and helps justify its effectiveness in solving the MILP node selection problem.\n\n### 7. **Efficient Learning**:\n   - The TRGNN model demonstrates higher learning efficiency compared to conventional models, requiring fewer training samples to achieve comparable performance. This efficiency is beneficial in scenarios where data collection is costly or time-consuming.", "weaknesses": "### 1. **Complexity of Graph Representation**:\n   - **Weakness**: The tripartite graph representation is complex, especially for large-scale instances, which may lead to high computational costs.\n   - **Suggestion**: Consider providing an analysis of the computational overhead introduced by the tripartite graph representation. Discuss possible optimizations or alternative representations that balance complexity and computational efficiency.\n\n### 2. **Limited Baseline Comparisons**:\n   - **Weakness**: The experimental comparisons focus primarily on human-designed heuristics and learning-based models but do not include more recent or diverse approaches in GNN-based optimization or other advanced reinforcement learning methods.\n   - **Suggestion**: Expand the list of baseline models to include state-of-the-art approaches in GNNs and other deep learning-based optimization techniques. This would provide a more comprehensive evaluation of TRGNN's advantages.\n\n### 3. **Scalability Concerns**:\n   - **Weakness**: Although the model shows good performance on larger problem instances, there is insufficient discussion on the scalability of the method concerning memory requirements and computational resources.\n   - **Suggestion**: Include an analysis of memory consumption and computational requirements when scaling the model to large MILP instances. This would help understand the practical limitations and requirements for deploying the approach in real-world scenarios.\n\n### 4. **Lack of Ablation Study on Graph Representation**:\n   - **Weakness**: The paper does not thoroughly evaluate the effectiveness of the tripartite graph representation versus other potential graph representations (e.g., bipartite or simpler versions).\n   - **Suggestion**: Conduct an ablation study comparing the tripartite graph representation with other simpler graph structures to demonstrate why it is more effective in capturing relevant information for node selection.\n\n### 5. **Limited Analysis of Hyperparameters**:\n   - **Weakness**: There is little to no discussion on the sensitivity of the model's hyperparameters, such as the reinforcement learning reward weights and the parameters in the graph convolution layers.\n   - **Suggestion**: Provide a sensitivity analysis of key hyperparameters, explaining how they impact the model's performance. This would help practitioners effectively tune the model for different MILP problems.\n\n### 6. **Implementation and Practical Considerations**:\n   - **Weakness**: The paper lacks detailed information on implementation aspects, such as training time, hardware requirements, and challenges in real-world implementation.\n   - **Suggestion**: Add practical details about the model's implementation, including the training time required for various datasets, hardware used, and potential challenges encountered during implementation. This would aid in understanding the practical feasibility of adopting TRGNN.\n\n### 7. **Limited Applicability to Non-MILP Problems**:\n   - **Weakness**: The paper focuses exclusively on MILP problems and does not discuss whether the proposed approach could be generalized to other types of optimization problems.\n   - **Suggestion**: Include a discussion on the potential for adapting TRGNN to other combinatorial optimization problems, such as Mixed-Integer Nonlinear Programming (MINLP) or general constraint satisfaction problems. This would extend the relevance of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)