Lookback for Learning to Branch
Authors: Prateek Gupta
Elias Boutros Khalil
Didier Chételat
Maxime Gasse
Andrea Lodi
Yoshua Bengio
M. Pawan Kumar
Venue: Accepted by TMLR ()

Abstract: The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) heuristic in branch-and-bound B&B  solvers. These GNNs are trained, offline and on a collection of MILPs, to imitate a very good but computationally expensive branching heuristic, strong branching. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target heuristic among the neighboring nodes of the B&B tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, a child node's best choice was often the parent's second-best choice. We call this the "lookback" phenomenon. Surprisingly, the typical branching GNN of Gasse et al. (2019) often misses this simple "answer". To imitate the target behavior more closely by incorporating the lookback phenomenon in GNNs, we propose two methods: (a) target smoothing for the standard cross-entropy loss function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework to incorporate harder-to-formulate objectives such as solving time in the final models. Through extensive experimentation on standard benchmark instances, we show that our proposal results in up to 22% decrease in the size of the B&B tree and up to 15% improvement in the solving times.

Published in Transactions on Machine Learning Research (09/2022)
Lookback for Learning to Branch
Prateek Gupta, University of Ouford, The Alan Turing Institute
peupla@rroools.. ac. uk @mmie. torootooooooooooooooo edu didier. chetelat @hotelat@ppolymttt mozime. gasse @polymti..om ca yoshua. bengio @rrilla, quebec andrea. lodi cornell edu pawannSrobote oz. ac. uk
Elias B. Khalil, University of Toronto
Didier Chételat, CERC, Polytechnique Montréol
Maxime Gasse, Mila, CERC, Polytechnique Montréal
Yoshua Bengio, Mila, Université de Montrial, CIFAR Fellow
Andrea Lodi, CERC, Polytechnique Montréal, and Cornell Tech and Technion 11T
M. Pawan Kumar, University of Oxford
Reviewed OpenReview: https: o/penrevwee.... net/ net/ forum? id- EQp Gku5rul
Abstract
The expressive and computationally efficient bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning enhanced Mixed-Integer Linear Programming (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs replacing the branching (variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs are trained, offline and on a collection of MILP instances, to imitate very good but computationally expensive branching heuristic, strong branchêng. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target hcuristic among the neighboring nodes of the B&BB tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, child node's best choice was often the parent's second- best choice. We call this the "lookback" phenomenon. Surprisingly, the branching GNN of Gasse al. (2019) often misses this simple "answer". To imitate the target behavior more closely, propose two methods that incorporate the lookback phenomenon into GNN training: (a) target smoothing for the standard cross-entrops loss function, and (b) adding a Parent-as- Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework that directly considers harder-to-fod forrmmuat-f objectives such as solving time. Through extensive experimentation on standard benchmark instances, we show that our proposal leads to decreases of up to 22% in the size of the B&B tree and up to 15% in the solving times.
1 Introduction
Many real-world decision making problems are naturally formulated as Mixed-Integer Linear Programs (MILPs), for example, process integration (Kantor et al.
2020), production planning (Pochet & Wolsey Fayazi & Vahidi 2018), data center resource
2006), urban traffic management (Foster & Ryan 1976 management (Nowatzki et al.] 2013), and auction design (Abrache et al.) 2007), to name a few. In some applications, such as urban traffic management (Fayazi & Vahidi 2018)), these MILPs need to be solved frequently (e.g,, every second) with only a slight change the specifications. Similarly in data center resource management (Nowatzki et al. 2013), the available machines and tasks that must be served evolve over time, prompting repeated assignments through MILP solving. Even with linear objective function and linear constraints, the requirement that some decision variables must take on integer values makes MILPs NP-Hard (Papadimitriou & Steiglitz 1982)-
As a result, the Baachhand-Bound (B&B) algorithm (Land Doig 1960) is used in the modern solvers effectively prune the search space of the MILPs to find the global optimum. B&B proceeds by recursively splitting the search space and solving the linear relaxation of the resulting sub-problems, the solution of

---

Published in Transactions on Machine Learning Research (09/2022)
which serves as informative bound to prine the search space. The algorithm continues until solution with integral decision variables is found and proven optimal. Quite naturally, the sub-problems resulting from the branching decisions at each step of the algorithm can be represented as a tree; every node (a sub-MILP) has a parent except the root node.
While seemingly simple, the B&B algorithm must repeatedly make search decisions that are crucial for its efficiency, such the choice of decision variable over which to branch each iteration, problem known variable selection. Even though the worst-case time-complexity of the B&BB algorithm is exponential in the size of the problem (Wolsey 1988 it has been successfully applied in practical settings thanks to the careful design of number of effective search heuristics.
Modern solvers are configured with expert-designed heuristics and are aimed at solving general MILPs. However, assuming that MILPs come from a specific distribution, there has been a recent surge in research
related statistical approaches to learning such houristics, c-g., (He ct al. 20144b Alvarez et al, 2017 Khali]
et al. 2016 Gasse al. 2019: Zarpellon el. al. 2020 Gupla al. 2020: Huang et al. 2022).
(a)
Frequency of lookback condition under strong branching heuristic
30
Ground truth
cauctions
11.1
29.6
GNN
setcover
12.8
facilities
21.8
27.1
indset
21.9
55.9
(b)
(c)
(d)
(e) indset
cauctions
setrover
facilities
56.0
47.8
Validation Accuracy
60.75-
53.0-
47.2
69.50
53.6-
30-
53.4
69.00
86.0
5.2
68 75
GNN
GNN-PAT
GNN
GNN-PAT
GNN
GNN-PAT
GNN
GNN-PAT
(f)
(g)
70
times GNN salving the instance first
12.5
% improvemnnt in solving times
10.0
55
7.5
5.0
45
2.5
40
0.0
couctions
facilities
inoset
cauctions
selcover
facilities
indset
Figure 1: (a) Frequency of the "lookback" property when (i) instances are solved using the strong branching heuristic (Ground truth), and (ii) corresponding frequency with which GNNs would have respected this property on Ground truth. (b)-(e) GNNs trained with the proposed techniques (GNN-PAT) have higher accuracy the validation dataset. (f) GNN-PAT solves test instances faster than other baselines resulting in (g) less time compared to GNNs.
2

---

Published in Transactions on Machine Learning Research (09/2022)
Gasse et al. (2019) proposed to use Graph Neural Network (GNN) for the variable selection problem to imitate the branching decisions of computationally expensive strong branching heuristic that yields the smallest B&B trees in practice on a number of benchmarks. The GNN operates on a bipartite representation of a MILP in which variables and constraints are nodes and an edge indicates that a variable has a non-zero coefficient in a constraint. Such a bipartite representation has several advantages. First, it able to capture the most. crucial invariances of MILPs, namely, permutation invariance the ordering of decision variables variables/coosstrannts /constraints, and, by way of feature engineering, scale invariance to the scaling of constraints or objective coelficients. Second, due to the shared parametric representation, the model can be applied to MILPs of arbitrary size. Thus, GNNs have been extensively used to process MILPs as inputs to a neural network aimed at imitating
various superior heuristic decisions (Huang et al.) 2022 Zarpellon et al. 2020 Nair et al. 2020 Khalil et al, 2022 often oulperforming off-the-shelf solvers with their default parameters/ heaieeteerreeuutttisssss heuristics.
The training of GNNs consists primarily of two steps: (a) Dataset collection: data, i.c., sub-problems and corresponding strong branching decisions, are collected offline by solving reasonably-sized MILPs while invoking, with some exploration probability, either less efficient but faster heuristie, or the strong branching heuristic, and (b) Model Training: assuming independent and identical distribution (i.i.d.) of the collected dataset, GNNs are trained to minimize standard cross-cntropy loss between the predictions of GNNs and the strong branching target.
So far, previous works on learning to branch have tried imitating the strong branching decisions at each node in isolation, thereby ignoring the statistical resemblance in the behavior of the neighboring nodes. However, it often happens that strong branching's top choice at node was the second-best choice at the node's parent, a phenomenon we will refer to onwards as the "lookback" property of strong branching. Figure Ta) shows how frequently this occurs in some standard benchmark instances, labeled for convenience as cauctions (Combinatorial Auction), setcover (Minimum Set Cover), facilities (Capacitated Facility Location), and indset (Maximum Independent Set); see Appendix A for similar statistics on some real- world instance sets, where the lookback property is equally prevalent. Given the importance of decisions closcr to the root node, Figure further shows that this phenomenon is quite prevalent at the top of the tree. Although it appears quite common empirically, this property has never been explicitly pointed out in the literature.
16
Ground truth
GNN
14
Friquetry of lookback car daten per tooth decile
12
10
8
6
4
2
0
1
2 3
4 depth deciie
5
6
8
9 10
Figure 2: (Maximum Independent Set.) Frequency of the lookback property per depth-decile, one of the 10 equally divided portions by depth of the B&BB tree. Ground truth is obtained by solving small instances using strong branching heuristic. Retrospectively, GNNs do not respect the look- back property well enough. For similar statistics on other benchmark problem families, see Ap- pendix B
Since imitation learning aims to mimic the expert as closcly as possible, and the expert exhibits this lookback prop- erty, it follows that successful imitation should exhibit the lookback property as well. However, as can be seen in Figures a) and 2 there frequently vanilla GNNs respect the lookback condition and the fraction of times it is actually observed. Towards closing this gap, we propose two approaches that encourage GNNs trained by imitation learning to respect
big gap between how
the lookback condition, and analyze the effects on solving performance.
A difficulty is that our proposed methods introduce new hyperparameters, which raises the question of how to select them efficiently. Gupta et al.] (2020) used validation accuracy on a few thousand observations collected by solving MILP' of a slightly bigger size than the training instances. We argue that such selection strategy may not serve the true objectives that a practitioner might have. For instance, they might prefer learning-enhanced solver with as small a running time as possible, regardless of the validation accuracy relative to the strong branching oracle. Thus, we also design an improved model selection framework to respect such varied requirements, As shown in Figure ())(e), the resulting combined method (GNN-PAT)
3

---

Published in Transactions on Machine Learning Research (09/2022)
not only increases the validation accuracy each benchmark, but also leads to decreases in the size of the final B&B tree by up to 22% and in the running time by up to 15% (Figure 1 gg). solving most of the instances fastest among the baselines (Figure (f))
To summarize, the contributions of this paper are as follows.
First, we demonstrate through numerical experiments that the "lookback" phenomenon often occurs in practice (see Figure and
Second, we propose two ways of exploiting this phenomenon, namely through target softening, and through a regularizer term that encourages the GNN to exhibit this phenomenon.
Third, we propose a model selection framework to incorporate harder-toofformulate practical objectives such as minimum solving times.
The paper is divided as follows. Sections and review the literature and preliminary notation and definitions, respectively. Section proposes techniques to exploit the lookback phenomenon in imitation learning. Scction 5 details our proposed hyperparameter selection framework. Then, Scction c presents experimental results that show the benefits of these adjustments. Finally, in Section 7 we discuss implications
of our proposals, limitations, and potential future directions, concluding in Section
2 Related Work
The problem of variable selection in B&B basod MILP solving has been studied quite extensively. While the gold standard strong branching heuristic yields the smallest B&B trees, due to the high computational cost. per iteration it is impractical (see Section 3 for details). Thus, in its early years, the focus of research has been on hand-designed heuristic methods (Applegate et al. 1995 Linderoth & Savelsberghi 1999) that are faster and sufficiently good. As a result, reliability pseudocost branching (RPB) (Achterberg et al 2005) became the preferred branching strategy to solve general MILPs. RPB combines the lookahead strengths of strong branching heuristic with faster estimations offered through computationally inexpensive measures of performance (such as pseudocosts (Linderoth & Savelsbergh 1999h).
In the last decade, researchers have proposed machine learning (ML) methods to imitate the strong branching heuristic, thereby leveraging the computationally inexpensive nature of the learned functions. For exam- ple, Alvarez et al. (2017) used extremely randonized trees on the data collected oflline, whereas Khalil et al. (2016) used support vector machines to imitate the strong branching ranking from the first few hundred nodes explored in the B&B trec. We refer the reader to Lodi & Zarpellon (201)) for a detailed survey on MI-based branching strategies.
Both Alvarez et (0117) and Khalil et al. (2016) learn classifier on fixed-dimensional, dandddesigned features. Recently, however, several works have proposed deep-learning based branching strategics, starting from Gasse et al. 2019 Their GNN approach has been the basis of several following work. Specifically, Gupta et al. (2020) explored the relation between the original MILP and subsequent sub-MIL.Ps in a. B&B tree to design CPU-efficient neural network architecture. However, this relationship has more to do with the B&B characteristics than the oracle behavior. Similarly, Zarpellon et al. (2020) explored learning suitable representations based on the evolution of the B&B tree. [Peng & Liao| (2022) investigated, in the context. of combinatorial auctions instances only, the effects of B&B node sampling to collect the training data. Finally, Nair et al. (2020) proposed a GPU-friendly alternating descent method of multipliers approach to solving linear programs that could be use to run strong branching on larger instances, allowing them to show that the approach could scale to large, heteroneous datasets. In none of these works, however, has the parent-child lookback property been explored in the context of training machine learning based variable selection strategies.
More recently, works have tried move beyond imitation learning and have investigated reinforcement learning formulations for learning to branch. [unn et al. (2020) used simple evolutionary strategies approach, but they only obtained improvements very homogeneous benchmarks, while reporting subpar results
4

---

Published in Transactions on Machine Learning Research (09/2022)
the harder benchmarks of Gasse et al. 2019 used in this work. Zhang et al. (022) used imitation
learning framework of [assse et al. 2019) to pre-train GNNs before using hybrid reinforcement learning
and Monte-Care tree search framework, reporting more encouraging results. In parallel, Etheve et al. (2020)
proposed a Q-learning approach on value functions representing subtree size, and Scavuzzo et al. (2022)
reinterpreted their approach as reinforcement. learning on a tree-shaped Markov decision processes. Parsonson ct al. (2022) proposed a similar mechanism, where the search tree divided into small diving paths, that are used as imitation targets. These works all seek address the problem of the long episode lengths using topological information from the branch-and-bown tree.
Although an interesting step forward, these approaches are nonethcless not currently competitive with imitation learning methods, which remain the state of the art. Indeed, they face unusual challenges in this context, including that poor decisions lead to longer, rather than shorter episodes, and also that transitions between states are also particularly computationally slow, since they involve solving linear programs. For these reasons, like most works, we chose to focus on the more successful strategy of imitation Iearning. Nenetheless, it is plausible that encouraging a lookback property in reinforcement learning policy could lead to similar benefits to those explored in the context of this work.
3 Preliminaries
A MILP is mathematical optimization problem characterized by a linear objective function and linear constraints in variables A generic representation of MILP is follows:
c s.t. Ax b, REZ'R""?
(1)
where R" is the vector of cost coefficients, A E R is the matrix of constraint coefficients, b R is vector of constant terms of constraints, and p > 0 decision variables are constrained to take integer values.
The B&B algorithm proceeds as follows. The Linear Programming (LP) relaxation of the MILP, obtained by relaxing the integer constraints on the discrete variables, is solved to obtain a lower bound on the global optimum, thereby resulting x* as the optimal solution. If x" has integral values for the integer-constraine decision variables, then is integer-optimal and the algorithm terminates. If not, one of the decision variables with fractional value, & C, such that C {k| x & Z. & p). is selected to split the MILP in two sub-MILPs. The resulting sub-MILPs are obtained by adding additional constraints 24 S [ and z 2 [ respectively. We denote as C the set of branching candidates, while the variable is termed as a branching variable. The algorithm proceeds recursively in this fashion by selecting the next sub-MILPs to operate on.
Denoting the optimal value of Eq. [1] by P, and using the superscripts to denote the parent MILP, - to denote the child MILP obtained by adding the lower bound to the branching variable, and + otherwise. The strong branching heuristic selects the variable Fab that has the maximum potential to improve the bound, namely
= arg max max PF - -P Prr max - pD, p0, crrl], kEe
where 6LP > is a small enough value to prevent the scores to collapse to 0 because of no improvement on either side of the branching (Achterberg] 2007).
4 Methodology
In this section, we describe our proposals to incorporate dependencies between successive nodes. A bipartite graph representation of MILP denoted by 9 E (V, E, C), where V E Ruxd, E E Rixd, and C E mxdd, Here, V is the matrix of features for n decision variables, is the matrix of features for m constraints, and E is the matrix of features for variable-constraint pairs. The terms dy, de, and de are the numbers of input features.
5

---

Published in Transactions on Machine Learning Research (09/2022)
The data is collected by using the strong branching heuristic to solve instances of manageable size, thereby yielding N graphical representations of MILPs, {G:) the set of candidate decision variables, C, with fractional value at a node i, and their corresponding strong branching scores 8; E R We use 8.j to denote the strong branching score of the jth candidate in C. We denote the strong branching target chosen during the solving procedure by Mi, and the set of second-best strong branching variables by 2; = arg , Sij- Thus, Z, may include variables which have the same strong branching score as y if there is a tie, else it includes all the variables with the second-best strong branching score, which can be more than one.
We denote the parent graph by superscripl 0 and the child node by a superscript bipartite graph of the i-th observation is denoted by 9 and the child graph by g.- Note that drop the superscripts whenever we do not need distinction between parent and child nodes. We use D [(G) sf, s.gg ,
Thus, the parent
(1, N to denote the entire dataset.
Defining a GNN by function fo that is defined over the parameter space O, Gasse et al. (0019 proposed to find the optimal parameters by empirical risk minimization of the cross-entropy loss between the predictions and the strong branching target over the dataset D. Thus, if there are n decision variables in 9r, fo(g.) e R" represents the scores predicted by the function fo- Denoting y; one-hot encoded vector with the value of at y, and 0 elsewhere, 0g is determined by solving
O7 arg min
CB)))
(2)
N
where CE is the cross-entropy loss function, and w, is the relative importance given to the observation i, which may depend on the depth of the node in the B&B tree (Gupta et al. 2020
4.1 Second-best e-smooth loss target
Keeping the cross-entropy loss function as is, we modify the target to a smooth label 2,, iee, instead of one-hot encoded vector yt, z, carries value of 1- e at the index of the strong branching target yi, while the value of is equally divided among the second-best strong branching decisions in 2, Thus, obtain the optimal parameters
N 0% arg min w. CF((f(()))) 22)-
A modified target such as z; in Eq. 3 yields parameters that lend to preserve the ranking of the second most important decisions. While intuitive and simple to implement with minimal changes in the existing framework, 0 is still not informed from the parent behavior.
4.2 Parent-As-Targee (PAT) lookback loss term
Here, we are interested in incorporating the relation between parent and child outputs as it happens under the strong branching oracle. In doing so, we expect the learned parameters to more appropriately represent the strong branching behavior. Defining the lookback condition L, at the node as
1,
yt 2 otherwise,
L =
(4)
0.
we consider an additional term to Eq. 2 or Eq. 3 that enforces fe to follow the same ordering between parent-child nodes whenever L, 1. We call this Parent-As-Ten Target (PAT) lookback term, designed to enforce
similarity between the logits at the parent node for the candidates C of the child node, denoted as [C!)) and the logits at the child node for the same candidates Ct2, denoted by fo(g)). Thus, obtain 0 GPAT with

---

Published in Transactions on Machine Learning Research (09/2022)
the target y;
0 yPAT = arg min
N w:
(CE(f((G)).)))
N Σ 1[4}
1[Ls} APAT CE((A(()) (5)
0
N ==1
or we obtain PAT with the target 2, as
0 PAT - arg min
wi (C Σ 1[L,}
N
1[1) APAT CE(GCO)) (6)
The first term in the brackets represents the usual cross-entropy loss which favors getting the top strong branching variable right. The second term favors aligning the predicted scores of the socond-best variable in the parent node whenever it is the best in the child node i. This term is active only when the lookback condition is satisfied. Here, APAT is the relative importance given to the lookback condition, whenever it holds.
5 Model Selection
The dataset D is collected on instances of manageable size such that reasonable number of observations are collected within certain time budget (e.g., 1 day). We label these instances Small. Given various hyperparameters involved in training machine learning models, a standard practice is to select a model with the best validation accuracy. However, owing to the sequential nature of the branching decisions, the validation accuracy not necessarily indicative of the models' performance on other metrics such as running time. For example, due to bad branching decisions carly on in the search, the models might later face sub-MILPs that are not representative of the training dataset, thereby leading even worse decisions. Alternatively, model might make reasonably good guesses of the strong branching variables, but the overall running time may be dominated by the solving time of the intermediate LP relaxations.
In general, a practitioner is interested in using the learned models to solve problems that are potentially bigger than those used for data collection and training. We label these instances as Big. To obtain some estinates of a model's ability to generalize to Big instances, we solve K randomly generated Medium instances of intermediate size by using each of the learned branching strategies, time limit of T seconds per instance. The aggregate performance (e.g., arithmetic mean, geometric mean, etc.) of the branching models can be evaluated in terms of (a) solving time, denoted by t(b), across K instances, e.g., 1-shifted geometric mean, (b) node counts, nlb, B), across the instances that are solved by all the strategies in B, or (c) number of solved instances within the time limit, denoted by w(b). Similarly, one can also define a metric based on the optimality gap of unsolved instances.
B, to guide the MILP solver within
In exploring generalization metries, we need to further distinguish between different objectives that a practitioner might have. For example, (a) Minimum solving time: the branching strategy that solves the instances as fast as possible; (b) Maximum wumber of inslances solved: branching strategy that solves the most instances to optimality within certain time budget, irrespective of whether the strategy solved the instances fastest or not; or (c) Minimam node count: branching strategy that yields the smallest trees.
Thus, even though the models are trained to mimic the strong branching oracle, thereby expecting to yield the smallest tree, we incorporate larder-to-formulat objectives by selecting the learned model using a combination of aggregate performance measures. Thus, to incorporate the objective (a), we sclect the branching strategy as per
B -0= t() S min t(b) + +.).
B
(7)
bime arg min min n(b, B'),
bEB'
where we introduce 4 as tolerance parameter to account for the variability that inherent to hardware- dependent measurements of solving time. For instance, & considers all the branching strategics b e B with aggregate solving time within second of the best such strategy, i.e., t(b) minker ((b) +
7

---

Published in Transactions on Machine Learning Research (09/2022)
The objective corresponding to solving the largest number of instances in the minimum amount of time be formulated as
B' = -jljEB, w(i) = max w(b)):
8" -iijj, t(j) S min ((6) + t
(8)
6 solved Siddeeddimme
arg min nb, B3)) bEB"
which is slightly different than the objective of selecting the strategy with the minimum time that also solves the most instances,
B' -ijjeB, (0) S min ((6 + e).
B' -iijEB, w(j) max w: (b))
(9)
b ismeessoved = arg min n (b, (l, BEB"
We discuss other possible formulations in Appendix
6 Experiments
To evaluate the performance of our proposed methods, we consider four benchmark problem families: Combinatorial Auctions, Minimum Set Covering, Capacitatod Facility Location, and Maximum Independent
Set. These the same problems that have been used extensively in the "learning to branch" literature (Gupla
et al. 2020 Scavuzzo et al. 2022 Etheve et al.) 2020 Sun et al. 2020) since introduced in Gasse et al. (2019)
Specifically, we collect dataset D for each of the problem families by solving the Small instances using SCIP [Gleixnrr et al. 2018) with the strong branching heuristic. Our models are trained to minimize the
objective functions as described in Equations
or G Due to the space constraints, we leave the
instance size, dataset collection, and training specifications to Appendices D and F respectively.
Baselines. To demonstrate the utility of the proposed models, we consider three types of widely used branching strategies: (a) Reliability Pseudocost Branching (RPB): Given the online statistical learning aspect of this heuristic, it has been shown to be the most promising among all. The commercial solvers use this as a default branching strategy; (b) TunedRPB: Given that we are focused on learning branching strategy suitable for problem sets coming from fixed distribution, select the ones suited best for the problem family. Specifically, we run grid search on two RPB parameters representing trade-off between running time and the iterative performance (see Appendix G We select the best performing parameters using the model selection framework from Section 5 making this tuned heuristic directly comparable to our method; (c) Graph Neural Networks (GNN): As proposed by Gasse et al. (0019) and widely used in the community, we use GNNs trained on the same dataset as our proposed models. These models have been shown be the best among all the other machine learning based models. Finally, we also show the performance of our gold-standard strong branching heuristic that is used to collect the training dataset (FSB).
scarch through the paramcters of RPB to
Evaluation. We replace the variable selection heuristic in SCIP Gleixner et al. (2018) with the strategy to be evaluated. For each of the four problem families, solve 100 randomly generated instances across three scales: Small, Medium, and Big (sec Appendix D) Since Combinatorial Auctions' big instances are solved fairly quickly, we exlend the evaluation to slightly bigger instances. Increasing scale is expected to increase the running time of the B&B algorithm. All Small and Medium instances used for evaluation are different from those used for training and model selection. Given the NP-Hard nature of the problems, we used the time limit of 45 minutes per instance to solve these instances using SCIP (Gleixner et al. 2018). See A Appendix H for the specifications of SCIP and the hardware used for evaluation.
8

---

Published in Transactions on Machine Learning Research (09/2022)
Evaluation Metrics. As per the standard practices in the MILP community, the performance of B&BB solvers is benchmarked across the following metrics: (a) Time: 1-shifted geometric mear of solving time of all the instances, irrespective of whether the instance was solved to optimality or not; (b) Nodes: 1-shifted geometric mean the number of nodes of the commonly solued instances (denoted by in parenthesis for clarity) across all branching stralegies; nole that this is a hardwaree wandeere-nndeeeendet measure of performance; (c) Wins: number of instances that were solved (to optimality) the fastest by the branching strategy; (d) Solved: Total number of instances solved within the time limit; and (e) Time: I-shifted geometric mean of solving time of the commonly solved instances. The commonly solved instances are subset of instances that have been solved to optimality by all the branching strategies.
Model Hyperparameters. We consider a grid search over the following hyperparameters: (a) loss-target E {v. =), where 2 refers to the modified loss function proposed in Section 4. and to the typical loss function that focuses only on the top strong branching variable; (b) Xι, E (0.0, 0.01, 0.1, 1.0), the Ig-rogularization penalty; and (c) XPAT (0.01, 0.1, 1, 0.2, 0.33 to define the strength the PAT lookback loss term proposed in Section 4.2 While we consider X for both fg and o2 for OPAT we consider the best performing model among all the hyperparameters (loss-target, Ata ApAr) For each hyperparameter configuration, train
five randomly seeded models described in Appendix [ Finally, 0g represents the baseline GNN from Gasse
et al." 2019)
without any of our proposed modifications.
48.0
70.0
54.4-
Maximum Validation Accuracy
55.2-
54.0
47.4
69.4-
53.8
55.0 69.2
47.2
53.6
47.0
69.0
54.8
53.4
46.6-
68.6
53.0
0y
02 cauctions
OPAT
0
0₂ setcover
OPAT
0,
82 facilities
θPAT
9,
0₂ indset
Figure 3: Maximum (across the hyperparameters) mean validation accuracy (1-standard deviation) of the proposed models is better than the bascline GNNs (0y). We see that the models trained with smoothed target (0z) and those with PAT lookback loss term (OPAT) result in better validation accuracy.
6.1 Results
Hyperparameter Selection. Figure shows validation accuracy of the best performing hyperparameters for fy: 0z, and fraT according to the validation accuracy on collected dataset D. However, select the models based on the generalization performance, we solve 100 randomly generated medium instances and gather the metrics described above. Table [ shows the selection of hyperparameters for 0rar as per various criteria (see Appendix I for the best parameters for 0, and 0z). We observe that the models selected by validation accuracy are not always preferred by the selection criteria defined on the evaluation of medium instances. Second, we observe that Eq. (8) and 9 may or may not have consensus among them; strategy might have the fastest solving times for all instances except one, but other strategies might solve all the instances just
slightly more time. Third, we observe that the time limit per instance, T, does play a role in model selection;
For complete definition, refer Appendix A.3 in Achterberg 2007

---

Published in Transactions on Machine Learning Research (09/2022)
both facilities and indset have different preference. Finally, we observe that even though the modified target is not preferred by all the problem families, there is a consensus for the use of the PAT lookback loss term.
Table 1: Best performing hyperparamcters (loss-target, X1, APAT) } for APAT- We see that loss-target z is preferred by some problem familics, while the PAT lookback term is preferred by all. In addition, the model selection criteria does impact the chosen hyperparameterrs
Problem family
Validation Accuracy
Eq. (8 (T
30mins)
Eq.
(T 30mins)
Eq. (8)
(T 15mins)
cauctions
{y. 0.0, 0.01)
(2,0.0,0.1}
3,0.0,0.1)
(2.0.00.1)
setcover
{y, 0.0,0.0.11 0.1]
(v.0.0,.11
fy,
0..0.00.11
facilities
(2,0.0, 0.0}
{2.0.0,0.13
02,0.0,0.13
(2,0.0.0.3
indset
0.0,
(2,0.01,0.2)
0v.0.10033
(v. 0.1,
1.0
Parent as Target
Normalized Time
0.8
True
False
Nodes
0.6
0.4
Loss target 6,
0.2
6:
0.0
lime(1.2s) Nodes(6a)
limeto.as)
Nodes/42) setcover
ls) Nodes(18)
lime('s Jsl Nodes]
cauctions
facilities
indset"
Figure 4: We plot the range-normalized (range is specified in parenthesis) Time and Node performance of the selected models as per Eq. ( The centered "X" black mark shows the final models that were selected to be used for evaluating the performance on bigger instances. The points with a red outline show the performance of the models selected according to the best validation accuracy (Note that we omit such models for indset it distorts the scale of the plot: see Appendix J for complete data).
Validation performance on Medium instances. To assess the interplay between our proposals in Section 4 and the model selection framework proposed in Section 5 we compare the performance of the selected models using Eq. ( (T = 30 minutes) for each of fy, 0z, 0yPAT, and (IPAT- Figure compares their performance on medium instances with respect to Time and Nodes. To accommodate different scales of time and nodes, we plot the norma-nordalized values of these measures and show the range of these measures in parentheses.
The centered black marks show the final models selected per Eq. [8] The models chosen as per validation accuracy are shown with transparent marks with red border.
We make the following obsorvations. First, the PAT lookback term is beneficial for the generalization performance most of the time. We observe that for the facilities set of problems, the current GNNs already respect the lookback condition sufficiently well that the proposed modifications do not yield significant improvements compared By. Second, we see that the cauctions and setcover models perform equally well with respect to time, thereby making the node count an important criterion for identifying better branching models. This is especially important because time measurements reliable. Third, central to the motivation of our model selection framework, the models chosen per validation accuracy do not fare well on practical objectives such as Time and Nodes
hardware-lependdent and thus not
Evaluation on Big instances. Given that sets of Small and Medium instances have already been used training and selection of the final models, we leave the evaluation on additional sets of unseen instances from these families to Appendix T. Here, we evaluate the performance of the selected models (as per Eq. ( (T 30
10

---

Published in Transactions on Machine Learning Research (09/2022)
minutes)) on bigger instances. We use the same instance scaling scheme as proposed by Gasse et al. (0019 (see Appendix D). Table shows various evaluation metries as computed from the evaluation of 100 randomly generated Big instances. Since Big instances of Combinatorial Auctions are solvable by all the strategies, we extend the scale of these instances to Bigger instances. Specifically, we observe that fAAT (GNN-PAT) outperforms the baseline model (GNN) in all the problem families on all fronts Time, Wins, Solved, and Nodes. As an example, for Maximum Independent Set problems, we observe 15% decrease Time and a 22% decrease in Nodes. Notably, GNN-PAT increases the number of "Solved" instances by to 5 for all but one problem family. Solving additional instances to optimality is testament to the improved branching decisions brought about by GNN-PAT.
Finally, as noticed above, the learned models for Maximum In- dependent Set might result a different hyperparameter configura- tion based on the selection crite- rion. Therefore, performance of the GNN-PAT mod- els that are selected by each of the Eqs. and (9) against. GNN in Table 3 We observe that as per the selection criterion of Eq. (8) the branching strategy solved the most number of instances. However, as Eq. (9) prefers the strategy with overall lower running time, we ob- serve superior performance of the branching strategy on Time of com- monly solved instances. These ob- servations confirm that the proposed model selection approach yields the expected outcomes on unseen test. instances.
Table 2: Performance of branching strategies on Big evaluation
instances. The best performing nunbers are in bold. Refer to Section for metrics. Since all of the Big Combinatorial Auctions instances were solved to optimality, we extend the evaluation to Bigger instances (*since only 10 instances were solved using FSB, we omit it here; See A Appendix for the full results including those on Big instances.)
compare the
Model
Time
Time (c)
Wins
Solved
Nodes (c)
n/a
n/a
n/a
a/a
n/a
026.81
434.92
80
17979
TONEDRPR
644.20
450.06
80
18 104
UNN
507.06
333.59
14
80
17 145
GNN-PAT (ours)
177.26
310.22
69
81
16 388
Combinatorial Auction (Bigger)
FSB
2700
n/a
0
n/a
RPU
1883.32
1213.57
47
58 766
TUNEDRPB
1851.83
1168.58
GNN CNN-PAT (ours)
1708.99
991.07
54
39 5335
1601.28
892.85
51
59
38 385
Set Covering
758.19
737.66
607.19
92
104
TUNEDRPB
751.27
619.27
91
97
GNN
646.03
525.80
16
92
293
CSN-PAT (ours)
581.91
471.20
66
95
301
Capacitated Facility Location
Similarly, we look at the effect of the time limit T on the selection criterion. The models selected as per Eq. (8) for facilities differ depending the specified time limit T (see Table D. We look at the how the time limit might affect generalization performance in Table 3 Specifically, we observe that insufficient time
FSB
2700
n/a
0
n/a
RPU
1984.91
888.04
32
12-407
TUNEDRPB GNN
2016.85
952.25
1207.62
279.71
14
65
7934
CNN-PAT (ours)
1035.32
233.97
56
70
6122
Maximum Independent Set
to evaluate Mediium instances may lead to suboptimal hyperparameters. To conclude, we've shown that the model selection criterion will impact generalization performance significantly.
7 Discussion
An objective in this paper was to imitate the strong branching behavior more closely by taking advantage of its lookback property. The proposals in Section are aimed at doing so. A post-hoc analysis shows up to 16% improvement in the GNNs' ability to follow the lookback property (sce Appendix M). Such improvements are evident at various depths from the root node (see Appendix N
We can argue that the proposals in Section f are regularizers or inductive biases. Although the modified target and the PAT lookback term were inspired to induce the required oracle behavior, owing to the lack of interpretability of GNNs, we cannot attribute the GNN-PATs' performance improvements to the ability follow the lookback property with 100% certainty. However, if we consider that the proposals did cause the
11

---

Published in Transactions on Machine Learning Research (09/2022)
observed improvements, we might consider it as inductive bias. Inductive biases are defined as any pre-coded knowledge about the target behavior, such as neural network architecture, choice of features, or loss function.
Table 3: Performance measures on branching strategies selected as per different criteria specified in Eqs. S and (9) and the specified time limit per instance T. We observe that each criterion supports the respective measure on scaled-up instances.
Further, the PAT lookback loss term similar to the objective function in knowledge distilla- tion (Hinton et al. 2015), i.e.,
are minimizing the cross- entropy between the logits of one model (child node) and the other model (parent node).
Model
Time
Time
Wins
Solved
Nodes
1207.62
753.81
65
29.52 573
GNN-PAT (Eq. GNN-PAT (Eq.)
1035.32
621.42
38
70
21574
1063.
613.96
Maximum Independent Set
Whereas the original distilla-- tion framework, there are two separale models (Leacher and student) that act the same inputs, the PAT lookback term can be understood as form of distillainn that acts through the same model but on different observa- tions which share some characteristics (e.g., output logits). Thus, we can understand that the PAT lookback term distills knowledge from the parent node to the child node, as was intended.
646.03
562 662.20
13
314
CNN-PAT (Eq. GNN- (Eq. Saiins)
30mins)
581.91
503.85
58
95
326
635.04
388
Capacitated Facility Location
Finally, our model selection framework enables us to incorporate complex metrics like Time and Nodes into hyperparameter selection criterion. We hope that this framework will help aligning the research in machine learning methods for MILP solvers with practitioners' varied objectives.
Limitations. As illustrated in Figure 7 the GNNs for facilities instances are capable of capturing the lookback condition 80% of the time. Since it is not possible consider all possible problem families and their varied formulations, useful all the time. Therefore, we recommend checking for the prevalence of the lookback condition to get some idca of expected improvement.
cannot make definitive claim on whether our proposed modifications will be
Further, due to time and resource constraints, we restricted the evaluation for model selection to just 100 Medium instances. However, for a more robust selection, we suggest using a larger set of instances. One can also consider sctting the size of Medium instances such that majority of them are solved, thereby resulting in robust selection of better performing hyperparamelers; see Table [ on how the best hyperparameters vary according to time limit per instance T and Table g for the effect of T generalization performance.
Finally, we emphasize that the model selection criteria are very much dependent on how these models will be deployed. For example, a practitioner might only be concerned with solving the maximum number of instances (to optimality) while ensuring the smallest optimality gaps in the unsolved instances. This objective can be formulated within our proposed framework, but considering all such formulations is beyond the scope of this work.
Future work. Although we did not specify the minimum optimality gap as the objective of the branching strategies, we ran a post-hoc analysis to compare 1-shifted geometric mean of optimality gaps of the commonly unsolved instances (lower is better). Figure 5 shows that, except for setcover instances, the proposed branching strategics are able to close larger gaps than the rest. We acknowlodge that, depending on the use, the optimality gap might be of primary importance to the practitioner. We think that the exploration of optimality gap as secondary objective could be subject of future work.
As evident from the gaps in Figure 7 (Appendix M) and Figure 8 (Appendix N.. we plan to design more ways to incorporate the lookback condition explored in this work. While we studied how the parent and child nodes in a B&B tree are related with respect to a simple PAT lookback condition, there still exists several ways which such nodes can be related (sce Appendix O for another example). Thus, the design of machine learning algorithms to discover and exploit such dependencies could be an important direction for future research. Moreover, such machine learning-aided discoveries can be equally important. for the MIL.
12

---

Published in Transactions on Machine Learning Research (09/2022)
community to inspire the design of novel heuristics improve the existing mamaaly-designed heuristics applicable to general instances.
8 Conclusion
With the huge gap between the perfor- mance of deep learning based heuristics and the oracle heuristics, we expect that the research efforts might require more in-depth investigation of how to imbue these models with the same "reasoning" the oracles themselves. In this line of
1.25
37
Goometric Mearg Opcinaitty unselled
1.30
0.0
3.-
"
1.3
2.1
0.80
2.-
thought, we investigated how the parent- child nodes of a B&B tree are related to each other under the oracle heuris- tic, We found that quite often, the par- ent's second-best choice the child's best choice. To incorporate this lookback con- dition into model training, we designed two methods to align the models more closely with the strong branching oracle's behavior. We believe that this investiga- tive approach to imitating oracle behavior could be useful way to close the gap bo- tween machine learning and the oracle hcuristics.
0.35
0.75
Ave
91
RP0
Rinestpp
cauctions (18)
seccever (48)
facilities (5)
Indset (30)
Figure 5: Post-hoc analysis of optimality gap of commonly un- solved instances (number is shown in parentheses next to the problem family label) shows that OPAT is able to achieve the best optimality gap (except for setcover) even though it is not the primary objective specified in the model training.
Broader Impact Statement
This paper continues the exploration of the use of machine learning techniques for the most critical step branch-and-bound methods, ie., variable selection. Branch and bound is the method of choice for solving a myriad of discrete optimization problems appearing in all sort of applications (a few named in the introduction of this paper) and it is the basic scheme of all commercial and open-source discrete optimization solvers. Thus, the impact of the research in the area is potentially very high, not only from methodological perspective but also in terms of day to day challenges that we all face, including drug discoveries and climate change.
This paper significantly advances the research in the area by observing for the first time a hidden pattern, the lookback phenomenon, in the statistical evolution of the most successful heuristic for variable selection. The paper proposes several methods exploit such phenomenon and makes a significant step forward on the use of ML for discrete optimization.
References
Jawad Abrache, Teodor Gabriel Crainic, Michel Gendreau, and Monia Rekik. Combinatorial auctions. Annals of Operations Research, 153(1):1311166) 164, 2007.
Tobias Achterberg, Constraint Integer Programming. Doctoral thesis, Technische Universität Berlin, Fakultät II Mathematik und Naturwissenschaften, Berlin, 2007. URL
depositonce-1633 1634
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):42 54, 2005. ISSN 0167-6377. doi: htttp://d0ooooo///0000////..0.00
URL
http://wwwwcinnnceireettttt http::/wwww................o.aaa
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-basse approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195 2017.
13

---

Published in Transactions on Machine Learning Research (09/2022)
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the TSP. Technical report, DIMACS, 1995.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, pp. 37-60. Springer, 1980.
Gérard Cormuéjols, Ranjani Sridharan, and Jean-Michel Thizy, A comparison of heuristics and relaxations for the capacitated plant location problem. European journal of operational research, 50(3):280-22) 297, 1991.
Bistra Dilkina, Rachel Houtman, Carla P Gomes, Claire A Montgomery, Kevin S McKelvey, Katherine Kendall, Tabitha A Graves, Richard Bernstein, and Michael Schwartz. Tradc-offs and efficiencics in optimal budget-consttrineed multispecies corridor networks. Conservalion Biology, (1(1):192 202, 2017.
Mare Etheve, Zacharie Ales, Côme Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Reinforcement learning for variable selection in a branch and bound algorithm. In International Conference on Integration of Construint Programming, Artificial Intelligence, and Operalions Research, pp. 176 185. Springer, 2020.
Seyed Alireza Fayazi and Ardalan Vahidi. Mixed-integer linear programming for optimal scheduling of
autonomous vehicle intersection crossing. IEFE Transactions Intelligent Vehicles, 3(3):287-299, 2018.
Brian A Foster and David M Ryan. An integer programming approach to the vehicle scheduling problem. Journal of the Operational Rescorch Society, 2772)3367-384 1976.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Fxact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pp. 15554-15566, 2019.
Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gollwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E. Lübbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, Marc E. Pfctsch, Christian Puchert, Daniel Rehfeldt, Franziska Schlösser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegschei- der, Jonas T. Witt, and Jakob Witzig, The SCIP Optimization Suite 6.0. Technical report, Optimization Online, July 2018. URL http:///wwwt http://wwwwiiiiiitiioo.o www.oooooooooooonnooooooooooooee HTMLL/20118/0//6622..mm
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-18009 2020.
He He, Hal Daume III, and Jason M Fisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014a.
He He, Hal III Daumé, and Jason Eisner. Learning to scarch in wranch-and-boneg algorithms. In Advances in Newral Information Processing Systems 27, pp.
2014b.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXie preprint arXiv:150s 10%.0:1503.02511, 2015.
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123:108353, 2022.
Frank Hutter, Holger H Hoos, and Kovin Leyton-Brown Automated configuration of mixed integer program- ming solvers. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 186-202. Springer, 2010.
Ivan Kantor, Jean-Loup Robincau, Hür Bütün, and François Maréchal. mixed-integer linear programming formulation for optimizing multi-scale material and energy integration. Frontiers in Energy Research, 8:49, 2020.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the Thirtieth AAAT Conference on Artificial Intelligence, pp. 724 731, 2016.
Elias B. Khalil, Christopher Morris, and Andrea Lodi. MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):10219 10227, Jun. 2022. doi: 10.1609 16609//aai.vaa www.aai.....2220661033 21262.. URL https:://ssssssatee http::///oo..aaaaa.oooo////a//ap http://meeeeppp////A//aaaaaalle/ 21262
Diederik P Kingma and Jimmy Ba. Adam:
method for stochastic optimization.
arXiv preprint
orXiu:1412.6900 2014.
A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28p3):pp. 497 520, 1960.
Kevin Leyton-Browd Mark Pearson, and Yoav Shoham. Towards universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM conference Electronic commerce, pp. 66 76, 2000.
Jeff Linderoth and Martin Savelsbergh. A computational study of search stralegies for mixed integer programming. INFORMS Journal on Computing, 11:173-187, 05 1999. doi: 10. http://ooo..........
Andrea Lodi and Giulia Zarpellon. On learning and branching: survey. TOP, 25:207-2200 236, 2017.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint ar 0rXiv2202..333/ 2020.
Tony Nowatzki, Michael Ferris, Karthikeyan Sankaralingam, Cristian Estan, Nilay Vaish, and David Wood. Optimization and mathematical modeling in computer architecture. Synlhesis Leclures on Computer Architecture, 8(4):1-144, 2013.
Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complezity. Prentice-Hade Hall, Inc., USA, 1982. ISBN 0131524623.
Christopher WF Parsonson, Alexandre Laterre, and Thomas D) Barrett. Reinforcement learning for branch- and-bound optimisation using retrospective trajectorics. arXiv preprint arXiv:2205.1434. 2022.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Chen Peng and Bolin Liao. Heavy-head sampling for fast imitation learning machine learning based combinatorial auction solver. Neural Processing Letters, pp. 1-14, 2022.
Yves Pochet and Laurence A Wolsey, Production planning by mized integer programming. Springer Science & Business Media, 2006.
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke Yorke-Smith, and Karen Aardal. Learning to branch with tree mdps. arXiv preprint arXiv:2205.1110 11107, 2022.
Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforccment learning. 2020.
Laurence A. Wolsey, Integer Programming.
1988.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing to learn branching policies. arXiv preprint arXiv:2002 051022000.0010,, 2020.
search trees
Tianyu Zhang, Amin Panitalebi-Dekkorre and Yong Zhang. Deep reinforcement learning for exact combina- torial optimization: Learning to branch. arXiv preprint ar arXin:2206.06000 2022.
15

---

Published in Transactions on Machine Learning Research (09/2022)
Appendix
A Lookback property on some real-world instances
We look at the frequency of the lookback property on some the real-world instances. Specifically, we study this property in the context of MIP instances related to wildlife management, first proposed by Dilkina et al. (2017). These instances have been used by the MTP community to demonstrate the efficacy of various proposals the real-world MIP instances Nair et al. (2020); Hutter et al. (2010); He et al. 20114 2014a) Table shows that at least 30% of the parent-child pairs exhibit this property.
Table 4: Frequency of the lookback property in the real-world instances is as prevalent as in the synthetic instances considered in the main paper. These instances are made available by Dilkina et al. (201)).
Instances
Description
number of parent-child pairs collected
number of parent-child pairs exhibiting the lookback property
Frequency of the lookback property
CORLAT
Corridor planning in Red-cockaded woodpecker diffusion conservation
5082
1765
34.73%
wildlife management
5115
1952
38.16%
RCW
B
Lookback property as function of depth-decile
16

---

Published in Transactions on Machine Learning Research (09/2022)
20.0
Ground truth
GNN
GNN
17.5
14
15.0
Frequency of lookback cond depph-decile 1%67
12
12.5
10.0
7.5
5.0
2.5
0.0
1
3
4
5
6
7
8
10
1
3
5
8
10
death decile
depth--declee
16
Ground truth
Ground truth
GNN
GNN
14
Frequeccy of lockback conditio depi-decile (55)
20
12
10
15
10
2
3 4
10
1
3
4
6
7
10
Figure 6: The gap between the frequency of the lookback condition per depth-decile for the strong branching oracle (Ground truth) and the traditionally trained GNNs (GNN) presents an opportunity to improve the GNN models. See Section 4 for the dataset collection procedure.
C Model Selection Objectives
To incorporate the objective of maximum solved instances, we select the branching strategy as per,
B' = (ijjeb w(j) = max w(bb),
8
(10)
6" = arg min (b, B')
BEB
Finally, to select the strategy only with the minimum node count, select the branching strategy per, arg min ra(b, B))
b*
(11)
BEB
Instance Specifications
We follow the procedure outlined by Gasse et al. (2019) generate and scale the instances. A well commented and functional code to generate these instances be found the authors' Github repository? 2 convenience, we describe the procedure here.
For
https://githubt http://hh...aaaaaaaaaaaaaaeaaaaa getpaaaateeerttteeeteteteeeeeeee inttteccssttttnsssommm
17

---

Published in Transactions on Machine Learning Research (09/2022)
D.1
Combinatorial Auction
These instances are generated following the arbitrary scheme described in the section 4.3 of Leylon-Brown et al. 2000p. The scalable parameters are the number of items and the number of bids.
Table 5: Parameters for Combinatorial Auctions
Instance Size
number of items
number of bids
USO
Amall--Trinnin
100
500
Dataset Collection & Training
Small-Validatioon Validation
100
500
Dataset Collection & Validation
Medium- Medium-Validatioo Validation
200
1000
Validation Evaluation
Small
100
500
Test Evaluation
Medium
200
1000
Test Evaluation
Big
300
1500
Test Evaluation
Bigger
350
1750
Test Evaluation
D.2 Set Covering
These instances are generated using the method described in Balas Ho (1980). The scalable paramcters are number of items, where the number of sets fixed to 1000.
Table 6: Parameters for Minimum Weighted Set Cover. Number of sets fixed 1000.
Instance Size
number of items
use
Smail-Training
500
Datasct Collection & Training
Small- Validation
500
Dataset Collection & Validation
Medium- Validation
1000
Validation Evaluation
Small
500
Test Evaluation
Medium
1000
Test Evaluation
Big
2000
Test Evaluation
D.3 Capacitated Facility Location
These instances are generated the method described by [Cornujooss et al. (1991 Fixing the number of facilities to 100, the scalable parameter is the number of customers.
Table 7: Parameters for Capacitated Facility Location. Number of facilities is fixed to 100.
Instance Size
number of customers
use
Small-Training Small- Validation
100
Dataset Collection & Training
100
Dataset Collection Validation
Medium-Validation
200
Validation Evaluation
Small
100
Test Evaluation
Medium
200
Test Evaluation
Big
400
Test Evaluation
D.4 Maximum Independent Set
These instances are generated by formulating the maximum independent set problem on a randomly generated Sorabási-Alberr with edge probability of 0.4. The scalable parameter is the number of nodes.
18

---

Published in Transactions on Machine Learning Research (09/2022)
Table 8: Parameters for Maximum Independent Set. Affinity is fixed to 4.
Instance Size
number of nodes
use
Small-Training
750
Dataset Collection & Training
Small- Validation
750
Dataset Collection & Validation
Medium- Validation
1000
Validation Evaluation
Small
750
Test Evaluation
Medium
1000
Test Evaluation
Big
1500
Test Evaluation
E
Data Generation
For each of the problem family, generate 10,000 Small random instances to collect training data, 2,000 Small random instances to collect the validation data, and 20 Medium instances for model selection. We use SCIP Gleixner et al. (2018) with strong branching hcuristic to solve the randomly generated instances and collect data of the form D = (G), s (!. i E 31.,,3 N]], as described in the main lext. We collected a total of 150,000 training observations and 30,000 validation observations.
The hand-cngincerod fcatures to the GNNs are same as Gasse al. (2019). For full description of these features, pleasee Section 2 in Supplementary material of Gupta. al. (2020).
F Training Specifications
Our models are all implemented in PyTorch (Paszke al. 2017). Following Gupta et al. (2020), we didn't change any of the training parameters, for example, used the Adam (Kingma & Ba 2014 optimizer with the learning rate of 1 training batch size of 32, and a learning rate scheduler to reduce the learning rate by a factor of 0.2 in the absence of any improvement in the validation loss for the last 15 epochs Moreover, we use the early stopping criterion to stop the training if the validation loss doesn't improve over 30 epochs. We validate the performance of model on the validation dataset after every epoch consisting of 10K random training samples. For each problem family, we trained models with five random seeds.
G TunedRPB
We consider two parameters in RPB to negotiate the trade-off between the compactness the resulting B&B tree and the computational time. Broadly, RPB performs strong branching on MaxLookahead candidates until it has collected enough information to reliably act on it. The selection of candidates is prioritized by the reliability of pseudoscores (statistically learned score to estimate bound improvement per fractional rounding of the variable) collected during the strong branching operations. If the minimum psucdoscore obtained by withere rounding up rounding down of the integer-constrained vairable is less than MaxReliable, the candidate is deemed unreliable, thereby prioritizing it in the next rows. Thus, we observe the following tradc-off by varying these two parameters: (i) MaxReliable: lower values prefer faster solving times at the expense larger trees, and (ii) MaxLookahead: higher values prefer shorter trees at the expense more computational time.
To have version of RPB that is trained on the training instances of interest, grid-search on the following values
hyperparameter
MaxLookahead:: 7,,7,8, 7,8,9, 9, 10, 11]
2. MaxReliable: {3, 4, 6, 7,8)
Specifically, we followed the procodure as described Section 5 solve 100 randomly generated medium instances, and select the best performing hyperparameters according to Fq.. [
19

---

Published in Transactions on Machine Learning Research (09/2022)
H Evaluation Specification
The ovaluation on Big instances is performed by using SCIP 6.0.1 installed on an Intel(R) Xcon (R) CPU E5-2650 v4 @ 2.20GHz. The learned neural networks, as branching models, are run on NVIDIA-TITAN Xp GPU card with CUDA 10.1. All of the main evaluations are done, as a standard practice, while ensuring that the ratio of the number of cores on the machine to the load average more than 4. This condition ensures that each process on the machine has at least CPUs a time.
The model selection is carried out by solving Medium instances the shared cluster specified by Nair et al. (2020) (see Section 12.7). Specifically, solve benchmark MIPLIB problem ('vpm2.mps') every 60 seconds to collect the solving time statistics. Given the solving times of the benchmark problem on the reference machine, we recalibrate the solving time of the instance, which is used as the final rumning time. We solve 20 independently generated Medium instances with five seeds resulting in 100 independent evaluations.
We followed the standard procedure used proposed by Gasse al. (2019) to set SCIP for evaluating branching strategies. Specifically, we used the following SCIP parameters evaluate the branching strategies
1. Cutting planes are allowed only at the root node
No restarts are allowed
Hyperparameters Model Selection
We use the ridge regression to penalize the parameters 8y and 0z. In addition to A12 dPAT searches over largel and ΛPAT. The following values were used for the hyperparameter search
Az2 0.1,
ΛPAT = 0.2.0.0.
3. largel [y,z)
Finally, Table 9 shows the best performing hyperparameters according to Eq. (8) for 0y, Oz, and OPAT. As
observed Gupta et al. 2020 we found that the (2-regularization is useful for the performance of indset models.
Table 9: Best performing hyperparameters according to Eq.
problem family
0g(Am
0z(212)
(par(target, Au2 APAT]
cauctions
0.0
0.0
(z,0.0,0.1)
setcover
0.0
0.0
0.0,0.01.1
facilities
0.0
0.0
(2,0.0, 0.1)
indset
0.1
0.1
fz,0.01,
J Performance on medium validation instances
Table 10 shows the data that was used plot the points in Figure 4 Due the huge variability in the
performance metrics of indset omit the performance of faccuracy from Figure
20

---

Published in Transactions on Machine Learning Research (09/2022)
Table 10: Data for Figure
Model
Metric
cauctions
setcover
facilities
indset
Time Nodes
14.66
38.21
159.60
73.16
0y
1077
1546
421
3102
Time
14.82
38.08
157.64
76.61
02
Nodes
1089
1527
437
3335
Time 13.83
37.92
160.13
74.80
yPAT
Nodes
1031
1503
429
3201
Time 13.65
37.89
153.81
71.32
02PAT
Nodes
1022
1513
420
2943
Time
14.22
37.92
159.59
572.39
0 accurocy
Nodes
1083
1503
421
9430
K Full performance of Combinatorial Auction models on Big and Bigger instances
Since Big Combinatorial Auction instances are solved by all the stralegies, we show them in Table 11 We extend the size of these instances to Bigger and show the evaluation in the main paper without FSB as there are only instances solved distorting the comparison of Time (c) and Node (c). See Table 12 for the full results.
Table 11: Performance of variable selection strategies Big instances for Combiatorial Auctions instances. See Appendix 1 for the instance scaling parameters.
Model
Time
Time (c)
Wins
Solved
Nodes (c)
FSB
2073.60
1643.78
0
53
336
RPB
202.78
113.47
1
100
4640
205.57
GNN
139.30
72.17
64
100
4142
GNN-PAT (ours)
141.63
73.31
100
3754
Table 12: Performance of variable selection strategies Bigger instances for Combinatorial Auctions instances. See Appendix D for the instance scaling parameters.
Model
Time
Time (c)
Wins
Solved
Nodes (c)
Optimallty Gap (16)
FSR
2591.81
1793.64
0
10
257
0.033 102
RPB
626.81
88.22
80
5719
0.009 555
TUNEDRPB
644.20
97.72
0
80
6191
0.009 605
GNN
507.06
69.22
80
5630
0.008 307
(ours)
L
Performance on small and medium instances
Table 13 shows the performance of the selected strategies as per Eq.
on small and medium instances. This
table is a counterpart to the Table 2
21

---

Published in Transactions on Machine Learning Research (09/2022)
Table 13: Performance of brunching strategies on evaluation instances. We report geometric mean of solving times, number of times method won (in solving time) over total finished runs, and geometric mean of number of nodes, Refer section for more details. The best performing results are in bold.
Small
Medium
Model
Time
Wins
Solved
Nodes
Time
Wins
Solved
Nodes
FSU
5.85
0
100
6
127.56
0
100
72
RPR
3.89
100
25.31
100
696
TUNEDRPE
3.72
100
24.70
100
591
CNN
2.10
82
100
71
13.15
58
100
693
(ours)
Combinatorial Auction
FSB
26.17
U
100
17
531.47
75
117
RPB
13.41
0
100
54
91.33
100
1119
TUNEDRPB
63
100
93.60
100
GNN
9.37
5
100
136
64.81
100
1030
(ours)
Set Covering
41.61
100
36.58
100
206.28
100
147
TUNEDRPB
37
1
100
21
211.77
2
100
140
GNN-PAT (ours)
29.46
15
100
112
159.95
30
100
329
Capacitated Facility Location
FSB
626.33
0
93
54
16341.4
0
60
46
RPB
58.03
100
702
144.92
100
770
TUNEDRPB
56.99
100
697
143.88
100
748
GNN
35.04
28
100
1000
76.53
36
100
795
(ours)
Maximum Independeut Set
M Post-hoc analysis of the lookback property
Ground truth
53.9
GNN
50
5003
PAT-GNN (Ours)
Frequency of lookback condition con
oF 5halll instances (36)
40
28.3
27.1
20
14.5
12.4
10
cauctions setcover
facilities
indset
Figure 7: Statistics of the lookback condition observed when the problems solved using the strong branching oracle (Ground truth). We also show how many times traditional GNNs (GNN) and our proposed GNNs (PAT-GNN) respect the lookback condition are on the offline dataset and do not reflect the final inference-time performance of the models. We find that the small improvements shown here results in large gains the inference time performance (sce Scction
the same dataset. Note that the displayed statistics
N Post-hoc depth-decile analysis of the lookback property
22

---

Published in Transactions on Machine Learning Research (09/2022)
20.0
Ground
GNN
GNN
[Ours]
17.5
PAT-GNN (Ours)
14
Frequency of lookback cond lion depih-decile 1%67
15.0
12
12.5
10.0
7.5
5.0
2.5
0.0
1
3
4
5
6
7
8
10
1
3
5
8
10
death decile
depth-deccle
16
Ground truth
Ground truth
GNN
GNN
14
PAT-GNN (Ours)
PAT-GNN
Frequeccy of lockback conditio depi-decile (55)
20
12
10
15
10
2
3
4
7
10
1
3
4
6
7
10
Figure 8: The gap between the frequency of the lookback condition per depth-decile for the strong branching oracle (Ground truth) and the Iraditionally trained GNNs (GNN) presents an opportunity improve the GNN models (PAT-GNN). See Section for the dataset collection procedure.
O Same strong branching decisions at the sibling nodes
Any MILP solving procedure results in tree of sub-problems, where each node shares some characteristics with its parent. This line of resemblance can eventually be traced all the way back to the original MILP. For example, the bipartite graph structure remains the same throughout the tree, a fact exploited by Gupta el al. (2020) to design CPU-efficient GNN-based models for learning to branch.
We investigate more of such dependencies among the B&B tree nodes of problem instances from the benchmark problem families (asss et. al., 2019) (see Appendix D for more details), which label cauctions (Combinatorial Auctions), setcover (Minimum Set Cover), facilities (Capacitated Facility Location), and indset (Maximum Independent Set).
Specifically, we investigate the frequency with which sibling nodes in the B&B tree have the same strong branching decision. Figure shows that this condition happens between 3-7% of the times on the small instances that were used to collect approximately 30K observations. The state-of-the-art GNNs (Gasse et al., 2019) are able capture this dependency as well. However, given that this condition is fairly less frequent relative the lookback condition, do not explore this condition in our current work.
23

---

Published in Transactions on Machine Learning Research (09/2022)
7
6.8
Ground truth
GNN
Frequency of same sibling decisions
smalllll instances (%)
3.7
3
2
1.4
0.5
cauctions setcover
facilities
indset
Figure Frequency with which sibling nodes a B&B tree have the same strong branching decisions (Ground truth), and the fraction of times this condition satisfied by GNNs trained as per Gasse al. (2019).
P Performance comparison with default SCIP
In this section, we provide comparison of our branching strategies with the default. SCIP and the tuned version of SCIP following the benchmarking procedure of Nair et al. (2020). But it is important to note that SCIP comes loaded with several heuristics, c.g., cut selection, primal heuristics, restarts, etc. To study the effect of branching strategies, the standard practice in the community switch off these heuristics. The results the main paper are based on this choice. Thus, comparing the branching strategics with default. SCIP isn't an apple to apple comparison.
However, it is still useful to where the proposed branching strategy stand relative to SCIP and some problem-specific tuned version of SCIP. Specifically, we ran grid scarch on 3 parameters of SCIP: (a) Presolve, (b) Heuristics, (c) Separating. Each of these parameters can take four values: (a) OFF do not use it, (b) DEFAULT; keep it at the default level (SCIP without tuning will use this setting), (c) AGGRESSIVE: use it
aggressively, and (d) FAST: use it, but do not spend too much time on it. Based on the Eq. S (T=30mins), we
found the following parameters suitable for the problem families: (a) cauctions (AGGRESSIVE DEFAULT, OFF), (b) selcovvr: (DEFAULT, DEFAULT, OFF), (c) facilities: (DEFAULT, DEFAULT, FAST), (d) indset: (FAST, OFF, FAST). Table 14 shows the performance comparison with SCIP and TunedSCIP. Specifically, we find that the proposed GNN-PAT retains its performance superiority over the default SCIP as well as the tuned version of SCIP.
24

---

Published in Transactions on Machine Learning Research (09/2022)
Table 14: Performance of branching strategies compared with SCIP and TunedSCIP. The best performing numbers are in bold. Refer to Section f for metrics.
Model
Time
Time (c)
Wins
Solved
Nodes (c)
FSB
n/a
a/a
u/a
626.81
431.92
0
80
17979
TUNEDRPB
644.20
450.06
0
80
104
582.47
396.90
4
17979
TUNRDSSIP
581.58
396.98
2
82
19937
507.06
GNN-PAT (ours)
477.26
310.22
64
84
16.888
Combinatorial Auction (Bigger)
FSB
2700
n/a
0
n/a
RPB
1883.32
1213.57
0
766
TUNKDRPB
1851.83
1168.58
0
155
SCIP
1755.15
1048.70 76
1
54
61 5-16
1708.99
991.07
3
54
39 535
CNN-PAT (ours)
1601.28
892.85
385
Set Covering
737.66
607.19
TUNEDRPB
751.27
619.27
1
91
97
SCIP
677.37
565.91
86
TUNEDSCIP
656.72
538,61
9-1
88
CNN
646.03
525.80
9/2
293
GNN-PAT (ours)
581.91
471.20
304
Capacitated Facility Location
FSB
2700
n/a
0
n/a
1984.91
865.90
0
32
11 886
TUNEDRPB
2016.85
927.68
0
12/186
1920.46
784.62
0
37
886
TUNEDSCIP
1578.01
443.89
48
10 392
1207.62
262.61
7233
GNN-PAT (ours)
1036.32
223.81
70
5722
Maximum Independent Sct
Results with 10,
geometric mean of time and nodes
We followed the evaluation protocol proposed by Gasse et al. (2019 (see Evaluation paragraph in Section of Gasse et al. (2019)). Therefore, our results in Tables are based on 1-shifted geometric means of nodes and time. However, since Achterberg (2007) studied much more diverse set of instances with widely varying solving behavior, they instances come from a specific distribution. Nonetheless, in Table 15 we show the results with 10,100-shifted geometric means. Our conclusions will still remain same.
10-shh-dd geometric means respectively. We not in this sctting
25

---

Published in Transactions on Machine Learning Research (09/2022)
Table 15: Performance branching stralegies on Big evaluation instances with 10,100-shifted geometric mean for time and nodes respectively. The best performing numbers are in bold. Refer to Section for metries. Since all of the Big Combinatorial Auctions instances
solved to optimality, evaluation to Bigger instances (*since only 10 instances were solved using FSB, we omit it here; See Appendix K
extend the
for the full results including those on Big instances.)
Model
Time
Time (c)
Wins
Solved
Nodes (c)
PSD"
n/a
n/a
n/a
n/a
n/a
RPB
633.20
438, 33
1
80
18052
TUNEDRPB
650.24
GNN
515.04
338.33
14
80
17 217
(ouns)
Combinatorial Auction (Bigger)
2700
n/a
0
n/a
18841449
1214.20
47
781
TUNEDRPB
1853.08
1169.20
0
48
58 169
GNN-PAT (ours)
1603.20
893.58
54
59
38 399
Set Covering
FSB
917.39
758.19
8
85
84
RPB
740016
608.88
3
92
157
TUNEDRPB
753.67
2
GNN
648.72
527.57
16
92
330
(ouns)
Capacitated Facility Location
2700
n/a
0
n/a
1987.27
889.92
0
12-443
TUNEDRPB
2019.12
954.35
0
33
12 976
GNN-PAT (ours)
1043.12
235.78
56
70
6186
Maximum Independent Sct.
26


Reviews:
[{"review_id": "U516SltYNo", "reviewer": "Reviewer_FN7m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is pretty clear and well presented. The logic flows well. The observation that Gasse’s GNN does not exhibit the “second-best” property of strong branching to the same extent is interesting. The authors modify the GNN to better imitate strong branching, which leads to improvements.\n\nIn my mind, the biggest weakness of the paper is in the way that it uses the observation that good branching candidates at one node are often good branching candidates at its children. Currently, I would describe the approach as a “patch”. It “just” gives an incentive to pick good branching candidates at the parent. Instead, I would be interested in understanding the shortcoming of Gasse’s GNN that makes it unable to exhibit this property naturally (supposing it is a desirable property). Once this shortcoming is identified, it ‘d be possible to change the approach so that the property naturally arises. I think that’d be more interesting and promising.\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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper extends the work of Gasse et al on using GNNs to imitate strong branching, the strongest heuristic we know in terms of number of nodes, in order to solve instances of MIPs drawn from the same problem. The work is based on the observation that the second-best variables to branch on at a node according to strong branching is often the best to branch on at the children of that node. The authors show that Gasse’s GNN does not exhibit this property to the same extent as strong branching, and therefore posit that a GNN that would exhibit this property would be a closer, stronger imitation of strong branching. Thus, the paper defines loss functions to encourage this behavior. Experiments show that the performance of the resulting branching rule is significantly improved.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "MAJOR\nThe paper uses shifted geometric mean with a shift of 1 for both time and nodes. However, the standard is 10 and 100, respectively, including in Tobias Achterberg’s PhD thesis, referenced by this paper. It would be good if the authors could justify why this standard was not followed, or follow it.\n\nMINOR\nThere are four minors issues with the last paragraph of Section 3.\nFirst, using - to denote the child obtained by adding a lower bound to the branching candidate is counterintuitive, because adding a lower bound will increase the value of the variable in the child’s LP. \nSecond, the argmax is taken over each branching candidates i, but the index i does not appear in the argmax, so it is unclear what changes in this expression when i changes. I would add i as a subscript to P^- and P^+.\nThird, I’d add epsilon_LP > 0 to be clear.\nFour, I’d add a reference to Tobias Achterberg’s PhD thesis for this section (already cited elsewhere in the paper).\n\nIn paragraph 2 of Section 4, I find the notation confusing. In Section 3, the letter i is used to index branching candidates. At the beginning of the first sentence of paragraph 2 of Section 4, it sounds like instances are indexed by i, but at the end of the sentence, we are told that nodes are indexed by i. Later in that paragraph, j is used to index variables. A small re-write would be good.\n\nIn Section 4.1, “equally distributed” is not formal. Furthermore, I suspect that the choice of parameter epsilon will be discussed later in the paper, but it might be good to say so at this point. “is still not aware of their parent behavior” is informal. I think I get the intuition, but I’m not sure.\n\nSection 5, paragraph 3: in my experience, practitioners do not care about criterion (c) Minimum node count. I would either further justify its inclusion, or remove it.\n\nEquation (7) is not clear. In particular, why is the number of nodes n() involved in selecting the branching strategy with the best solving time? Furthermore, at this point of the read, it is not clear to me why we need equation (7) at all.\n", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QGfhi3EcTl", "reviewer": "Reviewer_KxeK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe observed lookback phenomenon looks quite original to me. Finding similar regularities in other branching heuristics may lead to other improvements in ML-driven MIP solvers.\n\n## Weaknesses\n\n### Use of synthetic data only\n\nMy biggest concern regarding this paper is the use of synthetic datasets for both getting the inspiration for the lookback phenomenon and evaluation. I cannot be sure that lookback is as clearly observed in a diverse enough set of real-world MIPs and if that is not the case, then this paper's impact is fairly limited. (Nair et al, 2020) can serve as at least an initial source of more realistic datasets.\n\n### Lack of SCIP details\n\nParameters of SCIP can significantly affect solving time and are in some sense another set of hyperparameters for both training and evaluation. I would expect authors to ideally motivate their choice or at least report the configuration. It could be worth using SCIP (perhaps, with parameters tuned for each problem set individually) as a baseline. Outperforming tuned SCIP can indeed be regarded as a significant contribution to practical MIP solving.\n\n### Minor comments\n\nFSB abbreviature is used in the text but is actually never properly introduced. Does it mean full strong branching? ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the lookback phenomenon: in the branch and bound tree the strong branching heuristic would often predict a child's best variable as a second best variable one layer above. Authors explore ways of incorporating this phenomenon into GNNs trained to imitate strong branching. Empirical evaluation on 4 synthetic datasets from Gasse et al, 2019 suggests that GNN trained with Parent-as-target (PAT) lookback loss indeed better imitates strong branching and leads to shorter solving time. Authors additionally discuss a model selection framework that specifically assess generalization from smaller MIP to larger MIP instances.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Demonstrate the presence of the lookback phenomenon in a diverse set of real-world MIPs. In my opinion, without this data the paper cannot be accepted.\n2. Provide the configuration details for SCIP and add SCIP as a baseline. This is also quite crucial to understand where is the proposed method relative to the set of heuristics that are already included in SCIP. ", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yjl0tJQGS1", "reviewer": "Reviewer_X9jE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros.\n\n1. The paper is well written and easy to follow.\n\n2. The proposed methods are well motivated. First, they use the target smoothing to increase the frequency of the \"lookback\" phenomenon; second, they add regularization to make use of it.\n\n\n\nCons.\n\n1. The related works are quite old. As shown in Section 2, there is only one paper from 2022 and all other references are from before 2020. The authors need to include and discuss more relevant works arisen in 2021 and 2022.\n\n2. Missing discussions and comparisons with other efficient B&B solvers. Therefore, it is hard to know whether 15% time savings are significant or not.\n\n3. What is the definition of frequency of the loopback property in Figure 1?\n\n4. It seems the lookback phenomenon is not unique for the GNN B&B solver. I am curious about whether the proposed methods can also utilize lookback in other kinds of B&B solvers. If there is any unique relationship between lookback and GNN solvers, the authors need to clarify.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary.\n\nThis paper is dedicated to leveraging the \"lookback\" phenomenon in the B&B solvers. The \"lookback\" phenomenon means that with the strong branching heuristic, a child node's best choice was often the parent's second-best choice. Specifically, the authors introduce two methods, (1) target smoothing for the standard cross-entropy loss; (2) adding a parent-as-target lookback regularizer. They validate their proposals on standard benchmark instances and show 15% improvements in the solving times.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Refer to the weakness section.", "broader_impact_concerns": "I do not see obvious ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the lookback phenomenon in machine learning based mixed integer linear programming approaches. The authors point out that the standard GNN based approach does not show strong branching and suggests fixes to imitate strong branching. 

Reviewers commonly pointed out that the paper is clear and easy to follow. Also reviewers assessed that the claims made in the paper are accurate and well supported by the experiments. Moreover they pointed out that the proposed method is well motivated and interesting to the wider ML community. 

Authors have addressed major concerns (along with multiple minor changes) raised by the reviewers by including real world MIP results (raised by reviewer `KxeK`), expanding evaluation protocol (suggested by reviewer `FN7m`)  and explaining comparison against other efficient B&B solvers (by reviewer `X9jE`). In the end, all reviewers were satisfied with the author's response and changes and supported acceptance. 

In the final recommendation, reviewer `KxeK` mentioned: "it's worth accepting the paper to let researchers build on top of it, hopefully proving that these positive results also generalize to larger-scale problems." also reviewer `FN7m` mentioned: "the paper would be interesting to a sizeable part of the ML community."
Decision: Accept (poster)