Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
Authors: Abdel Ghani Labassi
Didier Chételat
Andrea Lodi
Venue: NeurIPS 2022 Accept (2022)

Abstract: Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model to tackle this problem, where the nodes are represented as bipartite graphs with attributes. Similar to prior work, we train our model to imitate a diving oracle that plunges towards the optimal solution. We evaluate our method by solving the instances in a plain framework where the nodes are explored according to their rank. On three NP-hard benchmarks chosen to be particularly primal-difficult, our approach leads to faster solving and smaller branch- and-bound trees than the default ranking function of the open-source solver SCIP, as well as competing machine learning methods. Moreover, these results generalize to instances larger than used for training. Code for reproducing the experiments can be found at https://github.com/ds4dm/learn2comparenodes.

Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
Abdel Ghani Labassi Johns Hopkins University alabass jhu. edu
Didier Chételat Polytechnique Montréal didier. chetelatt@oolyttl.ccoo ca
Andrea Lodi Cornell University
Indrea.lodiccorma edu
Abstract
Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model tackle this problem, where the nodes are represented as bipartite graphs with attributes. Similar to prior work, we train our model to imitate diving oracle that plunges towards the optimal solution. We evaluate our method by solving the instances in plain framework where the nodes are explored according to their rank. On three NP-hard benchmarks chosen be particularly primal- -dificcc,, our approach leads to faster solving and smaller branch- and-bound trees than the default ranking function of the open-source solver SCIP, as well as competing machine learning methods. Moreover, these results generalize to instances larger than used for training. Code for reproducing the experiments can be found at https:://// :/gi thub. com/ commddddm/// homm/s/dmmeeeanneeoon learn2comparenddss
Introduction
Mixed-integer linear programming is an optimization paradigm with applications as varied as airline scheduling [4], CPU management [26], auction design [1] and industrial process scheduling [14]. Modern solvers rely on the branch-and-bourd (B&B) algorithm, which recursively divides the search space into a tree, solving relaxations the problem until an integral solution found and proven optimal [25]. Throughout this procedure, numerous decisions must be repeatedly made, such as the choice of the variable on which to branch or the choice of primal heuristics to run at every node. These decisions often dramatically impact final performance yet still poorly understood [3]. Traditionally, these would be made according to hard-coded expert heuristics implemented in solvers. Recently, however, there has been surge of interest using machine learning methods learn such heuristics [5], in particular for variable selection [17, 19, 36, 27, 13].
Despite this success, other critical branch-and-bound decision tasks remain poorly studied. One of the most important is the node comparison problem. Throughout solving, the algorithm must repeatedly select the next node to subdivide, task known as node selection. It maintains priority list of the open nodes, ordered according to a node comparison function. This list is then used to select the next node subdivide, either by simply choosing the highest-ranked node through some more complex paradigm. Interestingly, a few works have proposed to use machine learning methods to derive node comparison functions [22, 33, 35]. This is particularly promising since the problem is naturally amenable to statistical learning methods. However, despite promising results, challenges hinder progress in this area. Most prominently, it is unclear how to represent nodes, which vary in the number of variables and constraints. Existing approaches have so far relied on fixed-dimensional representations that necessarily lose information.
In this paper, inspired by work on the related problem of variable selection in branch and bound [17, 19, 36, 27], we propose to tackle this problem by an approach based on graph neural networks (GNNs) [18]. We represent nodes by bipartite graphs with attributes and use a siamese architecture
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to model the node comparison function. This node representation allows complete information regarding the nodes be provided to the model, reducing the amount of manual feature engineering. In line with previous work on this node comparison problem [22, 33, 35], we train the network using imitation learning to approximate a diving oracle that plunges towards the optimal solution.
We compare our GNN approach against the support vector machine approach of He et al. [22], the feedforward neural network approach of Song et al. [33] and Yilmaz and Yorke-Smith [35], and the default node selection rule of the open-source solver SCIP [16]. In addition, we compare against the node comparator of this same branching rule but with a highest-rank node selection rule. Results show that our approach leads to improved node selection compared to competing machine learning approaches and, in fact, often improves on the default rule in SCIP itself. In addition, these results generalize to instances larger than those used for training.
The paper is divided follows. In Section 2, review the related literature, while in Section 3, we describe the rranch-and-boum algorithm and the node comparison problem. In Section 4, we describe our state representation, neural network architecture, as well training procedure. Finally, we detail experimental results in Section 5.
2 Related works
The first steps towards learning node comparison heuristics in branch and bound were taken by He et al. [22]. In this work, they propose to train a support vector machine (SVM) model using the DAGGER algorithm [32] to imitate the node comparison operator of a diving oracle. However, they only use it in combination with a learned pruning model, which cuts off unpromising branches of the branch-and-bound tree, yielding something more analogous to a primal heuristic. They report improvements in the optimality gap against SCIP under node limit and Gurobi [20] under a time limit on four benchmarks.
Subsequently, Song et al. [33] trained a multilayer perceptron (MLP) RankNet model to perform node comparison using a novel approach they call retrospective imitation learning. In this approach, as applied to the branch-and-boung algorithm, solver is run until a certain node limit (or potentially until optimality). The node selection trajectory is then corrected into a shortest path to the best solution found during the process. When the solver is run until optimality, this is in effect identical to trajectories generated by the diving oracle. practice, they generated trajectories using Gurobi and trained using the DAGGER and SMILe [31] imitation learning algorithms. Unlike He et al., they provided results that only use the learned node comparator without an additional pruning operator. On a collection of path planning integer programs, they report impressive improvements in the optimality gap under node limit against Gurobi and SCIP. However, their appendix also reports more mitigated results on more challenging combinatorial auctions benchmark used by He et al.
Finally, and more recently, Yilmaz and Yorke-Smith [35] proposed to learn limited form of feedforward neural network node comparison operator that decides whether the branch-and -adhc---n--buudd algorithm should expand the left child, right child or both children of node. This operator can then be combined with a backtracking algorithm to provide a full node selection policy: in effect, this can be interpreted by combining the neural network node comparator of Song et al. with a node selection rule that only calls it on children of the current node, and reverts to depth-first search otherwise. They use the state encoding from Gasse et al. [17] and train their model using behavioral cloning [30] to imitate oracle that prioritizes nodes a path towards one of the k > 1 best solutions in effect generalization of the He et al. oracle. On three benchmarks, they report improvements in time and number of nodes against He et al., and sometimes in nodes against SCIP; in fourth, they are slightly worse than He et al.
Background
A mixed-integer linear program (MILP) is an optimization problem of the form
arg min {c'x: Ax 2 b}. xE xB
for a matrix A E mx and vectors E Rm e E Rd. The manch-and-bount algorithm solves this problem recursively follows. First, the linear program (LP) relaxation arg minlge" (c'z: Ar 2 6}
2

---

a= nodez < nodes
Figure 1: The node comparison problem. Here the solver is asking the NODECOMP function to rank the open nodes and 4, which chose to prioritize the latter over the former.
is solved, which can be done efficiently in practice. This relaxation yields solution x², with a lower bound c'x" to the MILP. If the LP solution satisfies the integrality constraints, x² Z R=-k, the problem is solved. Otherwise, we can take any non-integer æ; for some 1 I i s k, and divide the problem into two subproblems
arg min {c'x: Ar 2 b, [ #E2* xRn-k
arg min (dx: Ax 2 b, 2 ZE2 xBa-k
L +
The process then starts again, recursively constructing a tree of subproblems with their associated linear relaxation solutions. The branching stops when subproblems are found unfeasible or when their linear relaxations are integral, in which case they furnish feasible solutions. These solutions can be used to prune parts of the branching tree, whose dual bounds are worse than the best-found solution so far.
Throughout this algorithm, nodes in the branch-and-bound tree, corresponding to subproblems, must be selected for further branching: this known as the node selection problem. In SCIP, this is implemented through a NODESELECT method that takes as argument the list of open nodes and must choose one for subdivision. In practice, it is expensive to rank open nodes every node selection step, and solvers maintain a priority list of open nodes throughout solving. Whenever new nodes are created, they are inserted in the priority list according which takes two nodes as argument and returns whether the first node, the second node or none are to be preferred. The NODESELECT function can then make use of the ranking; in the simplest strategy, it simply selects the node with the highest rank. More complex node selection strategies are also possible, such as prioritizing the highest-ranker children or sibling of the currently opened node over arbitrary leaves. Although this description uses SCIP terminology, other solvers work similarly.
node comparison function NODECOMP,
The current state-of-the-art NODECOMP rule, used by default in most solvers, is best estimate search [6. 15]. In this scheme, every node associated with an estimate of the increase in objective value resulting from selecting the node, computed from pseudocost statistics. The heuristic then selects the node with the highest estimate. Other popular rules include best-first search [21], which prioritizes nodes with the best dual bound, and depth-first search [12], which prioritizes the deepest node.
As detailed by He et al. [22], the task of designing a good NODECOMP function can be assimilated to finding good policy in Markov decision process. In this process, the solver is interpreted as the environment, which calls the NODECOMP (node,, nodes compared. This policy is provided information about nodes, which can be interpreted s = (node,, node2), and then takes an action as to whether to prefer the first node, the second node, none, (node; -better, node equal). This repeated decision making continues until no new nodes need insertion, that is, until the solving is complete. The process is illustrated in Figure 1.
policy whenever it needs two open
state
4 Methodology
We now describe our approach to learning good NODECOMP functions. Since the problem can be assimilated to Markov decision process, we follow previous work [22, 33, 35] and train by imitation learning to mimic expert policy.
3

---

Constraint verticas
Variable vertices
Global
primaal extimate
dool eviimate
Rype
Cj My
Eypee
Figure Bipartite graph representation of node.
Node graph
Embedding
Graph convolutions
Pooling
Norm
Score
AvgPool
Layer Norm
Graph
Conv
I-
Linear
AvgPool
0
Figure 3: Architecture of the GNN scoring function g-
4.1 State representation
Our learned NODECOMP(noden, node2) takes as input a state (node), nodez), which represents pair of nodes. In the related problem of variable selection, important advances were achieved by the usage of bipartite graph representations of the state the solver, allowing for the first time machine learning improve over human-designed heuristics in full-fledged solvers [17, 19, 36, 27]. These representations form the current state-of-the-art approach on this problem, and offer many advantages, such being cermutation-invarian in the labeling of the variables and constraints. Inspired by this innovation, we similarly propose to represent each node as bipartite graph, where side there variables, in the sub-MILP encoded by the node. We draw an edge between a constraint and a variable vertex if the coefficient associated with the variable in the constraint is nonzero. To each constraint vertex we associate a vector of features, namely its right-hand side b, and its type (>, < =). Similarly, to each variable vertex j we associate vector of features, namely its objective coefficient с₁, upper and lower bounds uj and (j. and type (binary, integer, or continuous). In addition, we associate the nonzero coefficient of the variable the constraint to each edge. Finally, an additional global vertex of attributes associated with the whole node is added, unconnected with the rest. To this vertex, we associate two features, namely an estimate of the objective value of the best feasible solution in the subtree of the node and an estimate of the dual bound achieved at the node, through the SCIPnodeGetEstinas
many vertices constraints, and the other side many vertices as
and SCIPnodeGetLoverbone The representation is illustrated in Figure 2.
SCIP functions. respectively.
4.2 Model
Our NODECOMP function has the form
-better if (node), nodez) S 0.5, nodee-better if (nodez, nodez) > 0.5,
NODECOMP(node),
(I)
where f [0. 1] is a classification machine learning model. Our model always prefers one node over the other, and never returns a = equal as an action. The classification model takes the form [node,, nodez) = a (g(node,) a scoring function with single dimensional, real-valued output. This siamese architecture [7] naturally symmetric, in the sense that model satisfies (node,, node,) 1 -f fnode,, node2).
g(nodez)) where stands for the sigmoid function, and E R is

---

Just as for the design of the state representation, we take inspiration from the latest line of work on variable selection [17. 19, 36, 27] and use graph neural network [18] model for our scoring function g. with suitable modifications for this node comparison problem. A diagram of the architecture is provided as Figure 3. An important advantage of this model is that, just as in the variable selection setting, the same model can be trained on problems of varying number of variables and constraints. In detail, the constraint and variable features of the node are first transformed by an 32-dimensional embedding layer and then pass through three graph convolutional layers, with 8, 4 and 4 dimensions each. Each layer uses ReLU activation function. The representations of the constraint and variable vectors then pooled by average separately and then concatenated with the global features of the node. Finally, the resulting vector's 's & norm is taken, which is outputted as the score.
4.3 Training procedure
Our training procedure is similar to the one of He et al. [22]. Just like them, we aim to imitate a "diving oracle" NODECOMP policy, which prioritizes node if it contains the optimal solution x", and falls back on another heuristic (we use best estimate search) if this is not the case: nodet-better
if ox nodel, x E node2,
ORACLEENOODECOM/(ndde, nodez)
nodez-better
nodez) otherwise. Since nodes represent a partition of the feasible space, the optimal solution cannot be in the feasible spaces of both nodes simultaneously, so this is well-defined. As this NODECOMP function uses knowledge of the optimal solution, it cannot be used in practice; however, it can be on training instances by precomputing optimal solutions, and it is worthwhile to try to imitate its decisions without this additional knowledge. To do this, He et al. use DAGGER, an expensive imitation learning algorithm that aims to diversify the states from which the expert is sampled through several rounds of training. We propose simpler procedure that achieves similar result with lower computing requirements.
ESTIMATE-NODECOMPPNNN
This procedure runs follows. We first solve the instances using a solver, collecting their optimal solutions. We then solve the instances again, using a plain highest-priority NODESELECT rule. When the solver calls the NODECOMP function, we query the oracle, and if it chooses node, -better or nodez-better, we collect state information s and the resulting decision a as an expert sample (s, a,). Next, crucially, take the opposite decision than the oracle recommends, making mistake on purpose. This increases the variety of states explored during the sampling phase and makes the state distribution more aligned with the machine learning policy, which is bound to make mistakes. We follow this procedure until the solving is completed.
As result of this sampling process, we obtain dataset of expert samples D {(,, a:)} from which to train our machine learning policy. Since we saved samples when the oracle had a preference, the actions can be interpreted as labels 0 or I according to whether the first second node was preferred. Learning the preference of the oracle then becomes a simple classification task that can be performed by minimizing a cross-entrope loss over our classifier f. Since mistakes coming early on in the sampling process can be exponentially costly, we weight the samples during training using an exponentially decreasing scheme, exp(1 + ld1 d2l)/ min(d1, d2)). where d1, d2 the depths of the first and second nodes, respectively. This is similar to the exponential weighting scheme used by He et al.
5 Experimental results
We now present experimental results on three NP-hard problems. We evaluate each machine learning method by running it in SCIP with a simple highest-priority rule that falls back to ESTIMATE after two feasible solutions have been found, as we detail in Section 5.4. We also evaluate the default SCIP node selection rule (that is, with both default NODESELECT and NODECOMP). Code for reproducing these experiments can be found at https: https://gitae //tgttub..ttttt//// com/ comm///addm/eeerrnooompeeenodddd
5.1 Benchmarks
We evaluate on three NP-hard instance families that are particularly primal-difficult, that is, for which finding feasible solutions is the main challenge. Those are instances for which improved
5

---

Table 1: Test accuracies of the different machine learning methods in imitating the diving oracle.
Test FCMCNF
Test MAXSAT
Test GISP
91.5%
90.6%
MLP
97.8%
97.9%
95.6% 97.7%
GNN
95.7%
97.0%
node comparison is likely to have a particularly broad impact, so differences between methods should be clearer. The first benchmark is composed of Fixed Charge Multicommodity Network Flow (FCMCNF) [23] instances, generated from the code of Chmiela et al. [10]. We train and test on instances with n 15 nodes and
1.5 n commodities, and also evaluate on larger transfer instances with = 20 nodes. The second benchmark is composed of Maximum Satisfiability (MAXSAT) instances, generated following the scheme of Béjar et al. [9]. We train and test on instances with a uniformly sampled number of nodes n E [60, 70] and transfer on instances with E [800- 100]. Finally, our third benchmark is composed of Generalized Independent Set (GISP) [11] instances, generated from the code of Chmiela et al. [10]. We train and test on instances with uniformly sampled number of nodes E [60, 70] and transfer on instances with n E [70 80). All these families require an underlying graph: we use in each case Erdös-Rényi random graphs with the prescribed number nodes, with edge probability p = 0.3 for FCMCNF and p = 0.6 for MAXSAT and GISP.
5.2 Baselines
We compare against the state-of-the-art best estimate node comparison rule [6, 15]. This is the NODECOMP function used by default in SCIP, in conjunction with a diving NODESELECT rule that prioritizes children and siblings of the currently focused node. To disentangle the effect of this NODESELECT rule, we report both results with this rule (default SCIP) and with a plain NODESELECT that always selects the highest-ranked node (ESTIMATE). We also report the performance of the expert we aim to imitate, the diving oracle (ORACLE). This method cheats by having access the optimal solution ahead of the solving.
In addition, compare against two competing machine learning approaches: the support vector machine [34] approach of He et al. [22] (SVM) and the RankNet feedforward neural network [8] approach of Song et al. [33] and Yilmaz and Yorke-Smith [35]. The former uses a multilayer perceptron; the latter uses the same, except for one benchmark where they use three hidden layers. For simplicity, we use multilayer perceptron for all benchmarks (MIP), with hidden layer of 32 neurons. The features used in the three papers are roughly similar; again, for simplicity, we use the eiedddiimnsiooall features of He et al. for both the SVM and the MLP. All methods except the default SCIP use a plain highest-rank NODESELECT.
5.3
Training
We use the training procedure of Section 4.3 for all machine learning models. The SVM model is trained using the scikit-learn [29] library: the MLP and the GNN implemented in PyTorch [28] and optimized using Adam [24] with training batch size of 16. Running the sampling procedure on 1000 training and 100 test instances yielded 16285 training and 3019 test samples for FCMCNE, 41299 training, and 4868 test samples for MAXSAT, and 41299 training and 4868 test samples for GISP. We train/evaluate using Nvidia@ Tesla V100 GPU and Intel@ Xeon Gold 6126 CPU. Test accuracies of the different models can be found in Table 1.
5.4 Evaluation
We evaluate each machine learning model by setting SCIP's NODECOMP function be the NODECOMP function associated with the machine learning model (Eq. 1). In parallel, the NODESELECT function designed to use the highest ranked node according to this node comparison function, until two feasible solutions have been obtained. After this state, it falls back to ESTIMATE. This has the effect of prioritizing the learned node comparison during the initial phases of the solving, in inzeenndepnn manner.

---

Table 2: Evaluation of node comparison methods in terms of the 1-shifted geometric mean of the number of nodes and solving time (in seconds) over the instances, with the geometric standard deviation. For each problem, machine learning models are trained on instances the same size as the test instances, and evaluated on those and the larger transfer instances (50 instances each).
Test FCMONF
Transfer FCMCNF
Test MAXSAT
Transfer MAXSAT
Test GISP
Transfer GISP
Nodes
Nodes
Time
Nodes
Time
Nodes
Time
Nodes
Nodes
ORACLE
15:44
3.80
75:44
19.9
10242
6,174188
160:2
8.911.5
98:3
4.18413
10624:2
22.6:::55
SCIP
41:5
1.64
178#4
2,
14742
9
171#2
12.914
18442
4,38
153342
19.1
ESTIMATE
21=5
1.09=115
122#5
23.8+200
17742
8.16117
247#2
12.1216
21842
4.64
1435+2
249:17
SVM
20:25
1.10:11.5
13345
1.
150433
7.34
22542
1077
20743
4,5741.
1295422
1.
MLP
21=5
4.15=1.5
115#5
24.1
15743
7.76+199
215-2
108811.6
20933
4.72+13
1238+2
23.0+::66
GNN
19:55
4.14::155
12245
1,
11743
6.6611199
171:2
9.11166
170#3
4.64::1
1203422
22841.5
We average results over the benchmarks using the 1-shifted geometric mean with geometric standard deviation to measure the average and dispersion of B&B tree size and solving time on our benchmarks. This metric the standard used in the mixed-integer programming community since it reduces outlier effects from both directions (too easy and too hard instances), as discussed in Appendix A3 of Achterberg [2]. We evaluated on 50 test and 50 transfer instances, as explained in Section 5.1. Table 2 summarizes the results.
5.5
Discussion
As can be seen in Table both the MLP and GNN achieve similar accuracies on the datasets, with the SVM lagging a bit more behind. When used in solving, however, the GNN more consistently dominates the other machine learning approaches. More impressively, the model is often competitive with or even better than the SCIP default node strategy, particularly on the MAXSAT problems. In addition, these results generalize larger instances than those trained on. This is the case despite using a plain NODESELECT rule, which suggests that most of the difficulty in node selection can be reduced by the design of a good NODECOMP function. This is particularly attractive as this is a problem that is naturally amenable to machine learning methods, as described in this work.
A disadvantage of the imitation learning approach follow is that it is limited by the performance of the expert itself. If the oracle does not beat a baseline, imitating it is unlikely to bring gains. A good example the largest benchmark, transfer GISP: this is the only family where the oracle does not beat the SCIP default rule in time. Therefore, is unsurprising that no other machine learning method was able beat it. Note that nonetheless, the GNN is the model that manages come the closest to the performance of the oracle on this benchmark, suggesting strong imitation capabilities.
Conclusion
This work proposes to train graph neural network to compare nodes in branch-and and-bound solver for solving mixed-integer linear programs. We represent nodes as bipartite graphs with features and train neural network to imitate diving oracle that plunges towards the optimal solution. On three primal-diffie NP-hard benchmarks, our approach outperforms prior machine learning approaches and often even the SCIP default node selection strategy, while generalizing larger instances than trained on.
An interesting direction for future work would be to combine variable and node selection strategies. Besides the fact that the two problems are tightly linked, good node selection is particularly important in primal-dit -iffflll problems, while good branching is particularly useful in dual- problems. Combining the two could thus help outperform current expert-designed strategies on generic problems.
Acknowledgements
This work was supported by the Canada Excellence Research Chair program. In addition, the first author was affiliated with the Department of Computer Science and Operations Research of the University of Montreal during most of the project.
7

---

References
[1] Jawad Abrache, Teodor Gabriel Crainic, Michel Gendreau, and Monia Rekik, Combinatorial auctions. Annals of Operations Research, 153:131-164, 2007.
[2] Tobias Achterberg. Constraint Integer Programming. PhD thesis, ZIB, Berlin, 2007.
[3] Tobias Achterberg, Timo Berthold, Stefan Heinz, Thorsten Koch, and Kati Wolter. Constraint integer programming: Techniques and applications. ZIB-Report 08-43, Zuse Institute Berlin, 2008.
[4] Christopher Bayliss, Geert De Maere, Jason A.D. Atkin, and Marc Paelinck. A simulation scenario based mixed integer programming approach to airline reserve crew scheduling under uncertainty. Annals of Operations Research, 252:335-233 363, 2017.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d' d'horizon. European Journal of Operational Research, 290:405-422 ,,,,,22,,000 2021.
[6] Michel Bénichou, Jean-Michel Gauthier, Paul Girodet, Gerard Hentges, Gerard Ribière, and Olivier Vincent. Experiments in mixed-integer linear programming. Mathematical Program- ming, 1:76 94, 1971.
[7] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using "siameee" time delay neural network. In Advances in Neural Information Processing Systems, volume pages 737-744, 1993.
[8] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd International Conference Machine Learning, pages 89-96, 2005.
[9] Ramón Béjar, Alba Cabiscol, Felip Manyà, and Jordi Planes. Generating hard instances for MTxSAT. In Proceedings of the 2009 39th International Symposium on Multiple- Hultiple-Valued Valued Logic, pages 191-195, 2009.
[10] Antonia Chmiela, Elias Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch and bound. In Advances in Neural Information Processing Systems, volume 34, pages 24235-24246, 2021.
[11] Marco Colombi, Renata Mansini, and Martin Savelsbergh. The generalized independent set problem: Polyhedral analysis and solution approaches. European Journal of Operational Research, 260:41-55, 2017.
[12] Robert J. Dakin. A tree-search algorithm for mixed integer programming problems. The Computer Journal, 8:250-255 255, 1965.
[13] Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, and Saña Kedad-Sidhoum. Rein- forcement learning for variable selection in a branch and bound algorithm. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 176-185, 2020.
[14] Christodoulos A. Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139:131- 162, 2005.
[15] J.J.H. Forrest, J.P.H. Hirst, and J.A. Tomlin. Practical solution of large mixed integer program- ming problems with UMPIRE. Management Science, 20:736-773, 1974.
[16] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Mare E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. ZIB-Report 20- 10, Zuse Institute Berlin, 2020.

---

[17] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, volume 32, pages 15580-15599 2019.
[18] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, volume 2, pages 729-734, 2005.
[19] Prateck Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. In Advances in Neural Information Processing Systems, volume 33, pages 18087-18097, 2020.
[20] Gurobi Optimization LLC. Gurobi Optimizer Reference Manual, 2020.
[21] Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determina- tion of minimum cost paths. IEFE transactions on Systems Science and Cybernetics, 4:100-107, 1968.
[22] He He, Hal Daume III, and Jason M. Eisner. Learning to search in branch-and-bound algorithms. In Advances in Neural Information Processing Systems, volume 27, pages 3293-3301, 2014.
[23] Mike Hewitt, George Nemhauser, and Martin Savelsbergh. Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS Journal on Computing, 22:314-325 325, 2010.
[24] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint /412.69911 2014.
[25] Ailsa H. Land and Alison G. Doig. An automatic method for solving discrete programming problems. In 50 Years of Inieger Programming 1958-2008, pages 105-132. Springer, 2010.
[26] Michele Lombardi, Michela Milano, and Andrea Bartolini. Empirical decision model learning. Artificial Intelligence, 244:343-367, 2017.
[27] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoguue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint 1rX1v:2012.13349, 2020.
[28] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, 2019.
[29] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 012282-22830, 2011.
[30] Dean A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3:88-97, 1991.
[31] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 661-668 JMLR Workshop and Conference Proceedings, 2010.
[32] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 627-635, 2011.
[33] Jialin Song, Ravi Lanka, Albert Zhao, Aadyot Bhatnagar, Yisong Yue, and Masahiro Ono. Learning to search via retrospective imitation. arXiv preprint
2018.

---

[34] Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer Science & Business Media, 1999.
[35] Kaan Yilmaz and Neil Yorke-Smith. study learning search approximation in mixed integer branch and bound: Node selection in SCIP. AI, 2:150-178, 2021.
[36] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing waanchhand-boune search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages
2021.
10

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] We discussed the main limitation of the work, which is that the performance is limited by the performance of the oracle expert.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our objective is improve the efficient solving of discrete optimization problems. Although any mathematical tool has the potential of having a negative societal impact, we believe that the fact that we limited ourselves synthetic problems with no known misuse potential limits potential societal impact. (d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A] The work is purely experimental.
(b) Did you include complete proofs of all theoretical results? [N/A] The work is purely experimental.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes]] We are attaching the code as supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We detail the training procedure and model hyperparameters: in addition, we provide the code to run the experiments.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We provide standard deviations with respect to the different instances in the evaluation benchmarks.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5.3. We indicate the GPU on which neural network training and inferences are made, and the CPU which the mixed integer programming solver runs.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Our work uses several libraries and generators, which are cited.
(b) Did you mention the license of the assets? [Yes] All the code and library we make use open-source, which we mention the text.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Code will be public and contains the data generator, our model and our reimplementa- tion of competitors.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We did not other datasets: data is synthetically generated. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We did not use other datasets: our data is synthetically generated.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
11


Reviews:
[{"review_id": "kd3kTsY-rYp", "reviewer": "Reviewer_ksTx", "summary": "Branch and bound is a fundamental component for solving the mixed integer linear programming problem. As one of the building block, node comparison function takes the responsibility of choosing next node to subdivide. In this work, a graph neural network (GNN) method is proposed by formalizing the way to represent the nodes when searching the next step to go. Different from previous work, the node features are extracted from the associated properties of linear equations and objective function. Oracle node division is regarded as the supervised data to train the scoring function based on GNN model. It's interesting to see the application of GNN method to solve NP hard problems after revisiting the original optimization task. The novelty of this work lies at the employment of GNN to learn the node representations to mimic the ideal branch-and-bound solution.", "questions": "Please refer to the weaknesses.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This work gives alternative way to represent the nodes with extracted features from the linear constraints and objective function. A bipartite graph to show the connection between constraints and variables builds the basics for applying the GNN method to score the node in branch-and-bound when comparing a pair of nodes.\n2. As one of the most important part, the proposed method employs imitation learning to optimize the scoring function through learning from the oracle branch-and-bound progress.\n3. Thorough experiments are conducted over real NP hard problems to valid how the proposed method works.\n\nWeaknesses:\n1. The motivation about the reason why employing GNN works is not clear enough. It's better to further comment on why the formalized bipartite graph works and what kinds of benefits that the other methods can not bring?\n2. It's hard to understand how the proposed method can adapt to a new MILP problem. From the presentation of this work, we can see that the training data to learn a node selection policy is based on oracle optimization progress for the problems in hand. One important question that needs to answer is how we can apply the learned GNN-based scoring function to a new problem. After reading the manuscript several times, it's still difficult to catch up with this point.\n3. The experimental results seem to be not strong enough to demonstrate the superiority of the proposed. From the results shown in Table 1 and 2, we can see that GNN-based method can beat the baseline in some tasks, but not show absolute advantage. It deserves more words and insight to explain the function of GNN method.\n\nMinor Issue:\n1. It's difficult to draw connection between Figure 1 and the description shown from Line 111-117. The illustration only shows the comparison between a pair of nodes, but missing key concepts of Markov Decision Process, such as the state, action, and the environment.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dZlkhk0ALO", "reviewer": "Reviewer_zJfP", "summary": "This paper proposes a variable selection method for MILPs based on GNNs, diving oracle, and imitation learning.", "questions": "- What is the most significant contribution of this paper that the authors want to inform the NeurIPS community?\n- What are the qualitative differences against the existing GNN-based approaches for MIP variable selection?", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The proposed method outperforms the SCIP solver in the experiments.\n- Three hard problems with standard and transfer settings are used in the evaluations.\n\n# Weaknesses\n\n- The proposed method is a combination of known techniques and provides few technical insights. This paper does not reach the NeurIPS standards of technical contributions.\n- The proposed approach looks very similar to Solving Mixed Integer Programs Using Neural Networks (Nair et al., 2021). Please discuss the differences and qualitative merits of the proposed method and compare them in the experiments.\n- There are many other ML methods for MILPs, e.g., learn2branch (Gasse et al., 2019) and many others cited in this submission. Please discuss the qualitative merits of the proposed method and compare them in the experiments.\n\nOverall, I feel that this paper fails to contextualize itself. More discussions and evaluations are needed to demonstrate the effectiveness of the proposed method over other approaches.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A4ANC67MUi2", "reviewer": "Reviewer_zm9Z", "summary": "In this paper, the authors design a GNN model for comparing two Branch and Bound (BnB) search nodes of Mixed Integer Linear Programming (MILP) and use this model to replace the node comparison function of an existing MILP solver SCIP. ", "questions": "See the above weaknesses.", "limitations": "The authors discussed that the performance is limited by the performance of the oracle expert. ", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe idea of using a GNN model to evaluate two BnB search nodes is novel and it has great significance to BnB search in other research fields of combinatorial optimization, such as SAT, Traveling Salesman Problem, Maximum Clique Problem, Graph Coloring Problem, etc. \n\nWeaknesses:\n1.\tThis work uses an antiquated GNN model and method, it seriously impacts the performance of this framework. The baseline algorithms/methods are also antiquated.\n2.\tThe experimental results did not show that this work model obviously outperforms other variant comparison algorithms/models. \n3.\tThe innovations of network architecture design and constraint embedding are rather limited.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept